如何确定二维点是否在多边形内?

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.

我正在尝试在多边形算法中创建一个快速的2D点，用于hit-testing(例如Polygon.contains(p: point))。对有效技术的建议将受到赞赏。

30 个解决方案

#1

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 works with floats and modern graphics libraries very often take advantage of GPU acceleration.

对于图形，我不喜欢整数。许多系统使用整数进行UI绘制(像素毕竟是ints)，但是macOS则使用浮点数。macOS只知道点和点可以转换成一个像素，但是根据监视器的分辨率，它可能转换成其他东西。在视网膜屏幕上，半点(0.5/0.5)是像素。尽管如此，我从未注意到macOS ui要比其他ui慢得多。在所有3D api (OpenGL或Direct3D)之后，也可以使用浮点数和现代图形库，它们经常利用GPU加速。

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 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.

现在你说速度是你最关心的，好吧，我们开始讲速度。在运行任何复杂的算法之前，首先做一个简单的测试。在多边形周围创建一个轴对齐的边框。这是非常简单，快速和安全的计算你已经很多。这是如何工作的呢?遍历多边形的所有点，找到X和Y的最小值/最大值。

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.

如你有点(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 coordif (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 the fact if the polygon can have holes or will always be solid. Here are examples of solid ones (one convex, one concave):

这是第一次运行任何点的测试。正如你所看到的，这个测试速度非常快，但也非常粗糙。要处理边界矩形内的点，我们需要更复杂的算法。有几种方法可以计算。哪种方法有效还取决于多边形是否可以有孔或永远是固体。这里有一些实的例子(一个凸，一个凹):

And here's one with a hole:

这里有一个洞:

The green one has a hole in the middle!

绿色的在中间有一个洞!

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.

最简单的算法，它可以处理以上三种情况，并且仍然非常快的命名为ray casting。算法的思想非常简单:从多边形以外的任何地方绘制一条虚拟光线到你的点，并计算它到达多边形一侧的频率。如果命中的次数是偶数，它在多边形的外面，如果它是奇数，它在里面。

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.

圈数算法是另一种选择，它对于非常接近多边形线的点更准确，但它也慢得多。雷铸件可能失败点一个多边形边太近,因为有限的浮点精度和舍入的问题,但在现实中这不是一个问题,好像一点谎言接近,通常观众视觉上不可能承认如果它已经内部还是外部。

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.

你还有上面的边框，记得吗?只要在边界框外选择一个点，并将它作为射线的起点。点(Xmin - e/p.y)一定在多边形外面。

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)

但e是什么?e(实际上)给了边界框一些填充。正如我所说，如果我们太靠近多边形线，射线追踪就会失败。由于边界框可能等于多边形(如果多边形是一个轴对齐的矩形，那么边界框就等于多边形本身!)你应该选择e?不是太大。这取决于你绘制时使用的坐标系标度。如果像素步长为1.0，那么选择1.0(不过0.1也可以)

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 sidesint 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}

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:

到目前为止还好，但是如果两个向量相交怎么办?这里有一些C代码(未经过测试)，应该可以实现这个功能:

#define NO 0#define YES 1#define COLLINEAR 2int 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;}

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.

输入值是向量1 (v1x1/v1y1和v1x2/v1y2)和向量2 (v2x1/v2y1和v2x2/v2y2)的两个端点。有两个向量，4个点，8个坐标。“是”和“否”都很清楚。是的增加了交叉口，不做任何事。

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.

共线的呢?这意味着两个向量都在同一条无穷线上，取决于位置和长度，它们根本不会相交，或者它们相交于无数个点。我不太确定如何处理这种情况，我不认为它是交叉的。由于浮点舍入误差，这种情况在实践中非常罕见;更好的代码可能不会对== 0.0f进行测试，而是对类似 <的东西进行测试，其中的是一个相当小的数字。< p>

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.

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

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.

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

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.

当然，这个方法只有在您的绘图表面不需要很大时才可用。如果不能装入GPU内存，则此方法比在CPU上执行要慢。如果它必须是巨大的并且你的GPU支持现代的着色，你仍然可以使用GPU来实现上面显示的作为GPU着色器的光线投射，这绝对是可能的。对于更多的多边形或大量的点来测试，这将会得到回报，考虑到一些gpu可以同时测试64到256个点。但是，请注意，将数据从CPU传输到GPU和返回GPU总是很昂贵的，因此，对于仅针对几个简单的多边形(在这些多边形中，点或多边形都是动态的，并且会经常发生变化)测试几个点，GPU方法几乎不会奏效。

#2

I think the following piece of code is the best solution (taken from here):

我认为下面这段代码是最好的解决方案(从这里开始):

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy){  int i, j, c = 0;  for (i = 0, j = nvert-1; i < nvert; j = i++) {    if ( ((verty[i]>testy) != (verty[j]>testy)) &&     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )       c = !c;  }  return c;}

Arguments

