我有很多（数十亿）二维点可以预处理，我想回答以下形式的查询：
给定一个矩形的所有四个角，输出矩形内的点数。
矩形可以处于任何方向（意味着矩形的轴可以以任何角度定向，而不仅仅是水平或垂直）。
有没有一个快速实用的算法呢？
更新。是否有任何数据结构来存储允许查询可证明处于亚线性时间的点？
更新二似乎答案是肯定的没有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) 时间（即您需要探索整个/大部分树的地方）的病理情况。这种情况的一个可能示例是当大多数点都在（非轴对齐）矩形的边缘（内部或外部）周围时，这意味着上面提到的“什么都不做”部分很少适用。
旧答案（如果您不能提前预处理这些点）：
通过快速包含位于内接矩形中的点，其边/边定向为 xy 轴，您可能会在性能上获得一些好处（不多，这取决于矩形的方向）。这需要一些预先计算，但考虑到您有很多积分这一事实可以忽略不计。
新答案：
rect是我们的输入矩形f1(point,rect)which 检查点是否在矩形内。你可以使用我上面提到的那个。f2(shape,rect)，这可以说明 shape 是否完全包含在 rect 中，或者 rect 是否完全包含在 shape 中，或者 shape 和 rect 相交或根本不相交f2为O(1)xy 轴的正截面）我们想要获得的是一种在运行时调用 f1 和 f2 最少时间的算法。例如，与（相同数量的）成比例的东西log(n)
所以我们想将二维平面划分为m多个形状，每个形状都包含p点。在运行时，我们用 f2 检查每个形状，我们可以有 4 种情况：
(O(p) )，然后结束。 (O(1) ) (O(p) )，然后继续。在第一种情况下，我们可能很幸运并迅速下降，但通常我们必须检查所有形状，并且对于其中至少一个形状，我们必须检查包含的所有点。所以这个算法是O(p) + O(m). 考虑到p * m = n，如果我们选择，p = m = sqrt(n)我们O(sqrt(n) )将获得用这种方法可以获得的最好的。(注意：我们执行 f1 多少次？这个数字实际上取决于矩形的形状，所以如果矩形被拉长很多，它将与许多区域相交，导致对 f1 的调用很多。但是，我认为我们可以假设矩形的度量与 的顺序不同n，sqrt(n)或者甚至log(n):n是巨大的。）
我们可以从这里增强；例如，我们可以说我们在形状之间有邻接关系，当我第一次发现形状和矩形之间有重叠时，我只检查连续的形状。但是，我们必须检查的平均形状数量无论如何都在 p/2 左右，并且O(p/2) = (O(p) ). 所以没有有效收益。
真正的收获是如果我们在形状中加入一些层次结构。
首先，我检查所有点，并找到我的界限值 max_x、max_y、min_x、min_y。（让我们假设这些边界是 > > n。如果我们可以有关于点分布的先验，我们可以针对的优化将完全不同）我们将空间划分为每个包含（大约）log(n) 个点的形状。我们首先使用 xy 轴将 2D 平面划分为 4 个形状（我也可以根据我的边界值居中）。这将是我们倒置金字塔的第一层。循环：对于每个包含超过 log(n) 个点的区域，我们使用垂直或水平线将区域分成两半（我们交替）。如果一个边界设置为无限，则分成两半，我使用相应的边界值。每个被分割的区域都包含一个指针到它被分割的区域。新区域是金字塔的第二层。我一直在划分，直到我所有的区域都包含（大约）log（n）个点。当一个区域被分割时，它包含指向“子”区域的指针。我已经建立了我的金字塔。倒置金字塔的顶层包含 n/log(n) 个形状，这是相当大的，但没关系：重要的是我们有 log(n) 个金字塔级别。注意：对于每个级别的每个形状，我们都知道它包含多少个点。注2：此预阐述平均每个金字塔级别的每个点分析一次，因此其复杂度为 O(n*(log(n) )。
当我输入矩形时，我使用 f2 检查第一级的形状。
O(log(n))）我丢弃任何其他形状。O(1)(O(log(n) )。现在是困难的部分：我们访问了多少个形状？同样，这取决于矩形的形状，它接触多少个形状。但是，对于每个级别，我们将访问多个不依赖于 的形状n，因此访问的形状数量与 成正比O(log(n) )。
由于 n 非常大，我们可以假设与矩形边相交的形状数量（这会导致对 f1 的昂贵调用）远少于O(log(n) )。整个算法应该是O(log(n) ).
还有进一步优化的方法，但任何东西都会保持平均水平O(log(n) )
最后一点：我们划分空间的方式必须控制多边形的边数，因为如果形状可以有很多边，不知何故取决于点的数量（根据我们称之为的函数g)，f2 将是O(g(n) )，并且它的复杂性必须再次乘以取决于n我们必须检查的形状数量的东西，所以可能不好。
您需要的是某种二进制空间分区数据结构。这将为您提供一个候选人列表，您可以对其进行真正的“多边形中的点”测试。
我建议您确保这是您真正应该自己编码的东西。例如，许多数据库都内置了这种功能。您的数据是否真的驻留在数据库中？可以吗？（重新发明轮子没有意义……）
您可以在此处看到多边形中点问题的一个很好的答案：如何确定 2D 点是否在多边形内？
我建议找到一种可以应用于空间的旋转+移位变换，以便矩形的一个角位于其中(0,0)，两条边沿轴x和y轴移动。
现在您通过这些点，应用相同的转换并检查0 < x < rectangle_max_x和0 < y < rectangle_max_y。
制作三角形。假设 abcd 是矩形，x 是点，那么如果点在矩形area(abx)+area(bcx)+area(cdx)+area(dax) equals area(abcd)内部。
解决问题的一种简化方法是找到包含给定 ( R ) 的最小轴对齐矩形 ( S )。使用一些空间树结构作为 kd 树来查找包含在S内的点的子集，最后，为该子集选择R内的点。
与@Dukelin 提出的直接使用R执行 kd 树搜索的方法相比，这种方法更容易实现。
您可以将 BoundBox 用于矩形，然后如果一个点在边界框内，您可以检查它是否与矩形碰撞，或者您可以使用定向有界框。
这是最简单的方法，不需要使用复杂的数据结构
如果速度是一个问题但内存/磁盘空间不是问题，请考虑执行以下操作，这应该是最有效的方法。
通过这种方式，您可以在进行任何重要的数学运算之前执行一些非常快速的测试：
public class DataPoint
{
double X, Y;
...
}
public bool IsInBoundingBox(Point p1, Point p2, Point p3, Point p4)
{
// assume p1, p2, p3, p4 to be sorted
return (X>p1.X && X<p3.X && Y>p4.Y && Y<p2.Y);
}
那么实际工作的顺序应该是这样的......
// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner
// See if the QueryRectangle in question is aligned with the grid; if it is,
// then the set of DataPoints that lie within the BoundingBox are within the
// QueryRectangle and no further calculation is needed
if (p1.X == p2.X || p1.X == p3.X || p1.X == p4.X)
{
// is orthogonal (aligned with axes)
foreach(DataPoint dp in listDataPoints)
if(dp.IsInBoundingBox())
{
// dp is in QueryRectangle; perform work
}
}
else
{
foreach(DataPoint dp in listDataPoints)
if(dp.IsInBoundingBox())
{
// perform further testing to see if dp is in QueryRectangle
}
}
或者，如果您想使用 viraptor 建议的旋转/平移解决方案...
// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner
public class DataPointList : List<DataPoint>
{
public List<DataPoint> GetPointsInRectangle(Point p1, Point p2, Point p3, Point p4)
{
List<DataPoint> tempListDataPoints = new List<DataPoint>();
foreach(DataPoint dp in this)
if(dp.IsInBoundingBox()) tempListDataPoints.Add(dp);
if (!(p1.X == p2.X || p1.X == p3.X || p1.X == p4.X))
{
// needs transformation
tempListDataPoints.TranslateAll(-1 * p1.X, -1 * p1.Y);
tempListDataPoints.RotateAll(/* someAngle derived from the arctan of p1 and p2 */);
// Note: you should be rotating counter-clockwise by some angle >0 but <90
// the new p1 will be 0,0, but p2, p3, and p4 all need to undergo the same transformations
// transP1 = new Point(0,0);
// transP2 = new Point(p2.Translate(-1 * p1.X, -1 * p1.Y).Rotate(/* someAngle derived from the arctan of p1 and p2 */));
// transP3 = ...; transP4 = ...;
foreach(DataPoint dp in tempListDataPoints)
if (!(dp.X>transP1.X && dp.X<transP3.X && dp.Y>transP1.Y && dp.Y<transP3.Y)) tempListDataPoints.Remove(dp);
}
else
{
// QueryRectangle is aligned with axes, all points in bounding box
// lie within the QueryRectangle, no need for transformation or any
// further calculation
// no code needs to go here, but you may want to keep it around for notes
}
return tempListDataPoints;
}
}
或者，您可以使用数组执行上述代码。我会留给你解决这个问题...
免责声明：我昨晚睡了 2 个小时，所以我不会校对。您可能需要做一些小修复。或者主要的。谁知道。:)
我将从沿任何轴预排序点数组开始（让它成为 x）。然后在矩形的边界框 x 投影中对具有 x 投影的点进行二进制搜索。这将大大减少要检查的点数。
然后我们可以通过检查它们是否在矩形边界框中来进一步过滤这些点。但是，是的，那将是线性的。
然后我们可以为矩形取一个变换矩阵（我假设我们已经有了它）。矩形是奇异 2-cube 的仿射变换，因此我们可以在不计算实际逆矩阵的情况下找到逆变换。
对于直接变换矩阵
A D a
B E b
C F c
解决方案是：
d = 1/(AE − BD)
A' = Ed
B' = −Bd
C' = (BF − EC)d
D' = −Dd
E' = Ad
F' = (DC − AF)d
a' = b' = 0
c' = 1
然后，通过对每个点应用逆变换，我们将把它转换成一个奇异的立方体，也就是说(0, 1)x(0, 1)，如果它最初位于一个矩形中，或者不是如果它不是。
UPD：或者，您可以执行以下操作，而不是所有转换内容：
设矩形P1..P4的点为和要检查的点A。
i = 1..4计算PAi为_Pi - A
现在的叉积(Pi.x, Pi.y, 0)x(Pj.x, Pj.y, 0)将测量由 A 和相应矩形的边缘构成的三角形。并且，由于原点都在xy平面上，结果会像(0, 0, Sij)，其中 Sij 是三角形的有符号平方。只需计算总和：
|(P1.x, P1.y, 0)x(P2.x, P2.y, 0)[3]|+
|(P2.x, P2.y, 0)x(P3.x, P3.y, 0)[3]|+
|(P3.x, P3.y, 0)x(P4.x, P4.y, 0)[3]|+
|(P4.x, P4.y, 0)x(P1.x, P1.y, 0)[3]|
并将其与矩形正方形进行比较。如果它或多或少相等，则该点在矩形中。会有一些小的计算错误，所以完全相等是不可能的。