对于图形，我宁愿不喜欢整数。许多系统使用整数进行 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）给边界框一些padding。正如我所说，如果我们开始离多边形线太近，光线追踪就会失败。由于边界框可能等于多边形（如果多边形是轴对齐的矩形，则边界框等于多边形本身！），我们需要一些填充以确保安全，仅此而已。你应该选择多大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 (和) 和向量 2 (和) 的两个端点。所以你有 2 个向量，4 个点，8 个坐标。并且很清楚。增加交叉点，什么都不做。v1x1/v1y1``v1x2/v1y2``v2x1/v2y1``v2x2/v2y2``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 方法很少会支付离开。