我有很多（十亿个）2D点可以进行预处理，我想回答以下形式的查询：
给定矩形的所有四个角，输出矩形内的点数。
矩形可以处于任何方向（意味着矩形的轴可以以任何角度定向，而不仅仅是水平或垂直方向）。
有没有一种快速实用的算法呢？
更新。 是否存在任何数据结构来存储点，从而允许在次线性时间内证明查询？
Update II 似乎答案是肯定的。https://cstheory.stackexchange.com/questions/18293/can-we-perform- an-nd-range-search-over-an-arbitrary-box-without-resorting-to -si。无论如何都接受最受欢迎的答案。
将点表示为kd树。
也就是说，可以将其中每个节点代表一个点且每个非叶节点的二叉树视为在该节点的x或y值上垂直或水平（或者在每个级别上）划分当前区域。
然后，进行查询：
当前节点=根
当前面积=当前节点的面积（可以在沿着树递归时跟踪/计算）
如果当前区域完全包含在矩形内，则添加此节点作为子节点的点数（当前节点为+1）。
如果当前区域完全在矩形内部，则什么也不做。
如果当前区域部分包含在矩形内：
计算矩形中是否包含区域或点应该足够简单。
每个查询对随机数据平均应花费O（log n）时间。
尽管在某些病理情况下，这将花费O（n）时间（即，您将需要探索整个树/大部分树）。这种情况的一个可能的示例是，大多数点都围绕（非轴对齐的）矩形的边缘（内部或外部），这意味着上面提到的“不执行任何操作”部分将很少适用。