• nvert: Number of vertices in the polygon. Whether to repeat the first vertex at the end has been discussed in the article referred above.
• nvert:多边形中顶点的数量。是否在最后重复第一个顶点已经在上面提到的文章中讨论过。
• vertx, verty: Arrays containing the x- and y-coordinates of the polygon's vertices.
• vertx, verty:包含多边形顶点的x和y坐标的数组。
• testx, testy: X- and y-coordinate of the test point.
• testx, testy:测试点的X和y坐标。

It's both short and efficient and works both for convex and concave polygons. As suggested before, you should check the bounding rectangle first and treat polygon holes separately.

它既短又有效，适用于凸多边形和凹多边形。如前所述，您应该首先检查边界矩形并分别处理多边形孔。

The idea behind this is pretty simple. The author describes it as follows:

这背后的想法很简单。作者描述如下:

I run a semi-infinite ray horizontally (increasing x, fixed y) out from the test point, and count how many edges it crosses. At each crossing, the ray switches between inside and outside. This is called the Jordan curve theorem.

我从测试点水平运行一条半无限射线(增加x，固定y)，并计算它穿过多少条边。在每个十字路口，光线在内外之间切换。这叫做约当曲线定理。

The variable c is switching from 0 to 1 and 1 to 0 each time the horizontal ray crosses any edge. So basically it's keeping track of whether the number of edges crossed are even or odd. 0 means even and 1 means odd.

变量c在每次水平射线穿过任何边时都从0到1，从1到0。所以基本上它是在跟踪交叉的边的数量是偶数还是奇数。0表示偶数，1表示奇数。

#3

Here is a C# version of the answer given by nirg, which comes from this RPI professor. Note that use of the code from that RPI source requires attribution.

这是nirg给出的答案的c#版本，来自RPI教授。注意，使用RPI源代码中的代码需要使用属性。

A bounding box check has been added at the top. However, as James Brown points out, the main code is almost as fast as the bounding box check itself, so the bounding box check can actually slow the overall operation, in the case that most of the points you are checking are inside the bounding box. So you could leave the bounding box check out, or an alternative would be to precompute the bounding boxes of your polygons if they don't change shape too often.

在顶部添加了一个边框复选框。但是，正如James Brown所指出的，主代码几乎和边界框本身一样快，因此边界框检查实际上可以减慢整个操作，如果您正在检查的大多数点都在边界框中。所以你可以退出边界框，或者另一种选择是，如果你的多边形的边界框不经常改变的话，你可以预先计算它们的边界框。

public bool IsPointInPolygon( Point p, Point[] polygon ){    double minX = polygon[ 0 ].X;    double maxX = polygon[ 0 ].X;    double minY = polygon[ 0 ].Y;    double maxY = polygon[ 0 ].Y;    for ( int i = 1 ; i < polygon.Length ; i++ )    {        Point q = polygon[ i ];        minX = Math.Min( q.X, minX );        maxX = Math.Max( q.X, maxX );        minY = Math.Min( q.Y, minY );        maxY = Math.Max( q.Y, maxY );    }    if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )    {        return false;    }    // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html    bool inside = false;    for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )    {        if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&             p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )        {            inside = !inside;        }    }    return inside;}

#4

Here is a JavaScript variant of the answer by M. Katz based on Nirg's approach:

根据Nirg的方法，M. Katz给出了一个JavaScript版本的答案:

function pointIsInPoly(p, polygon) {    var isInside = false;    var minX = polygon[0].x, maxX = polygon[0].x;    var minY = polygon[0].y, maxY = polygon[0].y;    for (var n = 1; n < polygon.length; n++) {        var q = polygon[n];        minX = Math.min(q.x, minX);        maxX = Math.max(q.x, maxX);        minY = Math.min(q.y, minY);        maxY = Math.max(q.y, maxY);    }    if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {        return false;    }    var i = 0, j = polygon.length - 1;    for (i, j; i < polygon.length; j = i++) {        if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&                p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {            isInside = !isInside;        }    }    return isInside;}

#5

Compute the oriented sum of angles between the point p and each of the polygon apices. If the total oriented angle is 360 degrees, the point is inside. If the total is 0, the point is outside.

计算点p和每个多边形顶点之间的角度之和。如果总的角度是360度，那么这个点在里面。如果总数是0，那么点在外面。

I like this method better because it is more robust and less dependent on numerical precision.

我更喜欢这种方法，因为它更健壮，更不依赖于数值精度。

Methods that compute evenness of number of intersections are limited because you can 'hit' an apex during the computation of the number of intersections.

计算交叉口数目均匀性的方法是有限的，因为你可以在计算交叉口数目的过程中“击中”顶点。

EDIT: By The Way, this method works with concave and convex polygons.

编辑:顺便说一下，这种方法适用于凹多边形和凸多边形。

EDIT: I recently found a whole Wikipedia article on the topic.

编辑:我最近在*上找到了一篇关于这个话题的文章。

#6

The Eric Haines article cited by bobobobo is really excellent. Particularly interesting are the tables comparing performance of the algorithms; the angle summation method is really bad compared to the others. Also interesting is that optimisations like using a lookup grid to further subdivide the polygon into "in" and "out" sectors can make the test incredibly fast even on polygons with > 1000 sides.

