logo标签列表

地理围栏 - 在/外多边形内的点

algorithmcomputational-geometry
58

我想确定一个多边形，并实现一个算法来检查一个点是否在多边形内部或外部。

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

16个回答
68
如果我记得正确，算法是通过测试点绘制一条水平线。计算您与达到您的点相交的多边形的线数。
如果答案是奇数，那么您在内部。如果答案是偶数，则您在外部。
编辑：是的，就像Wikipedia所说的那样，如he所说。

alt text

7
谢谢您提供图片以供快速参考，这真的很清晰明了，图文并茂。 - BigBeagle
2
不要忘记处理射线穿过顶点的逻辑。还要确定一个点是否在多边形的边缘上，是内部还是外部。上面的链接提供了更多详细信息。 - htm11h
不幸的是，如果点在多边形的边缘上，这种方法将无法工作。- 这是否意味着有时此算法无法工作？ - Ciaran Gallagher
如果一个点既不在多边形内部也不在外部，那么判断该点是在多边形内部还是外部的算法将无法给出答案。 - Ian Boyd
42

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

位置（Location）类

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;
    }
}
1
只是想提一下，我已经实现并测试了这个功能，看起来它能够正常工作。但我希望作者能够提供一些注释和指示，说明这个算法的具体实现方式。 - RenniePet
7
对于仍然有疑问的人，这显然是偶奇规则算法。 - Alexios
@Alexios，这个算法对于非凸多边形是否可行？ - CAMOBAP
1
我正在将其转换为VBScript。当poly[j].Lt和poly[i].Lt相同时，我会在此处遇到一个除以零的错误 - "/（poly [j] .Lt - poly [i] .Lt）"。 - MrVimes
1
如果您使用的多边形中有任何一条线穿过180度经线，那么该算法将失败。因此，我们需要对每个经度小于0的点加上360度，这样它就能正常工作了！我已经将我们的版本添加为答案。 - Nelly
显示剩余4条评论
16

在搜索网络和尝试不同的实现并将它们从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

6
据我所知没有，但是有经验的PHP程序员应该能够将原始代码转换为PHP。 - Manuel Castro
这个没毛病。我写了xUnit测试来检查上述内容，结果完美无缺。我还提供了一个OOP C#类的重构代码。希望你会觉得有用： https://dev59.com/TKXja4cB1Zd3GeqPLQ5W - Jim Speaker
5
我认为有一个更简单、更高效的解决方案。
以下是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;
}
5
目前最好的解释和实现可以在此找到：点与多边形包含性问题中的绕数法。这篇文章详细解释，并提供了 C++ 实现。该网站还提供了其他基于几何的问题的算法/解决方案。
我修改并使用了 C++ 实现，并创建了 C# 实现。您一定要使用绕数算法，因为它比较准确，而且非常快。
2

这是一个关于asp.Net C#的完整解决方案，你可以在这里查看完整细节。你可以了解如何使用纬度和经度来判断点（lat,lon）是否在多边形内部或外部。

文章参考链接

private static bool checkPointExistsInGeofencePolygon(string latlnglist, string lat, string lng) {

    List<Loc> objList = new List<Loc>();
    // sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|";
    string[] arr = latlnglist.Split('|');
    for (int i = 0; i <= arr.Length - 1; i++)
    {
        string latlng = arr[i];
        string[] arrlatlng = latlng.Split(',');

        Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1]));
        objList.Add(er);
    }
    Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng));

    if (IsPointInPolygon(objList, pt) == true)
    {
          return true;
    }
    else
    {
           return false;
    }
}
private static 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;
}
2

仅提醒一下（由于不能评论，我使用答案），如果您想要在地理围栏中使用点-多边形算法，则需要更改算法以适用于球面坐标系。-180经度与180经度相同，在这种情况下，点-多边形将会失败。

2

关于kobers的回答，我通过更易读的干净代码解决了问题，并更改了跨越日期边界的经度：

public bool IsPointInPolygon(List<PointPosition> polygon, double latitude, double longitude)
{
  bool isInIntersection = false;
  int actualPointIndex = 0;
  int pointIndexBeforeActual = polygon.Count - 1;

  var offset = calculateLonOffsetFromDateLine(polygon);
  longitude = longitude < 0.0 ? longitude + offset : longitude;

  foreach (var actualPointPosition in polygon)
  {
    var p1Lat = actualPointPosition.Latitude;
    var p1Lon = actualPointPosition.Longitude;

    var p0Lat = polygon[pointIndexBeforeActual].Latitude;
    var p0Lon = polygon[pointIndexBeforeActual].Longitude;

    if (p1Lon < 0.0) p1Lon += offset;
    if (p0Lon < 0.0) p0Lon += offset;

    // Jordan curve theorem - odd even rule algorithm
    if (isPointLatitudeBetweenPolyLine(p0Lat, p1Lat, latitude)
    && isPointRightFromPolyLine(p0Lat, p0Lon, p1Lat, p1Lon, latitude, longitude))
    {
      isInIntersection = !isInIntersection;
    }

    pointIndexBeforeActual = actualPointIndex;
    actualPointIndex++;
  }

  return isInIntersection;
}

private double calculateLonOffsetFromDateLine(List<PointPosition> polygon)
{
  double offset = 0.0;
  var maxLonPoly = polygon.Max(x => x.Longitude);
  var minLonPoly = polygon.Min(x => x.Longitude);
  if (Math.Abs(minLonPoly - maxLonPoly) > 180)
  {
    offset = 360.0;
  }

  return offset;
}

private bool isPointLatitudeBetweenPolyLine(double polyLinePoint1Lat, double polyLinePoint2Lat, double poiLat)
{
  return polyLinePoint2Lat <= poiLat && poiLat < polyLinePoint1Lat || polyLinePoint1Lat <= poiLat && poiLat < polyLinePoint2Lat;
}

private bool isPointRightFromPolyLine(double polyLinePoint1Lat, double polyLinePoint1Lon, double polyLinePoint2Lat, double polyLinePoint2Lon, double poiLat, double poiLon)
{
  // lon <(lon1-lon2)*(latp-lat2)/(lat1-lat2)+lon2
  return poiLon < (polyLinePoint1Lon - polyLinePoint2Lon) * (poiLat - polyLinePoint2Lat) / (polyLinePoint1Lat - polyLinePoint2Lat) + polyLinePoint2Lon;
}
1
我添加一个细节来帮助居住在南半球的人们！！如果你在巴西（这是我的情况），我们的GPS坐标都是负数。而所有这些算法给出的结果都是错误的。
最简单的方法是使用所有点的纬度和经度的绝对值。在这种情况下，Jan Kobersky的算法是完美的。
0

多边形被定义为点对A、B、C……A的顺序列表。 没有边A-B、B-C……与其他边相交

确定框Xmin、Xmax、Ymin、Ymax

情况1 测试点P在框外

情况2 测试点P在框内：

确定框的“直径”D{[Xmin，Ymin] - [Xmax，Ymax]}（并添加一些额外的内容以避免可能与D在一侧混淆）

确定所有边的梯度M

找到一个梯度Mt，它与所有梯度M最不同

测试线从P开始，以Mt梯度和距离D运行。

将交点计数设置为零

对于每个边A-B、B-C，测试P-D与其起点到但不包括其终点的边的交点。如有必要，增加交点计数。请注意，从P到交点的零距离表示P在一条边上

奇数计数表示P在多边形内

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接