我试图创建的快速的点多边形算法里面，在使用命中测试（例如 Polygon.contains（号码：点））。

I'm trying to create a fast point inside polygon algorithm, for use in hit-testing (e.g. Polygon.contains(p:Point)).

推荐答案

对于图形，我从来没有去为整数。许多操作系统使用整数绘画UI（像素整数毕竟），但Mac OS X中的示例使用浮动的一切（点它的谈判。有一点可以转化为一个像素，但根据显示器分辨率，它可能会转换成任何东西其他人，但一个像素，如果分辨率非常高的显示器，理论上一个像素可以转化为半分，让1.5 / 1.5可以是一个不同的像素比1/1和2/2）。不过，我从来没有注意到Mac的用户界面比其他的UI显著慢。毕竟3D（OpenGL或Direct3D的）也与时间彩车所有的现代图形库很可能会往往利用系统的高功率GPU的没有你甚至没有注意到它（为GPU也可以加速的2D绘图，而不仅仅是三维; 2D是三维的一个子集，考虑2D到3D是其中在Z坐标总是0例如）

For graphics, I'd never go with Integers. Many OSes use Integers for painting UI (pixels are ints after all), but Mac OS X for example uses float for everything (it talks of points. A point can translate to one pixel, but depending on monitor resolution, it might translate to anything else but a pixel and if resolution is very high of a monitor, in theory a pixel can translate to half a point, so 1.5/1.5 can be a different pixel than 1/1 and 2/2). However, I never noticed that Mac UIs are significantly slower than other UIs. After all 3D (OpenGL or Direct3D) also works with floats all of the time and modern graphics libraries might very often take advantage of high power GPUs of a system without you even noticing it (as a GPU can also speed up 2D painting, not just 3D; 2D is only a subset of 3D, consider 2D to be 3D where the Z coordinates are always 0 for example).

现在你说速度是你的主要关注，好吧，让我们去的速度。在运行任何复杂的算法，首先做一个简单的测试。创建一个在你的多边形轴排列的包围盒。这是非常简单，快速，已经可以安全你吨的CPU时间。这是如何工作的？遍历多边形的所有点（每点为X / Y），发现X和YEG的最大/最小值你具有点（9/1），（4/3），（2/7），（8/2），（3/6）。 XMIN是2，Xmax的是9，YMIN是1，YMAX为7。现在你知道你的多边形中没有一点都不能比2比9斧头值小和更大的，没有一点可以比1比y值小和更大的7.这样，您就可以迅速排除多少分不是你的多边形中：

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 safe you tons of CPU time. How does that work? Iterate over all points of the polygon (every point being X/Y) and find the min/max values of X and Y. E.g. you have the points (9/1), (4/3), (2/7), (8/2), (3/6). Xmin is 2, Xmax is 9, Ymin is 1 and Ymax is 7. Now you know that no point within your polygon can ever have a x value smaller than 2 and greater than 9, no point can have a y value smaller than 1 and greater than 7. This way you can quickly exclude many points not being within your 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 on any point. If this test already excludes the point from the polygon (even though it's a very coarse test!), then there is no use of running any other tests. As you can see, this test is ultra fast.

如果此测试将不会排除点，它是轴对齐包围盒内，但是，这并不意味着它是面内;它只是意味着它可能是多边形内。我们所需要的下一个是一个更复杂的测试，以检查是否该点是真的内的多边形或者仅仅边界框之内。有几种方法如何可以计算出来。这也使得一个巨大的差异是多边形可以有洞，还是它的固体。下面是实的人的例子（一个凸起，一个凹）：

If this test won't exclude the point, it is within the axis aligned bounding box, but that does not mean it is within the polygon; it only means it might be within the polygon. What we need next is a more sophisticated test to check if the point is really within the polygon or just within the bounding box. There are a couple of ways how this can be calculated. It also makes a huge difference is the polygon can have holes or whether its solid. Here are examples of solid ones (one convex, one concave):

和这里有一个有孔：

绿色的一个人在中间有一个洞！

The green one has a hole in the middle!

最简单的方法就是使用光线投射，因为它可以处理上述所有正确显示的多边形，没有特殊的处理是必要的，它仍然提供了不错的速度。该算法的思想是pretty的简单：从任何地方画一个虚拟的射线多边形，以你的观点之外，怎么算往往碰到多边形的任何一方。如果命中数是偶数，它的多边形之外，如果是奇数，它的内部。

The easiest way is to use ray casting, since it can handle all the polygons shown above correctly, no special handling is necessary and it still provides good speed. 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 any side of the polygon. If the number of hits is even, it's outside of the polygon, if it's odd, it's inside.

卷数算法更准确点是非常，非常，非常接近一个多边形线;光线投射可能会失败，因为浮precision和舍入问题在这里，但是卷绕数是慢得多，如果一个点被意外检测为多边形的外如果它是如此接近的多边形线，即你的眼睛不能即使知道它是内部还是外部，是不是真的有问题？我不这么认为，所以让我们让事情变得简单。

The winding number algorithm is more accurate for points being very, very, very close to a polygon line; ray casting may fail here because of float precision and rounding issues, however winding number is much slower and if a point is accidentally detected to be outside of the polygon if it's so close to a polygon line, that your eye can't even tell if it's inside or outside, is it really a problem? I don't think so, so let's keep things simple.

您仍然有上面的边框，还记得吗？好了，现在让我们假设你的意思是对试（PX / PY）。您的射线可能会去从

You still have the bounding box of above, remember? Okay, now let's say your point is p again (p.x/p.y). Your ray might go from

这并不重要。选择自己最好的给你听。该射线绝对开始多边形之外，并停止在该点它是唯一重要的

It won't matter. Choose whatever sounds best to you. It's only important that the ray starts definitely outside of the polygon and stops at the point.

那么什么是电子呢？那么，E（实际上小量）给出了边框部分的填充的。正如我所说的，光线追踪，如果我们开始太接近多边形线路出现故障。因为边界框可能等于多边形（如果多边形是实际的轴线对齐的矩形，边界框等于多边形本身！和射线将直接开始对多边形侧）。你应该如何大的选择e？不要太大。这取决于你使用的绘图坐标系的规模。你可以选择e是1.0，但是，如果你的多边形有坐标比1.0小很多，选择E要为0.001可能是足够大的。你可以选择e是始终为1％的多边形大小，例如对具有沿x轴线时，你可以计算出这样的E：

So what is e anyway? 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 actually an axis aligned rectangle, the bounding box is equal to the polygon itself! And the ray would start directly on the polygon side). How big should you choose e? Not too big. It depends on the coordinate system scale you use for drawing. You could select e to be 1.0, however, if your polygons have coordinates much smaller than 1.0, selecting e to be 0.001 might be large enough. You could select e to be always 1% of the polygon size, e.g. when having a ray along the x axis, you could calculate e like this:

