地理围栏 - 指向内部/外部多边形

Question

我想确定一个多边形并实现一个算法,该算法将检查一个点是在多边形内部还是外部.

有谁知道是否有任何类似算法的可用示例？

Answer 1

如果我没记错的话,算法是在测试点绘制一条水平线.计算相交多边形的线数以达到您的点.

如果答案是奇怪的,你就在里面.如果答案是平坦的,那么你就在外面.

编辑:是的,他所说的(维基百科):

Answer 2

C#代码

bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
                || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
                && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
                    / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
        {

            c = !c;
        }
    }

    return c;
}

Loc类

public class Loc
{
    private double lt;
    private double lg;

    public double Lg
    {
        get { return lg; }
        set { lg = value; }
    }

    public double Lt
    {
        get { return lt; }
        set { lt = value; }
    }

    public Loc(double lt, double lg)
    {
        this.lt = lt;
        this.lg = lg;
    }
}

Answer 3

只需看看多边形点(PIP)问题.

Answer 4

在搜索网络并尝试各种实现并将它们从C++移植到C#后,我终于得到了我的代码:

        public static bool PointInPolygon(LatLong p, List<LatLong> poly)
    {
        int n = poly.Count();

        poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
        LatLong[] v = poly.ToArray();

        int wn = 0;    // the winding number counter

        // loop through all edges of the polygon
        for (int i = 0; i < n; i++)
        {   // edge from V[i] to V[i+1]
            if (v[i].Lat <= p.Lat)
            {         // start y <= P.y
                if (v[i + 1].Lat > p.Lat)      // an upward crossing
                    if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                        ++wn;            // have a valid up intersect
            }
            else
            {                       // start y > P.y (no test needed)
                if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                    if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                        --wn;            // have a valid down intersect
            }
        }
        if (wn != 0)
            return true;
        else
            return false;

    }

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
    {
        double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
                - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
        if (calc > 0)
            return 1;
        else if (calc < 0)
            return -1;
        else
            return 0;
    }

isLeft函数给了我舍入问题,我花了好几个小时没有意识到我做错了转换,所以请原谅我在该函数结束时的跛脚if块.

顺便说一句,这是原始代码和文章:http: //softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 5

到目前为止，最好的解释和实现可以在“多边形中的 点缠绕数包含”中找到

在详细解释的文章的末尾甚至还有一个C ++实现。该站点还包含一些其他基于几何的问题的出色算法/解决方案。

我已经修改并使用了C ++实现，还创建了C＃实现。您肯定要使用“缠绕数”算法，因为它比边缘交叉算法更准确且非常快。

Answer 6

我认为有一个更简单,更有效的解决方案.

这是C++中的代码.我应该很简单地将它转换为C#.

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}