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

Question

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

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

score 65 · Accepted Answer

如果我没记错的话，算法是通过你的测试点画一条水平线。计算你相交的多边形有多少线到达你的点。

如果答案很奇怪，你就在里面。如果答案是偶数，你就在外面。

编辑：是的，他说的（维基百科）：

score 41 · Accepted Answer

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

位置类

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

score 15 · Accepted Answer

在网上搜索并尝试了各种实现并将它们从 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

score 5 · Accepted Answer

到目前为止，最好的解释和实现可以在 Point In Polygon Winding Number Inclusion找到

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

我已经修改并使用了 C++ 实现，还创建了一个 C# 实现。您肯定想使用绕组数算法，因为它比边缘交叉算法更准确，而且速度非常快。

score 5 · Accepted Answer

我认为有一个更简单、更有效的解决方案。

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

score 2 · Accepted Answer

asp.Net C#中的完整解决方案，你可以在这里看到完整的细节，你可以看到如何使用纬度和经度找到点（纬度，经度）是在多边形内部还是在多边形外部？文章参考链接

私有静态 bool checkPointExistsInGeofencePolygon（字符串 latlnglist，字符串 lat，字符串 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;
}

score 2 · Accepted Answer

只是一个提示（使用答案，因为我无法评论），如果您想使用多边形中的点进行地理围栏，那么您需要更改您的算法以使用球坐标。-180 经度与 180 经度相同，在这种情况下，多边形中的点会中断。

score 2 · Accepted Answer

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

score 1 · Accepted Answer

我添加一个细节来帮助生活在地球南部的人们！如果您在巴西（这是我的情况），我们的 GPS 坐标都是负面的。所有这些算法都会给出错误的结果。

最简单的方法是使用所有点的 Lat 和 Long 的绝对值。在这种情况下，Jan Kobersky 的算法是完美的。

score 0 · Accepted Answer

如果您有一个简单的多边形（没有一条线交叉）并且没有孔，您也可以对多边形进行三角剖分，无论如何您都可能会在 GIS 应用程序中绘制 TIN，然后测试每个点中的点三角形。如果多边形的边数很少，但点数很多，这很快。

有关三角形中的一个有趣点，请参见链接文本

否则肯定使用缠绕规则而不是边缘交叉，边缘交叉对边缘上的点有实际问题，如果您的数据是从精度有限的 GPS 生成的，则很有可能。

score 0 · Accepted Answer

检查一个点是否在多边形内 -

考虑具有顶点 a1、a2、a3、a4、a5 的多边形。以下一组步骤应有助于确定点 P 是位于多边形内部还是外部。

计算由边 a1->a2 和连接 a2 到 P 和 P 到 a1 的向量形成的三角形的向量面积。类似地，计算每个可能的三角形的矢量面积，其中一个边作为多边形的边，另外两个将 P 连接到该边。

对于一个位于多边形内的点，每个三角形都需要具有正面积。即使其中一个三角形的面积为负，点 P 也会从多边形中脱颖而出。

为了计算三角形的面积，给定代表其 3 条边的向量，请参阅http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

score 0 · Accepted Answer

如果你的多边形是凸的，问题就更容易了。如果是这样，您可以对每条线进行简单的测试，以查看该点是在该线的内部还是外部（在两个方向上都延伸到无穷大）。否则，对于凹多边形，从您的点到无穷远（在任何方向）绘制一条假想的射线。计算它穿过边界线的次数。奇数表示点在里面，偶数表示点在外面。

最后一个算法比看起来更棘手。你必须非常小心当你的假想光线恰好击中多边形的一个顶点时会发生什么。

如果您的假想光线沿 -x 方向行进，您可以选择仅计算包含至少一个 y 坐标严格小于该点的 y 坐标的点的线。这就是让大多数奇怪的边缘情况正常工作的方法。

score 0 · Accepted Answer

多边形被定义为点对 A、B、C .... A. 没有边 AB、BC ... 与任何另一边相交的顺序列表

确定框 Xmin、Xmax、Ymin、Ymax

案例 1 测试点 P 位于框外

案例 2 测试点 P 位于盒子内：

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

确定所有边的梯度 M

找到与所有梯度 M 最不同的梯度 Mt

测试线在梯度 Mt 处从 P 开始，距离 D。

将交叉点的计数设置为零

对于边 AB、BC 中的每一个，测试 PD 与边从其开始到但不包括其结束的交点。如果需要，增加交叉点的计数。请注意，从 P 到交叉点的距离为零表示 P 在一侧

奇数表示 P 在多边形内

score 0 · Accepted Answer

简的回答很棒。

这是使用 GeoCoordinate 类的相同代码。

using System.Device.Location;

...

public static bool IsPointInPolygon(List<GeoCoordinate> poly, GeoCoordinate point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Latitude <= point.Latitude) && (point.Latitude < poly[j].Latitude))
                || ((poly[j].Latitude <= point.Latitude) && (point.Latitude < poly[i].Latitude)))
                && (point.Longitude < (poly[j].Longitude - poly[i].Longitude) * (point.Latitude - poly[i].Latitude)
                    / (poly[j].Latitude - poly[i].Latitude) + poly[i].Longitude))
            c = !c;
    }

    return c;
}

score 0 · Accepted Answer

我在 PHP 中翻译了 c# 方法，并添加了许多注释来理解代码。

PolygonHelps 的描述：
检查一个点是在多边形的内部还是外部。此过程使用 gps 坐标，它适用于多边形的地理区域较小的情况。

输入：
$poly：点数组：多边形顶点列表；[{点}，{点}，...]；
$point：要检查的点；Point: {"lat" => "x.xxx", "lng" => "y.yyy"}

$c 为假时，与多边形的交点数为偶数，所以点在多边形外；
$c 为真时，与多边形的交点数为奇数，所以点在多边形内；
$n 是多边形的顶点数；
对于多边形中的每个顶点，方法计算通过当前顶点和前一个顶点的线，并检查两条线是否有交点。
$c 在交叉点存在时发生变化。
因此，如果点在多边形内，方法可以返回 true，否则返回 false。

class PolygonHelps {

    public static function isPointInPolygon(&$poly, $point){

        $c = false; 
        $n = $j = count($poly);


        for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){

            if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) ) 
                || ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) ) 

            && ( $point->lng <   ( $poly[$j]->lng - $poly[$i]->lng ) 
                               * ( $point->lat    - $poly[$i]->lat ) 
                               / ( $poly[$j]->lat - $poly[$i]->lat ) 
                               +   $poly[$i]->lng ) ){

                $c = !$c;
            }
        }

        return $c;
    }
}

score -1 · Accepted Answer

你可以试试这个简单的类https://github.com/xopbatgh/sb-polygon-pointer

处理它很容易

您只需将多边形坐标插入数组
Ask library 是多边形内的 lat/lng 所需的点

$polygonBox = [
    [55.761515, 37.600375],
    [55.759428, 37.651156],
    [55.737112, 37.649566],
    [55.737649, 37.597301],
];

$sbPolygonEngine = new sbPolygonEngine($polygonBox);

$isCrosses = $sbPolygonEngine->isCrossesWith(55.746768, 37.625605);

// $isCrosses is boolean

（答案是我自己删除的，因为最初格式错误）

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

16 回答 16

Related

Reference