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

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

位置类

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

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

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

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

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

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

Answer 6

asp.Net C# 中的完整解决方案，您可以在此处查看完整的详细信息，您可以了解如何使用纬度和经度查找点（lat，lon）无论是在多边形内部还是外部？
文章参考链接

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

Answer 7

请注意（使用答案，因为我无法发表评论），如果您想使用多边形内的点进行地理围栏，那么您需要更改算法以使用球坐标。 -180 经度与 180 经度相同，在这种情况下，多边形内的点将被破坏。

Answer 8

关于科伯斯的回答，我用更易读的干净代码解决了这个问题，并更改了跨越日期边界的经度：

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

Answer 9

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

最简单的方法是使用所有点的纬度和经度的绝对值。 在这种情况下，扬·科伯斯基的算法是完美的。

Answer 10

检查点是否在多边形内部 -

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

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

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

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

Answer 11

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

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

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

Answer 12

如果您有一个简单的多边形（没有任何线交叉）并且没有孔，您也可以对多边形进行三角测量，您可能会在 GIS 应用程序中执行此操作来绘制 TIN，然后测试每个多边形中的点三角形。 如果多边形的边数较少但点数较多，则速度很快。

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

否则肯定使用缠绕规则与边缘交叉相比，边缘交叉对于边缘上的点确实存在问题，如果您的数据是从精度有限的 GPS 生成的，则很可能会出现这种问题。

Answer 13

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

确定框 Xmin、Xmax、Ymin、Ymax

情况 1 测试点 P 位于框外 情况

2 测试点 P 位于框内：

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

确定所有边的梯度 M

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

测试线从 P 以梯度 Mt 延伸距离 D。

将交点计数设置为零

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

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

Answer 14

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

PolygonHelps 的说明：
检查点是在多边形内部还是外部。 此过程使用 GPS 坐标，当多边形具有较小的地理区域时，它可以工作。

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

当 $c 为 false 时，与多边形交点的个数为偶数，因此该点在多边形之外；
当 $c 为 true 时，与多边形交点的数量为奇数，因此该点在多边形内部；< br>$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;
    }
}

Answer 15

Jan 的回答非常棒。

下面是使用 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;
}

Answer 16

您可以尝试这个简单的类 https://github.com/xopbatgh/sb-polygon-pointer< /a>

处理起来很容易

1. 你只需将多边形坐标插入数组中
2. 询问库是否需要多边形内有纬度/经度的点

$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

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