performance - 如何确定 2D 点是否在多边形内？

Question

我正在尝试在多边形算法中创建一个快速的 2D 点，用于 HitTest (例如 Polygon.contains(p:Point) )。对有效技术的建议将不胜感激。

Answer 1

对于图形，我宁愿不喜欢整数。许多系统使用整数进行 UI 绘制(像素毕竟是整数)，但例如 macOS 对所有内容都使用浮点数。 macOS 只知道点，一个点可以转换为一个像素，但根据显示器分辨率，它可能会转换为其他像素。在视网膜屏幕上，半点 (0.5/0.5) 是像素。不过，我从未注意到 macOS UI 比其他 UI 慢得多。毕竟 3D API(OpenGL 或 Direct3D)也适用于浮点数，现代图形库经常利用 GPU 加速。

现在你说速度是你最关心的问题，好吧，让我们追求速度。在运行任何复杂的算法之前，先做一个简单的测试。在多边形周围创建一个轴对齐的边界框。这非常简单、快速，并且已经可以安全地进行大量计算。这是如何运作的？迭代多边形的所有点并找到 X 和 Y 的最小值/最大值。

例如。你有积分(9/1), (4/3), (2/7), (8/2), (3/6) .这意味着 Xmin 为 2，Xmax 为 9，Ymin 为 1，Ymax 为 7。具有两条边 (2/1) 和 (9/7) 的矩形外部的点不能位于多边形内。

// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
    // Definitely not within the polygon!
}

这是针对任何一点运行的第一个测试。如您所见，此测试速度非常快，但也非常粗糙。为了处理边界矩形内的点，我们需要一个更复杂的算法。有几种计算方法。哪种方法有效还取决于多边形是否可以有孔或始终是实心的。以下是实心的示例(一凸一凹):



这是一个有洞的:



绿色的中间有个洞!

最简单的算法，可以处理上述所有三种情况并且仍然非常快，它被命名为 射线转换 .该算法的思想非常简单:从多边形外部的任何地方绘制一条虚拟射线到您的点，并计算它击中多边形一侧的频率。如果命中数是偶数，则在多边形外，如果是奇数，则在多边形内。



绕数算法将是另一种选择，对于非常接近多边形线的点来说更准确，但它也慢得多。由于有限的浮点精度和舍入问题，光线转换可能会因太靠近多边形边的点而失败，但实际上这几乎不是问题，就好像一个点离边那么近，通常在视觉上甚至不可能查看器以识别它是已经在里面还是还在外面。

你还有上面的边界框，记得吗？只需在边界框外选择一个点并将其用作射线的起点。例如。点 (Xmin - e/p.y)肯定在多边形之外。

但是什么是e ?那么，e (实际上是 epsilon)给边界框一些填充。正如我所说，如果我们开始太靠近多边形线，光线追踪就会失败。由于边界框可能等于多边形(如果多边形是轴对齐的矩形，则边界框等于多边形本身!)，我们需要一些填充来确保安全，仅此而已。你应该选择多大e ?不要太大。这取决于您用于绘图的坐标系比例。如果您的像素步长为 1.0，则只需选择 1.0(但 0.1 也可以)

现在我们有了带有起点和终点坐标的光线，问题就从“是多边形内的点”转移到“光线与多边形边相交的频率”。因此我们不能像以前那样只处理多边形点，现在我们需要实际的边。边总是由两点定义。

side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:

您需要针对所有方面测试光线。将射线视为向量，将每一边视为向量。射线必须精确地击中每一侧一次或根本不击中。它不能两次击中同一侧。二维空间中的两条线总是恰好相交一次，除非它们平行，在这种情况下它们永远不会相交。然而，由于向量的长度有限，两个向量可能不平行并且永远不会相交，因为它们太短而无法相遇。

// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
    // Test if current side intersects with ray.
    // If yes, intersections++;
}
if ((intersections & 1) == 1) {
    // Inside of polygon
} else {
    // Outside of polygon
}

到目前为止一切顺利，但是您如何测试两个向量是否相交？这是一些 C 代码(未测试)，应该可以解决问题:

#define NO 0
#define YES 1
#define COLLINEAR 2

