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

Question

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

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

Answer 1

只要看看该点在多边形（PIP）问题。

Answer 2

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

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

编辑：是啊，什么 他 说 （维基百科):

Answer 3

<强> 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 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功能是给我取整的问题，我花了几个小时，而没有意识到我在做转换错误，所以请原谅我的瘸腿，如果块中的该函数的结束。

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

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

到目前为止，最好的解释和执行可以在发现 点在多边形卷绕圈数夹杂

甚至有一个C ++在井的端解释执行制品。这个网站还包含了一些伟大的算法/解决方案等基于几何问题。

我已经修改和所使用的C ++实现，并且还创建了一个C＃实现。你一定要使用的卷绕圈数的算法，因为它是比边缘交叉算法更准确，这是非常快的。

Answer 7

刚抬起头（使用的答案，我不能评论），如果你想用点在多边形的地理围栏，那么你需要改变你的算法与球面坐标的工作。 -180经度是相同的180的经度和点在多边形将在这样的情况下断裂。

Answer 8

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

私有静态布尔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 9

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

考虑具有顶点 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 10

问题是容易，如果您的多边形是凸的。如果是这样，你可以做一个简单的测试，每一行，看是否点位于内或行外（在两个方向延伸到无穷大）。否则，对于凹多边形，绘制从您的点的假想射线出到无穷大（在任何方向）。数一数有多少次越过边界线。奇指点是内部，甚至是指该点之外。

这最后的算法是麻烦比它的外观。你必须非常小心，当你的虚拟光线正好击中多边形的顶点之一会发生什么。

如果您的虚拟光线进入-x方向，你只能选择计算行包括至少一个点，其y坐标严格小于在y你少点的坐标。这是你如何得到最怪异的边缘的情况下才能正常工作。

Answer 11

如果你有一个简单的多边形（没有线的交叉），你不要有破洞，你也可以三角多边形，你很可能会在GIS应用反正做画一个三角，然后测试分中的每个三角形。如果你有一个边缘数少的多边形，而是由大量的点这是快速的。

有关在三角形中的一个有趣的观点看链接文本

否则肯定使用缠绕规则，而不是边缘交叉，边缘交叉对边缘与分真实问题，其中如果产生数据形成具有有限精度一个GPS很可能。

Answer 12

多边形被定义为点对的顺序列表A，B，C .... A. 无侧A-B，B-C ...跨越任何其他侧

确定框Xmin时，的Xmax，YMIN，YMAX

1的情况下的测试点P位于外箱

2的情况下的测试点P位于内盒：

确定框的 '直径' d {[Xmin时，YMIN] - [的Xmax，YMAX]}（并添加一些额外的，以避免与d是在侧可能的混淆）

确定梯度m该边的

查找梯度从山所有梯度中号

最不同

在测试线与P在梯度运行山的距离d。

设置交叉点的计为零

有关各边A-B，B-C测试用于P-d的有侧的交点的 从自身做起，直到但不包括其结束。增加交叉口的次数 如果需要的话。注意，从P到交叉点的距离零表示P是ON的侧

这是奇计数表示P是多边形内部

Answer 13

我在Php翻译C＃方法和我添加许多意见理解代码搜索结果PolygonHelps的描述：结果 检查点是内部或外部的多边形。此过程使用GPS坐标和多边形的时候有一个小的地理区域它的作品。搜索结果 结果输入：点击$聚：点阵列：多边形顶点列表; [{点}，{}点，...]点击$点：点检查;点：{ “LAT”=> “x.xxx”， “LNG”=> “y.yyy”}
中国 当$ c为假，与多边形交叉点的数目是偶数，所以点是多边形的外部;结果，当$ c为真，与多边形交叉点的数目是奇数，所以点是多边形的内部; < 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 14

我想补充一个细节，以帮助谁住在地球...南部人！ 如果您是在巴西（这是我的情况），我们的GPS坐标均为阴性。 而所有这些算法中给出错误的结果。

如果使用纬度和所有点的长的绝对值的最简单方法。而在这种情况下，扬Kobersky的算法中是完美的。

Answer 15

扬的回答是巨大的。

下面是使用会有地理座标类，而不是相同的代码。

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

对付它很容易

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

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