bobobobobo引用的Eric Haines的文章真是太棒了。特别有趣的是比较算法性能的表格;与其它方法相比，角度总和法是很差的。同样有趣的是，优化方法，比如使用查找网格将多边形进一步细分为“in”和“out”扇区，即使是在有> 1000条边的多边形上，也可以使测试非常快速。

Anyway, it's early days but my vote goes to the "crossings" method, which is pretty much what Mecki describes I think. However I found it most succintly described and codified by David Bourke. I love that there is no real trigonometry required, and it works for convex and concave, and it performs reasonably well as the number of sides increases.

不管怎么说，现在还处于初期阶段，但我的投票是通过“十字路口”的方式进行的，我想这差不多就是Mecki所描述的。然而，我发现大卫·布尔克对它的描述和编纂最为成功。我喜欢不需要真正的三角函数，它适用于凸和凹，而且随着边数的增加，它表现得相当好。

By the way, here's one of the performance tables from the Eric Haines' article for interest, testing on random polygons.

顺便说一下，这是Eric Haines的文章中的一个性能表，用于测试随机的多边形。

                       number of edges per polygon                         3       4      10      100    1000MacMartin               2.9     3.2     5.9     50.6    485Crossings               3.1     3.4     6.8     60.0    624Triangle Fan+edge sort  1.1     1.8     6.5     77.6    787Triangle Fan            1.2     2.1     7.3     85.4    865Barycentric             2.1     3.8    13.8    160.7   1665Angle Summation        56.2    70.4   153.6   1403.8  14693Grid (100x100)          1.5     1.5     1.6      2.1      9.8Grid (20x20)            1.7     1.7     1.9      5.7     42.2Bins (100)              1.8     1.9     2.7     15.1    117Bins (20)               2.1     2.2     3.7     26.3    278

#7

This question is so interesting. I have another workable idea different from other answers of this post.

这个问题很有趣。我有另一个与这篇文章的其他答案不同的可行的想法。

The idea is to use the sum of angles to decide whether the target is inside or outside. If the target is inside an area, the sum of angle form by the target and every two border points will be 360. If the target is outside, the sum will not be 360. The angle has direction. If the angle going backward, the angle is a negative one. This is just like calculating the winding number.

这个想法是用角度的和来决定目标是在里面还是在外面。如果目标在一个区域内，则目标与每两个边界点的角度之和为360。如果目标在外面，那么总数不会是360。角的方向。如果这个角向后，这个角是负的。这就像计算圈数一样。

Refer to this image to get a basic understanding of the idea:

参考这张图片，对这个想法有一个基本的了解:

My algorithm assumes the clockwise is the positive direction. Here is a potential input:

我的算法假设顺时针是正方向。这里有一个潜在的输入:

[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]

The following is the python code that implements the idea:

下面是实现这个想法的python代码:

def isInside(self, border, target):degree = 0for i in range(len(border) - 1):    a = border[i]    b = border[i + 1]    # calculate distance of vector    A = getDistance(a[0], a[1], b[0], b[1]);    B = getDistance(target[0], target[1], a[0], a[1])    C = getDistance(target[0], target[1], b[0], b[1])    # calculate direction of vector    ta_x = a[0] - target[0]    ta_y = a[1] - target[1]    tb_x = b[0] - target[0]    tb_y = b[1] - target[1]    cross = tb_y * ta_x - tb_x * ta_y    clockwise = cross < 0    # calculate sum of angles    if(clockwise):        degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))    else:        degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))if(abs(round(degree) - 360) <= 3):    return Truereturn False

#8

I did some work on this back when I was a researcher under Michael Stonebraker - you know, the professor who came up with Ingres, PostgreSQL, etc.

我做过一些研究当我是迈克尔·斯通布莱克的研究员，他提出了Ingres, PostgreSQL等等。

We realized that the fastest way was to first do a bounding box because it's SUPER fast. If it's outside the bounding box, it's outside. Otherwise, you do the harder work...

我们意识到最快的方法是先做一个边界框，因为它超级快。如果它在边框之外，它就在外边。否则，你会做更辛苦的工作……

If you want a great algorithm, look to the open source project PostgreSQL source code for the geo work...

如果您想要一个伟大的算法，请查看开放源码项目PostgreSQL的geo源代码…

I want to point out, we never got any insight into right vs left handedness (also expressible as an "inside" vs "outside" problem...

我想指出的是，我们从来没有深入研究过右利手和左利手(也可以用“内”和“外”来表示……

---

UPDATE

更新

BKB's link provided a good number of reasonable algorithms. I was working on Earth Science problems and therefore needed a solution that works in latitude/longitude, and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area? The answer is that the "direction" of the verticies matters - it's either left-handed or right handed and in this way you can indicate either area as "inside" any given polygon. As such, my work used solution three enumerated on that page.

BKB的链接提供了大量合理的算法。我正在研究地球科学问题，因此需要一个在纬度/经度上工作的解决方案，它有一个独特的“利手”问题——是小区域内的面积还是大区域内的面积?答案是，垂直的“方向”很重要——它要么是左手的，要么是右手的，这样你就可以将任何一个区域表示为任何给定的多边形的“内部”。因此，我的工作使用了该页上列举的解决方案3。

In addition, my work used separate functions for "on the line" tests.

此外，我的工作在“在线”测试中使用了单独的函数。

...Since someone asked: we figured out that bounding box tests were best when the number of verticies went beyond some number - do a very quick test before doing the longer test if necessary... A bounding box is created by simply taking the largest x, smallest x, largest y and smallest y and putting them together to make four points of a box...

…既然有人问:我们发现当垂直的数量超过某个数字时，边界框测试是最好的——在必要的情况下进行更长的测试之前，做一个非常快速的测试……简单地取最大的x、最小的x、最大的y和最小的y，把它们放在一起，就可以得到一个方框的四个点……

Another tip for those that follow: we did all our more sophisticated and "light-dimming" computing in a grid space all in positive points on a plane and then re-projected back into "real" longitude/latitude, thus avoiding possible errors of wrapping around when one crossed line 180 of longitude and when handling polar regions. Worked great!

另一个技巧对于那些遵循:我们做了所有我们的更复杂的和“light-dimming”计算网格空间中所有积极点在飞机上然后re-projected回“真实”经度/纬度,从而避免可能的错误的包装当一个交叉的第180行经度和在处理极地。工作好了!

#9

Really like the solution posted by Nirg and edited by bobobobo. I just made it javascript friendly and a little more legible for my use:

真的很喜欢Nirg发布的和bobobobobo编辑的解决方案。我只是使它更友好的javascript和更清晰的使用:

function insidePoly(poly, pointx, pointy) {    var i, j;    var inside = false;    for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {        if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;    }    return inside;}

#10

Swift version of the answer by nirg:

nirg的快速版本:

extension CGPoint {    func isInsidePolygon(vertices: [CGPoint]) -> Bool {        guard !vertices.isEmpty else { return false }        var j = vertices.last!, c = false        for i in vertices {            let a = (i.y > y) != (j.y > y)            let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x)            if a && b { c = !c }            j = i        }        return c    }}

#11

David Segond's answer is pretty much the standard general answer, and Richard T's is the most common optimization, though therre are some others. Other strong optimizations are based on less general solutions. For example if you are going to check the same polygon with lots of points, triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms. Another is if the polygon and points are on a limited plane at low resolution, say a screen display, you can paint the polygon onto a memory mapped display buffer in a given colour, and check the color of a given pixel to see if it lies in the polygons.

David Segond的答案几乎是标准的一般答案，Richard T的答案是最常见的优化，尽管还有其他一些。其他强大的优化基于不那么通用的解决方案。举个例子，如果你要检查同一个有很多点的多边形，三角形化这个多边形可以大大提高速度因为有很多快速搜索算法。另一种方法是，如果多边形和点在一个低分辨率的有限平面上，比如屏幕显示，你可以用给定的颜色将多边形绘制到内存映射的显示缓冲区上，然后检查给定像素的颜色，看看它是否位于多边形中。

Like many optimizations, these are based on specific rather than general cases, and yield beneifits based on amortized time rather than single usage.

与许多优化一样，这些优化基于特定的而不是一般的情况，并基于平摊时间而不是单个使用来生成beneifits。

Working in this field, i found Joeseph O'Rourkes 'Computation Geometry in C' ISBN 0-521-44034-3 to be a great help.

在这个领域工作，我发现Joeseph O' rourkes在C' ISBN 0-521-44034-3中的计算几何对我很有帮助。

#12

The trivial solution would be to divide the polygon to triangles and hit test the triangles as explained here

最简单的解决方案是将多边形分割成三角形，然后点击这里所介绍的三角形测试

If your polygon is CONVEX there might be a better approach though. Look at the polygon as a collection of infinite lines. Each line dividing space into two. for every point it's easy to say if its on the one side or the other side of the line. If a point is on the same side of all lines then it is inside the polygon.

如果你的多边形是凸的，也许有更好的方法。把多边形看成是无限线的集合。每条线把空间分成两部分。对于每一点，我们都很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一边，那么它就在多边形内。

#13

I realize this is old, but here is a ray casting algorithm implemented in Cocoa, in case anyone is interested. Not sure it is the most efficient way to do things, but it may help someone out.

我知道这已经过时了，但这里有一个用Cocoa实现的射线投射算法，以防有人感兴趣。不确定这是最有效的做事方式，但它可能会帮助某人。

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point{    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];    BOOL result;    float aggregateX = 0; //I use these to calculate the centroid of the shape    float aggregateY = 0;    NSPoint firstPoint[1];    [currentPath elementAtIndex:0 associatedPoints:firstPoint];    float olderX = firstPoint[0].x;    float olderY = firstPoint[0].y;    NSPoint interPoint;    int noOfIntersections = 0;    for (int n = 0; n < [currentPath elementCount]; n++) {        NSPoint points[1];        [currentPath elementAtIndex:n associatedPoints:points];        aggregateX += points[0].x;        aggregateY += points[0].y;    }    for (int n = 0; n < [currentPath elementCount]; n++) {        NSPoint points[1];        [currentPath elementAtIndex:n associatedPoints:points];        //line equations in Ax + By = C form        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;          float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);        float _A_BAR = olderY - points[0].y;        float _B_BAR = points[0].x - olderX;        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);        if (det != 0) {            //intersection points with the edges            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);            if (olderX <= points[0].x) {                //doesn't matter in which direction the ray goes, so I send it right-ward.                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {                      noOfIntersections++;                }            } else {                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {                     noOfIntersections++;                }             }        }        olderX = points[0].x;        olderY = points[0].y;    }    if (noOfIntersections % 2 == 0) {        result = FALSE;    } else {        result = TRUE;    }    return result;}

#14

Obj-C version of nirg's answer with sample method for testing points. Nirg's answer worked well for me.

目的- c版本的nirg的答案与样本方法的测试点。Nirg的回答对我来说很有效。

- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test {    NSUInteger nvert = [vertices count];    NSInteger i, j, c = 0;    CGPoint verti, vertj;    for (i = 0, j = nvert-1; i < nvert; j = i++) {        verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue];        vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue];        if (( (verti.y > test.y) != (vertj.y > test.y) ) &&        ( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) )            c = !c;    }    return (c ? YES : NO);}- (void)testPoint {    NSArray *polygonVertices = [NSArray arrayWithObjects:        [NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)],        [NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)],        [NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)],        [NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)],        [NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)],        [NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)],        nil    ];    CGPoint tappedPoint = CGPointMake(23.0, 70.0);    if ([self isPointInPolygon:polygonVertices point:tappedPoint]) {        NSLog(@"YES");    } else {        NSLog(@"NO");    }}

