如何确定 2D 点是否在多边形内? [英] How can I determine whether a 2D Point is within a Polygon?

问题描述

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

I'm trying to create a fast 2D point inside polygon algorithm, for use in hit-testing (e.g. Polygon.contains(p:Point)). Suggestions for effective techniques would be appreciated.

推荐答案

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

For graphics, I'd rather not prefer integers. Many systems use integers for UI painting (pixels are ints after all), but macOS, for example, uses float for everything. macOS only knows points and a point can translate to one pixel, but depending on monitor resolution, it might translate to something else. On retina screens half a point (0.5/0.5) is pixel. Still, I never noticed that macOS UIs are significantly slower than other UIs. After all, 3D APIs (OpenGL or Direct3D) also work with floats and modern graphics libraries very often take advantage of GPU acceleration.

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

Now you said speed is your main concern, okay, let's go for speed. Before you run any sophisticated algorithm, first do a simple test. Create an axis aligned bounding box around your polygon. This is very easy, fast and can already save you a lot of calculations. How does that work? Iterate over all points of the polygon and find the min/max values of X and Y.

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

E.g. you have the points (9/1), (4/3), (2/7), (8/2), (3/6). This means Xmin is 2, Xmax is 9, Ymin is 1 and Ymax is 7. A point outside of the rectangle with the two edges (2/1) and (9/7) cannot be within the polygon.

// 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!
}

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

This is the first test to run for any point. As you can see, this test is ultra fast but it's also very coarse. To handle points that are within the bounding rectangle, we need a more sophisticated algorithm. There are a couple of ways how this can be calculated. Which method works also depends on whether the polygon can have holes or will always be solid. Here are examples of solid ones (one convex, one concave):

这是一个有洞的:

绿色的中间有个洞！

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

The easiest algorithm, that can handle all three cases above and is still pretty fast is named ray casting. The idea of the algorithm is pretty simple: Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon. If the number of hits is even, it's outside of the polygon, if it's odd, it's inside.

绕数算法将是一种替代方法，它对于非常接近多边形线的点更准确，但速度也慢得多.由于有限的浮点精度和四舍五入问题，光线投射对于太靠近多边形边的点可能会失败，但实际上这几乎不是问题，就好像一个点离边那么近，通常在视觉上甚至不可能以识别它是已经在里面还是还在外面.

The winding number algorithm would be an alternative, it is more accurate for points being very close to a polygon line but it's also much slower. Ray casting may fail for points too close to a polygon side because of limited floating point precision and rounding issues, but in reality that is hardly a problem, as if a point lies that close to a side, it's often visually not even possible for a viewer to recognize if it is already inside or still outside.

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

You still have the bounding box of above, remember? Just pick a point outside the bounding box and use it as starting point for your ray. E.g. the point (Xmin - e/p.y) is outside the polygon for sure.

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

But what is e? Well, e (actually epsilon) gives the bounding box some padding. As I said, ray tracing fails if we start too close to a polygon line. Since the bounding box might equal the polygon (if the polygon is an axis aligned rectangle, the bounding box is equal to the polygon itself!), we need some padding to make this safe, that's all. How big should you choose e? Not too big. It depends on the coordinate system scale you use for drawing. If your pixel step width is 1.0, then just choose 1.0 (yet 0.1 would have worked as well)

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

Now that we have the ray with its start and end coordinates, the problem shifts from "is the point within the polygon" to "how often does the ray intersects a polygon side". Therefore we can't just work with the polygon points as before, now we need the actual sides. A side is always defined by two points.

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

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

You need to test the ray against all sides. Consider the ray to be a vector and every side to be a vector. The ray has to hit each side exactly once or never at all. It can't hit the same side twice. Two lines in 2D space will always intersect exactly once, unless they are parallel, in which case they never intersect. However since vectors have a limited length, two vectors might not be parallel and still never intersect because they are too short to ever meet each other.

// 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 代码(未测试)，应该可以解决问题:

So far so well, but how do you test if two vectors intersect? Here's some C code (not tested), that should do the trick:

#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 什么都不做.

The input values are the two endpoints of vector 1 (v1x1/v1y1 and v1x2/v1y2) and vector 2 (v2x1/v2y1 and v2x2/v2y2). So you have 2 vectors, 4 points, 8 coordinates. YES and NO are clear. YES increases intersections, NO does nothing.

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

What about COLLINEAR? It means both vectors lie on the same infinite line, depending on position and length, they don't intersect at all or they intersect in an endless number of points. I'm not absolutely sure how to handle this case, I would not count it as intersection either way. Well, this case is rather rare in practice anyway because of floating point rounding errors; better code would probably not test for == 0.0f but instead for something like < epsilon, where epsilon is a rather small number.

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

If you need to test a larger number of points, you can certainly speed up the whole thing a bit by keeping the linear equation standard forms of the polygon sides in memory, so you don't have to recalculate these every time. This will save you two floating point multiplications and three floating point subtractions on every test in exchange for storing three floating point values per polygon side in memory. It's a typical memory vs computation time trade off.

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

Last but not least: If you may use 3D hardware to solve the problem, there is an interesting alternative. Just let the GPU do all the work for you. Create a painting surface that is off screen. Fill it completely with the color black. Now let OpenGL or Direct3D paint your polygon (or even all of your polygons if you just want to test if the point is within any of them, but you don't care for which one) and fill the polygon(s) with a different color, e.g. white. To check if a point is within the polygon, get the color of this point from the drawing surface. This is just a O(1) memory fetch.

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

Of course this method is only usable if your drawing surface doesn't have to be huge. If it cannot fit into the GPU memory, this method is slower than doing it on the CPU. If it would have to be huge and your GPU supports modern shaders, you can still use the GPU by implementing the ray casting shown above as a GPU shader, which absolutely is possible. For a larger number of polygons or a large number of points to test, this will pay off, consider some GPUs will be able to test 64 to 256 points in parallel. Note however that transferring data from CPU to GPU and back is always expensive, so for just testing a couple of points against a couple of simple polygons, where either the points or the polygons are dynamic and will change frequently, a GPU approach will rarely pay off.

这篇关于如何确定 2D 点是否在多边形内?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！