e = ((Xmax - Xmin) / 100)

现在，我们已经与它的起点和终点坐标的光线，这个问题从转移是多边形内的点到多久相交线多边形边。为此，我们不能只用多边形点的工作和以前一样（的边框），现在我们需要实际的两侧。 A面总是由两个点来定义。

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 intersects the ray a polygon side". Therefor we can't just work with the polygon points as before (for the bounding box), 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).

// 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 code（未测试），这应该做的伎俩：

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 either above or below the line.
    // 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;

    // We repeat everything above for vector 2.
    // We start by calculating line 2 in linear equation standard form.
    a2 = v2y2 - v2y1;
    b2 = v2x1 - v2x2;
    c2 = (v2x2 * v2y1) - (v2x1 * v2y2);

    // Calulate 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 three possibilities are left. Either the two
    // vectors intersect in exactly one point or they are collinear
    // (they both lie both on the same infinite line), in which case they
    // may intersect in an infinite number of points or not at all.
    if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;

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

的输入值是在两个端点的载体1（x和y）和矢量2（x和y）的。所以，你有2个向量，4个，8个坐标。 YES和NO是明确的。 YES增大交叉口，NO什么都不做。怎么样共线？这意味着两种载体位于同一无限线，这取决于位置和长度，它们不相交于所有或它们在点的无尽数量相交。我不完全知道如何处理这种情况下，我不会指望它路口两种方式。那么，这种情况下是由于浮点舍入误差相当罕见的做法无论如何; ;更好的code可能不会对 = = 0.0 而是这样的事情＆LT测试小量，其中小量是一个相当小的数字（这样较小的舍入错误不会导致错误的结果）。

The input values are the two endpoints of vector 1 (x and y) and vector 2 (x and y). So you have 2 vectors, 4 points, 8 coordinates. YES and NO are clear. YES increases intersections, NO does nothing. 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 (so smaller rounding mistakes won't lead to wrong results).

最后但并非最不重要的：如果你可以用3D硬件来解决问题，忘记任何事情上面。有更快和更容易的方式。只是让GPU做所有的工作适合你。创建一个绘画表面，关闭屏幕（这样你就可以画到它，没有它出现在屏幕上的任何地方）。完全用颜色填充黑色。现在让OpenGL或Direct3D的画你的多边形（甚至所有的多边形，如果你只是想测试，如果该点内的任何人，但你不关心哪一个）到这个绘图表面和填充多边形（S ）用不同的颜色，例如白色。检查点是否在多边形内，拿到这一点从图形表面的颜色。这仅仅是一个O（1）存储器中获取。如果它是白色的，它的里面，如果是黑色的，它的外面。很简单，不是吗？如果你有非常小的多边形此方法将还清（例如50-100），但该死的很多点测试（> 1000），在这种情况下，这个方法比什么都快得多。它只会是一个问题，如果你的绘图表面必须是巨大的，因为你的多边形。如果您的绘图表面需要100 MB或更多，使多边形契合，这种方法可能会变得非常慢（尽管它浪费吨内存的事实）。

Last but not least: If you may use 3D hardware to solve the problem, forget about anything above. There is a much faster and much easier way. Just let the GPU do all the work for you. Create a painting surface that is off screen (so you can paint into it, without it appearing anywhere on the 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) into this drawing surface 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. If it's white, it's inside, if it's black, it's outside. Easy, isn't it? This method will pay off if you have very little polygons (e.g. 50-100), but a damn lot of points to test (> 1000), in which case this method is much speedier than anything else. It will only be a problem if your drawing surface must be huge because your polygons are. If your drawing surface needs to be 100 MB or more to make the polygons fit, this method might become very slow (despite the fact that it wastes tons of memory).