#15

I too thought 360 summing only worked for convex polygons but this isn't true.

我也认为360求和只适用于凸多边形但这不是真的。

This site has a nice diagram showing exactly this, and a good explanation on hit testing:Gamasutra - Crashing into the New Year: Collision Detection

这个网站有一个很好的图表，正好显示了这一点，并给出了一个很好的解释:Gamasutra——在新的一年里会崩溃:碰撞检测。

#16

C# version of nirg's answer is here: I'll just share the code. It may save someone some time.

c#版本的nirg的答案是:我只共享代码。这可能会节省一些时间。

public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) {            bool result = false;            int j = polygon.Count() - 1;            for (int i = 0; i < polygon.Count(); i++) {                if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) {                    if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) {                        result = !result;                    }                }                j = i;            }            return result;        }

#17

Java Version:

Java版本:

public class Geocode {    private float latitude;    private float longitude;    public Geocode() {    }    public Geocode(float latitude, float longitude) {        this.latitude = latitude;        this.longitude = longitude;    }    public float getLatitude() {        return latitude;    }    public void setLatitude(float latitude) {        this.latitude = latitude;    }    public float getLongitude() {        return longitude;    }    public void setLongitude(float longitude) {        this.longitude = longitude;    }}public class GeoPolygon {    private ArrayList<Geocode> points;    public GeoPolygon() {        this.points = new ArrayList<Geocode>();    }    public GeoPolygon(ArrayList<Geocode> points) {        this.points = points;    }    public GeoPolygon add(Geocode geo) {        points.add(geo);        return this;    }    public boolean inside(Geocode geo) {        int i, j;        boolean c = false;        for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {            if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&                    (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))                c = !c;        }        return c;    }}

#18

.Net port:

net端口:

    static void Main(string[] args)    {        Console.Write("Hola");        List<double> vertx = new List<double>();        List<double> verty = new List<double>();        int i, j, c = 0;        vertx.Add(1);        vertx.Add(2);        vertx.Add(1);        vertx.Add(4);        vertx.Add(4);        vertx.Add(1);        verty.Add(1);        verty.Add(2);        verty.Add(4);        verty.Add(4);        verty.Add(1);        verty.Add(1);        int nvert = 6;  //Vértices del poligono        double testx = 2;        double testy = 5;        for (i = 0, j = nvert - 1; i < nvert; j = i++)        {            if (((verty[i] > testy) != (verty[j] > testy)) &&             (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]))                c = 1;        }    }

#19

There is nothing more beutiful than an inductive definition of a problem. For the sake of completeness here you have a version in prolog which might also clarify the thoughs behind ray casting:

没有什么比问题的归纳定义更有用的了。为了完整起见，这里有一个prolog的版本，它也可以澄清ray casting背后的想法:

Based on the simulation of simplicity algorithm in http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

基于http://www.ecse.rpi.edu/主页/ wrf/research/short_notes/pnpoly.html中简单算法的模拟

Some helper predicates:

一些辅助谓词:

exor(A,B):- \+A,B;A,\+B.in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).inside(false).inside(_,[_|[]]).inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) +      X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).get_line(_,_,[]).get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).

The equation of a line given 2 points A and B (Line(A,B)) is:

给定两点a和B的直线方程(直线(a,B))为:

                    (YB-YA)           Y - YA = ------- * (X - XA)                     (XB-YB) 

It is important that the direction of rotation for the line issetted to clock-wise for boundaries and anti-clock-wise for holes.We are going to check whether the point (X,Y), i.e the tested point is at the lefthalf-plane of our line (it is a matter of taste, it could also bethe right side, but also the direction of boundaries lines has to be changed inthat case), this is to project the ray from the point to the right (or left)and acknowledge the intersection with the line. We have chosen to projectthe ray in the horizontal direction (again it is a matter of taste,it could also be done in vertical with similar restrictions), so we have:

重要的是，将直线的旋转方向设置为沿时钟方向的边界，并将反时钟方向设置为孔。我们要检查点(X,Y) i。e lefthalf-plane的测试点是直线(这是一个味道,这也可能是右边,而且界限线的方向必须改变inthat),这是项目的雷点向右(或左)和承认的交叉线。我们选择在水平方向上投射光线(这也是一个味道问题，它也可以在垂直方向上以类似的限制进行)，所以我们有:

               (XB-XA)           X < ------- * (Y - YA) + XA               (YB-YA) 

Now we need to know if the point is at the left (or right) side ofthe line segment only, not the entire plane, so we need to restrict the search only to this segment, but this is easy sinceto be inside the segment only one point in the line can be higherthan Y in the vertical axis. As this is a stronger restriction itneeds to be the first to check, so we take first only those linesmeeting this requirement and then check its possition. By the JordanCurve theorem any ray projected to a polygon must intersect at aneven number of lines. So we are done, we will throw the ray to theright and then everytime it intersects a line, toggle its state.However in our implementation we are goint to check the lenght ofthe bag of solutions meeting the given restrictions and decide theinnership upon it. for each line in the polygon this have to be done.

现在我们需要知道点在线段的左(或右),而不是整个飞机,所以我们需要限制搜索只有这部分,但这很容易sinceto是段内只有一个点的线可以高于Y在垂直轴。由于这是一个更严格的限制，它需要首先检查，所以我们只取那些符合要求的行，然后检查它的可能性。根据JordanCurve定理，任何投射到多边形上的射线都必须在偶数条直线上相交。我们做完了，我们把射线放到那里然后每次它与一条线相交时，切换它的状态。然而，在我们的实施过程中，我们将检查符合规定限制的一揽子解决方案是否正确，并对此作出决定。对于多边形中的每条线，都必须这样做。

is_left_half_plane(_,[],[],_).is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] =  [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA));                                                         is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon),  in_range(Y,YA,YB).all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line),    in_y_range_at_poly(Coordinate,Line,Polygon), Lines).traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).% This is the entry point predicateinside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).

#20

VBA VERSION:

VBA版本:

Note: Remember that if your polygon is an area within a map that Latitude/Longitude are Y/X values as opposed to X/Y (Latitude = Y, Longitude = X) due to from what I understand are historical implications from way back when Longitude was not a measurement.

注意:请记住，如果你的多边形是地图上的一个区域，那么纬度/经度是Y/X值，而不是X/Y值(纬度= Y，经度= X)，因为根据我的理解，从历史意义上来说，经度不是一个度量。

CLASS MODULE: CPoint

类模块:CPoint

Private pXValue As DoublePrivate pYValue As Double'''''X Value Property'''''Public Property Get X() As Double    X = pXValueEnd PropertyPublic Property Let X(Value As Double)    pXValue = ValueEnd Property'''''Y Value Property'''''Public Property Get Y() As Double    Y = pYValueEnd PropertyPublic Property Let Y(Value As Double)    pYValue = ValueEnd Property

MODULE:

模块:

Public Function isPointInPolygon(p As CPoint, polygon() As CPoint) As Boolean    Dim i As Integer    Dim j As Integer    Dim q As Object    Dim minX As Double    Dim maxX As Double    Dim minY As Double    Dim maxY As Double    minX = polygon(0).X    maxX = polygon(0).X    minY = polygon(0).Y    maxY = polygon(0).Y    For i = 1 To UBound(polygon)        Set q = polygon(i)        minX = vbMin(q.X, minX)        maxX = vbMax(q.X, maxX)        minY = vbMin(q.Y, minY)        maxY = vbMax(q.Y, maxY)    Next i    If p.X < minX Or p.X > maxX Or p.Y < minY Or p.Y > maxY Then        isPointInPolygon = False        Exit Function    End If    ' SOURCE: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html    isPointInPolygon = False    i = 0    j = UBound(polygon)    Do While i < UBound(polygon) + 1        If (polygon(i).Y > p.Y) Then            If (polygon(j).Y < p.Y) Then                If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then                    isPointInPolygon = True                    Exit Function                End If            End If        ElseIf (polygon(i).Y < p.Y) Then            If (polygon(j).Y > p.Y) Then                If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then                    isPointInPolygon = True                    Exit Function                End If            End If        End If        j = i        i = i + 1    Loop   End FunctionFunction vbMax(n1, n2) As Double    vbMax = IIf(n1 > n2, n1, n2)End FunctionFunction vbMin(n1, n2) As Double    vbMin = IIf(n1 > n2, n2, n1)End FunctionSub TestPointInPolygon()    Dim i As Integer    Dim InPolygon As Boolean'   MARKER Object    Dim p As CPoint    Set p = New CPoint    p.X = <ENTER X VALUE HERE>    p.Y = <ENTER Y VALUE HERE>'   POLYGON OBJECT    Dim polygon() As CPoint    ReDim polygon(<ENTER VALUE HERE>) 'Amount of vertices in polygon - 1    For i = 0 To <ENTER VALUE HERE> 'Same value as above       Set polygon(i) = New CPoint       polygon(i).X = <ASSIGN X VALUE HERE> 'Source a list of values that can be looped through       polgyon(i).Y = <ASSIGN Y VALUE HERE> 'Source a list of values that can be looped through    Next i    InPolygon = isPointInPolygon(p, polygon)    MsgBox InPolygonEnd Sub

#21

Heres a point in polygon test in C that isn't using ray-casting. And it can work for overlapping areas (self intersections), see the use_holes argument.

在C的多边形测试中，没有使用射线铸造。它可以用于重叠区域(自交点)，参见use_holes参数。

/* math lib (defined below) */static float dot_v2v2(const float a[2], const float b[2]);static float angle_signed_v2v2(const float v1[2], const float v2[2]);static void copy_v2_v2(float r[2], const float a[2]);/* intersection function */bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,                         const bool use_holes){    /* we do the angle rule, define that all added angles should be about zero or (2 * PI) */    float angletot = 0.0;    float fp1[2], fp2[2];    unsigned int i;    const float *p1, *p2;    p1 = verts[nr - 1];    /* first vector */    fp1[0] = p1[0] - pt[0];    fp1[1] = p1[1] - pt[1];    for (i = 0; i < nr; i++) {        p2 = verts[i];        /* second vector */        fp2[0] = p2[0] - pt[0];        fp2[1] = p2[1] - pt[1];        /* dot and angle and cross */        angletot += angle_signed_v2v2(fp1, fp2);        /* circulate */        copy_v2_v2(fp1, fp2);        p1 = p2;    }    angletot = fabsf(angletot);    if (use_holes) {        const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);        angletot -= nested * (float)(M_PI * 2.0);        return (angletot > 4.0f) != ((int)nested % 2);    }    else {        return (angletot > 4.0f);    }}/* math lib */static float dot_v2v2(const float a[2], const float b[2]){    return a[0] * b[0] + a[1] * b[1];}static float angle_signed_v2v2(const float v1[2], const float v2[2]){    const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);    return atan2f(perp_dot, dot_v2v2(v1, v2));}static void copy_v2_v2(float r[2], const float a[2]){    r[0] = a[0];    r[1] = a[1];}

Note: this is one of the less optimal methods since it includes a lot of calls to atan2f, but it may be of interest to developers reading this thread (in my tests its ~23x slower then using the line intersection method).

注意:这是一种不太理想的方法，因为它包含很多对atan2f的调用，但是对于正在阅读这个线程的开发人员来说，这可能会很有趣(在我的测试中，它的速度比使用线交方法慢了~23x)。

#22

For Detecting hit on Polygon we need to test two things:

要检测多边形上的命中，我们需要测试两件事:

1. If Point is inside polygon area. (can be accomplished by Ray-Casting Algorithm)
2. 如果点在多边形区域内。(可通过射线投射算法实现)
3. If Point is on the polygon border(can be accomplished by same algorithm which is used for point detection on polyline(line)).
4. 如果点在多边形边界上(可以使用同一算法完成，该算法用于多边形(线)上的点检测)。

#23

To deal with the following special cases in Ray casting algorithm:

针对射线铸造算法中的以下特殊情况:

1. The ray overlaps one of the polygon's side.
2. 光线与多边形的一侧重叠。
3. The point is inside of the polygon and the ray passes through a vertex of the polygon.
4. 点在多边形的内部，光线通过多边形的一个顶点。
5. The point is outside of the polygon and the ray just touches one of the polygon's angle.
6. 点在多边形的外面光线只接触到多边形的一个角。

Check Determining Whether A Point Is Inside A Complex Polygon. The article provides an easy way to resolve them so there will be no special treatment required for the above cases.

检查确定一个点是否在一个复杂的多边形中。本文提供了一种简单的方法来解决这些问题，因此不需要对上述情况进行特殊处理。

#24

You can do this by checking if the area formed by connecting the desired point to the vertices of your polygon matches the area of the polygon itself.

您可以通过检查将所需点连接到多边形顶点所形成的区域是否与多边形本身的区域相匹配来实现这一点。

Or you could check if the sum of the inner angles from your point to each pair of two consecutive polygon vertices to your check point sums to 360, but I have the feeling that the first option is quicker because it doesn't involve divisions nor calculations of inverse of trigonometric functions.

或者你可以检查的和内心的角度从你连续两个多边形的每一对顶点指向你的支票金额到360点,但我有感觉,第一个选项是更快,因为它不涉及部门和计算三角函数的逆。

I don't know what happens if your polygon has a hole inside it but it seems to me that the main idea can be adapted to this situation

我不知道如果你的多边形里面有一个洞会发生什么，但是在我看来，主要的想法是可以适应这种情况的

You can as well post the question in a math community. I bet they have one million ways of doing that

你也可以把这个问题放到一个数学社区里。我打赌他们有一百万种方法

#25

If you are looking for a java-script library there's a javascript google maps v3 extension for the Polygon class to detect whether or not a point resides within it.

