确定坐标是否存在于多边形内部

Question

我正在开发一个开源跟踪和地理围栏软件应用程序，但在计算地理围栏的数学时遇到了一些困难。

我需要确定多边形内部是否存在坐标。然而，棘手的部分是多边形没有固定的边数。我需要能够计算五十面或五面。

我的研究表明，最简单的方法是采用我的点（我将其称为 x）和多边形外部的点（称为 y）并确定线 ((xx, xy), (yx, yy)) 是否与多边形的边界。如果相交奇数次，则点 x 必须在多边形内部。

然而，我知道如何在算法中表达这一点。显然，我需要遍历构建多边形的各种线条，但我所做的检查却无法实现。有人可以帮忙吗？请知道我不一定要求解决方案。任何能帮助我找出答案的事情都是巨大的帮助。

非常感谢。

Answer 1

请参阅此处基本上

有一种方法（我认为它是乔丹曲线定理）可以计算射线与构成多边形的线段相交的次数。如果结果是偶数，则该点位于多边形外部，否则该点位于多边形内部。

HTH

编辑
还有另一个与此问题相关的问题可以找到 这里

Answer 2

这里的关键是要意识到您可以自由选择您喜欢的任何 Y 点。一个非常好的选择是点 (xx, -infinity)。换句话说，该点是从所讨论的点直接向下且无限远的点。现在的问题是：有多少多边形边与相关点下方的 X 坐标相交。因此只需要考虑跨越 X 坐标的线段。

如果点为 P = (x,y)，线段端点为 P1 = (x1,y1) 且 P2 = (x2,y2)，则与 x 相交的线段的 y 坐标由下式给出： sy = (x- x1)*(y2-y1)/(x2-x1) + y1

检查是否 sy < y（仅当 x1 < x < x2 或 x2 < x < x1 时）。如果其中有奇数个，则 P 位于内部。

当多边形的一个顶点与相关点的 y 位置完全相同时，就会出现一些微妙的问题。对于这种情况你必须要小心。

Answer 3

贾斯汀，

您可能还需要更好地定义“多边形外部”来构造线段。

采取分钟和;所有 x 和 的最大值y 坐标并构造一个矩形 (xmin,ymin),(xmax,ymin),(xmax,ymax),(xmin,ymax)。矩形之外的任何点肯定都会在多边形之外 - 然后继续，如上面其他人所示。每个多边形线段和构造的线由方程 y = ax + b 以及每个线段的范围 xlo 和 xhi 定义。您构造的线要么穿过范围内的线段，要么不穿过。即两个联立方程在段范围内的解要么存在，要么不存在。只需计算存在的解决方案的数量即可获得交叉点的数量。

Answer 4

我假设你在飞机上（2D）。

• 计算每条边的斜率（在某些坐标系中）以及从 X 点到 Y 点的直线（XY 线）的斜率。
• 对于斜率不等于 XY 斜率的所有边，计算交点。
• 对于每个点，确定交点是否在线段 XY 和定义边的线段上。如果是的话，你就跨过了那一边。 （检查交叉点的坐标，看看 x 和 y 分量是否都包含在每个线段的值范围内。）
• 计算交叉点的数量，您就会得到答案。

Answer 5

计算多边形和点的绕数。

Answer 6

试试这个，

public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }