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

Question

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

Answer 1

对于图形，我宁愿不要整数。许多系统使用整数进行UI绘制（像素毕竟是ints），但是macOS例如对所有内容都使用float。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!
}

这是任何时候都可以运行的第一个测试。如您所见，此测试非常快，但也很粗糙。要处理边界矩形内的点，我们需要一种更复杂的算法。有几种方法可以计算出来。哪种方法有效还取决于多边形是否可以具有孔或将始终为实体的事实。以下是实心示例（一个凸，一个凹）的示例：

绿色的在中间有一个洞！

可以处理上述所有三种情况并且仍然非常快的最简单算法称为ray cast。该算法的思想非常简单：从多边形外部的任意位置绘制一条虚拟射线到您的点，并计算其撞击多边形一侧的频率。如果命中数是偶数，则在多边形之外，如果是奇数，则在多边形内。

该绕数的算法将是一个另类，它是点非常接近多边形线条更准确，但它也慢得多。由于有限的浮点精度和舍入问题，射线投射可能会因为太靠近多边形边而失败，但实际上这几乎不是问题，就好像一个点靠近边，通常在视觉上甚至不可能查看器以识别它是否已经在内部或仍然在外部。

您还有上方的边框，记得吗？只需在边界框外选择一个点，然后将其用作射线的起点即可。例如，该点(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 polyhtml" target="_blank">gon
} 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（和）和向量2（和）的两个端点。因此，您有2个向量，4个点，8个坐标。而且很清楚。增加十字路口，什么也不做。v1x1/v1y1v1x2/v1y2v2x1/v2y1v2x2/v2y2YESNOYESNO

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

如果需要测试更多的点，则可以通过将多边形边的线性方程标准形式保留在内存中来一定程度地加快整个过程，因此不必每次都重新计算它们。这样可以在每个测试中节省两个浮点乘法和三个浮点减法，以换取在内存中每个多边形边存储三个浮点值。这是典型的内存与计算时间之间的折衷。

最后但并非最不重要的一点：如果您可以使用3D硬件解决问题，则有一个有趣的替代方法。只需让GPU为您完成所有工作即可。创建不在屏幕上的绘画表面。用黑色完全填充它。现在，让OpenGL或Direct3D绘制多边形（如果只想测试该点是否在其中任何一个，但您不在乎哪一个，则可以绘制所有多边形），然后用其他填充多边形颜色，例如白色。要检查点是否在多边形内，请从绘图表面获取该点的颜色。这只是一个O（1）内存提取。

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