int areIntersecting(
    float v1x1, float v1y1, float v1x2, float v1y2,
    float v2x1, float v2y1, float v2x2, float v2y2
) {
    float d1, d2;
    float a1, a2, b1, b2, c1, c2;

    // Convert vector 1 to a line (line 1) of infinite length.
    // We want the line in linear equation standard form: A*x + B*y + C = 0
    // See: http://en.wikipedia.org/wiki/Linear_equation
    a1 = v1y2 - v1y1;
    b1 = v1x1 - v1x2;
    c1 = (v1x2 * v1y1) - (v1x1 * v1y2);

    // Every point (x,y), that solves the equation above, is on the line,
    // every point that does not solve it, is not. The equation will have a
    // positive result if it is on one side of the line and a negative one 
    // if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
    // 2 into the equation above.
    d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
    d2 = (a1 * v2x2) + (b1 * v2y2) + c1;

    // If d1 and d2 both have the same sign, they are both on the same side
    // of our line 1 and in that case no intersection is possible. Careful, 
    // 0 is a special case, that's why we don't test ">=" and "<=", 
    // but "<" and ">".
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // The fact that vector 2 intersected the infinite line 1 above doesn't 
    // mean it also intersects the vector 1. Vector 1 is only a subset of that
    // infinite line 1, so it may have intersected that line before the vector
    // started or after it ended. To know for sure, we have to repeat the
    // the same test the other way round. We start by calculating the 
    // infinite line 2 in linear equation standard form.
    a2 = v2y2 - v2y1;
    b2 = v2x1 - v2x2;
    c2 = (v2x2 * v2y1) - (v2x1 * v2y2);

    // Calculate d1 and d2 again, this time using points of vector 1.
    d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
    d2 = (a2 * v1x2) + (b2 * v1y2) + c2;

    // Again, if both have the same sign (and neither one is 0),
    // no intersection is possible.
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // If we get here, only two possibilities are left. Either the two
    // vectors intersect in exactly one point or they are collinear, which
    // means they intersect in any number of points from zero to infinite.
    if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;

    // If they are not collinear, they must intersect in exactly one point.
    return YES;
}

输入值是向量 1( v1x1/v1y1 和 v1x2/v1y2 )和向量 2( v2x1/v2y1 和 v2x2/v2y2 )的两个端点。所以你有 2 个向量，4 个点，8 个坐标。 YES和 NO很清楚。 YES增加交叉点，NO什么也没做。

COLLINEAR 怎么样？这意味着两个向量位于同一条无限线上，取决于位置和长度，它们根本不相交或相交于无数点。我不确定如何处理这种情况，无论如何我都不会将其视为交叉点。好吧，由于浮点舍入错误，这种情况在实践中很少见；更好的代码可能不会测试 == 0.0f而是像 < epsilon 这样的东西，其中 epsilon 是一个相当小的数字。

如果您需要测试更多的点，您当然可以通过将多边形边的线性方程标准形式保留在内存中来加快整个过程，因此您不必每次都重新计算这些。这将为您在每次测试中节省两个浮点乘法和三个浮点减法，以换取在内存中存储每个多边形边的三个浮点值。这是典型的内存与计算时间的权衡。

最后但并非最不重要的一点:如果您可以使用 3D 硬件来解决问题，那么还有一个有趣的选择。只需让 GPU 为您完成所有工作。创建一个屏幕外的绘画表面。用黑色完全填充它。现在让 OpenGL 或 Direct3D 绘制您的多边形(或者甚至所有多边形，如果您只想测试点是否在其中任何一个内，但您不关心哪个)并用不同的填充多边形颜色，例如白色的。要检查点是否在多边形内，请从绘图表面获取该点的颜色。这只是 O(1) 内存获取。

当然，这种方法仅在您的绘图表面不必很大时才可用。如果它无法放入 GPU 内存，则此方法比在 CPU 上执行要慢。如果它必须很大并且您的 GPU 支持现代着色器，您仍然可以通过将上面显示的光线转换实现为 GPU 着色器来使用 GPU，这绝对是可能的。对于大量多边形或大量要测试的点，这将是值得的，请考虑一些 GPU 将能够并行测试 64 到 256 个点。但是请注意，将数据从 CPU 传输到 GPU 并返回总是很昂贵的，因此仅针对几个简单的多边形测试几个点，其中点或多边形是动态的并且会经常变化，GPU 方法很少支付离开。