8

我正在开发一个开源跟踪和地理围栏软件应用程序，并且在弄清楚地理围栏的数学方面有点困难。

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

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

然而，知道这一点，我无法弄清楚如何在算法中表达这一点。我显然需要遍历构造多边形的各种线，但我所做的检查却让我望而却步。任何人都可以提供帮助吗？请知道我不一定要求解决方案。任何能帮助我找出答案的东西都是巨大的帮助。

非常感激。

4

6 回答 6

6

看这里

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

高温高压

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

于 2010-01-13T20:43:38.003 回答
1

贾斯汀，

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

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

于 2010-01-15T22:52:31.430 回答
1

这里的一个关键是要意识到你可以自由选择你喜欢的任何 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 位置时，就会出现一些微妙的问题。你必须小心这种情况。

于 2010-01-13T20:58:56.240 回答
0

计算多边形和点的缠绕数。

于 2010-01-13T20:44:20.247 回答
0

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

  • 计算每边的斜率（在某个坐标系中）和从点 X 到点 Y 的线的斜率（线 XY）。
  • 对于斜率不等于 XY 斜率的所有边，计算交点。
  • 对于每个点，确定交点是否在线段 XY 和定义边的线段上。如果是，你越过了那一边。（检查交点的坐标，看看 x 和 y 分量是否都包含在每条线段的值范围内。）
  • 数一数穿越的次数，你就有答案了。
于 2010-01-13T19:44:30.187 回答
0

尝试这个，

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;
    }
于 2011-11-20T21:21:59.247 回答