如果您正在寻找java-script库，则有一个javascript谷歌映射多边形类v3扩展，用于检测其中是否存在一个点。

var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3);var isWithinPolygon = polygon.containsLatLng(40, -90);

Google Extention Github

谷歌延伸Github

#26

When using qt (Qt 4.3+), one can use QPolygon's function containsPoint

当使用qt (qt 4.3+)时，可以使用QPolygon的函数containsPoint

#27

The answer depends on if you have the simple or complex polygons. Simple polygons must not have any line segment intersections. So they can have the holes but lines can't cross each other. Complex regions can have the line intersections - so they can have the overlapping regions, or regions that touch each other just by a single point.

答案取决于你是否有简单或复杂的多边形。简单多边形必须没有任何线段相交。所以它们可以有洞但是线不能相交。复杂的区域可以有直线交叉点——因此它们可以有重叠的区域，或者仅仅通过一个点互相接触的区域。

For simple polygons the best algorithm is Ray casting (Crossing number) algorithm. For complex polygons, this algorithm doesn't detect points that are inside the overlapping regions. So for complex polygons you have to use Winding number algorithm.

对于简单的多边形，最好的算法是射线投射(交叉数)算法。对于复杂多边形，该算法不检测重叠区域内的点。所以对于复多边形你必须使用圈数算法。

Here is an excellent article with C implementation of both algorithms. I tried them and they work well.

这里有一篇优秀的文章，介绍了两种算法的C实现。我试过了，效果很好。

http://geomalgorithms.com/a03-_inclusion.html

http://geomalgorithms.com/a03-_inclusion.html

#28

Scala version of solution by nirg (assumes bounding rectangle pre-check is done separately):

nirg的Scala版本解决方案(假设边界矩形预先检查是分开进行的):

def inside(p: Point, polygon: Array[Point], bounds: Bounds): Boolean = {  val length = polygon.length  @tailrec  def oddIntersections(i: Int, j: Int, tracker: Boolean): Boolean = {    if (i == length)      tracker    else {      val intersects = (polygon(i).y > p.y) != (polygon(j).y > p.y) && p.x < (polygon(j).x - polygon(i).x) * (p.y - polygon(i).y) / (polygon(j).y - polygon(i).y) + polygon(i).x      oddIntersections(i + 1, i, if (intersects) !tracker else tracker)    }  }  oddIntersections(0, length - 1, tracker = false)}

#29

I've made a Python implementation of nirg's c++ code:

我已经完成了nirg的c++代码的Python实现:

Inputs

输入

• bounding_points: nodes that make up the polygon.
• bounding_points:组成多边形的节点。

• bounding_box_positions: candidate points to filter. (In my implementation created from the bounding box.

  bounding_box_positions:候选点用于筛选。(在我的实现中，从边界框中创建。

  (The inputs are lists of tuples in the format: [(xcord, ycord), ...])

  (输入是格式为[(xcord, ycord)，…]的元组列表)。

Returns

返回

• All the points that are inside the polygon.
• 所有的点都在多边形中。

def polygon_ray_casting(self, bounding_points, bounding_box_positions):    # Arrays containing the x- and y-coordinates of the polygon's vertices.    vertx = [point[0] for point in bounding_points]    verty = [point[1] for point in bounding_points]    # Number of vertices in the polygon    nvert = len(bounding_points)    # Points that are inside    points_inside = []    # For every candidate position within the bounding box    for idx, pos in enumerate(bounding_box_positions):        testx, testy = (pos[0], pos[1])        c = 0        for i in range(0, nvert):            j = i - 1 if i != 0 else nvert - 1            if( ((verty[i] > testy ) != (verty[j] > testy))   and                    (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):                c += 1        # If odd, that means that we are inside the polygon        if c % 2 == 1:             points_inside.append(pos)    return points_inside

Again, the idea is taken from here

同样，这个想法是从这里开始的。

#30

This only works for convex shapes, but Minkowski Portal Refinement, and GJK are also great options for testing if a point is in a polygon. You use minkowski subtraction to subtract the point from the polygon, then run those algorithms to see if the polygon contains the origin.

这只适用于凸形，但是Minkowski Portal细化，并且GJK也是测试一个点是否在多边形中的很好的选择。用闵可夫斯基减法从多边形中减去点，然后运行这些算法，看看这个多边形是否包含原点。

Also, interestingly, you can describe your shapes a bit more implicitly using support functions which take a direction vector as input and spit out the farthest point along that vector. This allows you to describe any convex shape.. curved, made out of polygons, or mixed. You can also do operations to combine the results of simple support functions to make more complex shapes.

同样，有趣的是，你可以用支持函数来更含蓄地描述你的形状，它以一个方向向量作为输入，然后沿着那个向量吐出最远的点。这允许你描述任何凸形。弯曲的，由多边形构成的，或混合的。您还可以进行操作，将简单的支持函数的结果组合在一起，以生成更复杂的形状。

More info:http://xenocollide.snethen.com/mpr2d.html

更多信息:http://xenocollide.snethen.com/mpr2d.html。

Also, game programming gems 7 talks about how to do this in 3d (:

此外，游戏编程gems 7讨论如何在3d中实现这一点(