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

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

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

如果我没记错的话，算法是在测试点上画一条水平线。计算您要相交的多边形的几条线。

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

编辑：是的，他说了什么(维基百科)：

• 感谢您收录图片以便快速参考。它真的说明了一切。
• 如果射线穿过顶点，不要忘记要处理的逻辑。并确定一个点是否在边上，它是在多边形内还是在多边形外。上面的链接提供了更多详细信息。
• "不幸的是，如果该点位于多边形的边缘，则此方法将无效。" -这是否意味着该算法有时无法工作？
• @CiaranGallagher如果点既不在多边形内部也不在多边形外部，则该点在多边形内部还是外部的答案的算法将无法回答您。

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

• 只需提及我已经实现并测试了它，它似乎就可以了。只希望作者提供了一些评论并指出了该算法实现的算法。
• 对于仍然想知道的人，这显然是奇偶规则算法。
• 我在C＃中使用WGS84坐标测试了上面的代码，它似乎也对我有用！谢谢
• @Alexios，此算法可用于非凸多边形吗？
• 我将其转换为vbscript。当poly [j] .Lt和poly [i] .Lt相同时，我得到零除错误-" /(poly [j] .Lt-poly [i] .Lt)"。
• ... Ive通过检测相等性并将一个值加上0.0000001来粗略地解决了我的被零除问题，但是我想知道Im是否在做被零除的情况时做错了什么。这仅意味着两个点具有相同的纬度，这是完全可行的。
• 完美地工作。谢谢一群！
• @MrVimes前两个&&条件通过将poly [i] .Lt和poly [j] .Lt相比较，以将它们与point.Lt进行比较来间接确定其相等。不确定VBScript，但这意味着在C＃中，它永远不会达到被零除的情况。
• 如果您使用的多边形在180度经度上越过日期线，则此算法将失败。因此，我们将所有经度添加到<0 +360度，然后效果很好！我也添加了我们的版本作为答案。

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

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

• 并不是我所知道的，但是任何经验丰富的PHP程序员都应该能够将原始代码移植到PHP
• 这是钱。我围绕上述内容编写了xUnit测试，它可以完美地签出。我还提供了上述代码的重构作为OOP C＃类。希望对您有所帮助：stackoverflow.com/questions/46144205/

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

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

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

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

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

只是要抬头(使用我无法评论的答案)，如果您想使用多边形多边形围栏，则需要更改算法以使用球面坐标。 -180经度与180经度相同，在这种情况下多边形折断。

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

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

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

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

多边形定义为点对A，B，C .... A的顺序列表。
没有侧面A-B，B-C ...越过另一面

确定方框Xmin，Xmax，Ymin，Ymax

情况1，测试点P位于盒子外面 短码网=DuanMa.NET

情况2，测试点P位于盒子内：

确定框{[Xmin，Ymin]-[Xmax，Ymax]}的"直径" D(并添加一些额外的值以避免D放在一边而造成混淆)

确定各边的梯度M

查找与所有渐变M最不同的渐变Mt

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

将交叉点数设置为零

对于侧面A-B，B-C，测试P-D与侧面的交点
从开始到结束都没有。增加交点数
如果需要。请注意，从P到交点的零距离表示P在一侧

奇数表示P在多边形内

我在Php中翻译了c＃方法，并添加了许多注释来理解代码。
检查点在多边形内部还是外部。此过程使用gps坐标，并且在多边形的地理区域较小时可以使用。
INPUT：$ poly：Point：多边形顶点列表的数组； [{Point}，{Point}，...]； $ point：要检查的点；点：{" lat" =>" x.xxx"，" lng" =>" y.yyy"}
$ c为假时，与多边形的交点数为偶数，因此该点位于多边形的外部;当$ c为true时，与多边形的交点数为奇数，因此该点在多边形内部; $ 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;
    }
}

如果您有一个简单的多边形(没有一条线交叉)并且没有孔，那么您也可以对多边形进行三角测量，无论如何您都可能要在GIS应用程序中绘制该TIN，然后在每个多边形中测试点三角形。如果多边形的边数量较少，但是点的数量很多，则此速度很快。

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

否则，一定要使用绕线规则而不是边线交叉，边线交叉会对边上的点产生实际的问题，如果您的数据是由精度有限的GPS生成的，则这很有可能。

简的答案很好。

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

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

最后一种算法比看起来复杂。您必须非常小心，当您的虚构射线恰好撞击多边形的一个顶点时会发生什么。

如果您的假想射线沿-x方向传播，则只能选择对至少包括一个点的y坐标严格小于该点的y坐标的线进行计数。这就是您如何使大多数奇怪的边缘情况正常工作的方式。

检查点是否在多边形内-

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

计算由边a1-> a2形成的三角形的矢量区域以及将a2连接到P并将P连接到a1的矢量。类似地，计算每个可能的三角形的向量面积，这些三角形的一侧为多边形的边，另两个三角形将P连接到该边。

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

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

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

很容易处理

$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

(答案是我自己删除后返回的，因为它最初的格式错误)

以上就是短码网小编为大家整理的《算法 地理围栏-指向内部/外部多边形》相关内容，希望大家喜欢。