地理围栏 – 指向内部/外部多边形
我想确定一个多边形，并实现一个algorithm来检查一个点是否在多边形的内部或外部。
有谁知道是否有任何类似的algorithm可用的例子吗？
只要看看多边形中的点（PIP）问题 。
如果我没有记错，algorithm是通过你的testing点绘制一条水平线。 计算您相交的多边形的多less行以达到您的要点。
如果答案很奇怪，你就在里面。 如果答案是偶然的，你就在外面。
编辑：是的， 他说的（ 维基百科 ）：
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; } Loc类
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; } }
在search网页并尝试各种实现并将它们从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 <= Py 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 > Py (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
我认为有一个更简单，更有效的解决scheme。
这里是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; }
到目前为止，最好的解释和实现可以在点多边形绕组编号包含中find
在解释良好的文章结尾处甚至还有一个C ++实现。 这个网站还包含一些很好的algorithm/解决scheme，用于其他基于几何的问题
我修改并使用了C ++实现，并创build了一个C＃实现。 你一定要使用Winding Numberalgorithm，因为它比边缘交叉algorithm更精确，而且速度非常快。
只是一个头（用我不能评论的答案），如果你想用geo fencing的多边形中的点，那么你需要改变你的algorithm来使用球坐标。 -180度经度与180度经度相同，在这种情况下，多边形的点将被打破。
在asp.Net C＃中完整的解决scheme，你可以在这里看到完整的细节，你可以看到如何使用纬度和经度find点（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; }
检查一个点是否在一个多边形内 –
考虑具有顶点a1，a2，a3，a4，a5的多边形。 下面的一组步骤可以帮助确定点P是位于多边形内部还是外部。
计算由边a1-> a2形成的三angular形的vector面积和连接a2到P和P到a1的vector。 类似地，计算每个可能的三angular形的vector面积，其中一个边作为多边形的一侧，另外两个连接P作为该边。
对于一个多边形内的点，每个三angular形都需要有正面的面积。 即使其中一个三angular形具有负面的面积，那么点P也不在多边形中。
为了计算三angular形给定的三angular形边界的面积，请参考http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm
如果你的多边形是凸的，问题会更容易。 如果是这样，您可以对每条线做一个简单的testing，看看该点是在该线的内部还是外部（在两个方向上延伸到无穷大）。 否则，对于凹多边形，从你的angular度画一个虚射线到无限（在任何方向）。 计算它跨越边界线的次数。 奇数意味着点在里面，甚至意味着点在外面。
这最后一个algorithm比看起来更复杂。 当你的虚射线正好碰到多边形的一个顶点时，你将必须非常小心。
如果虚射线沿-x方向移动，则只能select包含至less一个y坐标严格小于y坐标的点的线。 这是如何让大多数奇怪的边缘情况下正常工作。
如果你有一个简单的多边形（没有任何交叉线），你也没有洞，你也可以对多边形进行三angular剖分，无论如何，在GIS应用中你可能要绘制一个TIN，然后testing每个点三angular形。 如果多边形的边数less，但是点数多，则速度快。
有关三angular形中有趣的点，请参阅链接文本
否则肯定会使用缠绕规则而不是边缘交叉，边缘交叉在边缘上有点问题，如果您的数据是以精度有限的GPS生成的，那么很有可能。
该多边形被定义为点对A，B，C …的顺序列表。A.无边AB，BC …穿过任何其他边
确定框Xmin，Xmax，Ymin，Ymax
情况1，testing点P位于盒子外面
情况2testing点P位于箱内：
确定方框{[Xmin，Ymin] – [Xmax，Ymax]}的“直径”D（并加一点额外的值以避免与D在一侧可能的混淆）
确定各方面的梯度M.
find与所有梯度M最不同的梯度Mt
testing线从P处以梯度Mt运行距离D.
将交点数设置为零
对于每一边AB，BC都从一开始就testingPD与一侧的相交点，但不包括其末端。 根据需要增加交叉点的数量。 请注意，从P到交点的零距离表示P在一侧
奇数指示P在多边形内
我翻译了PHP中的C＃方法，并添加了很多注释来理解代码。
PolygonHelps的描述：
检查点是在多边形的内部还是外部。 这个程序使用gps坐标，当多边形有一个小的地理区域时，它可以工作。
INPUT：
$ poly：Point：多边形顶点列表的数组; [{Point}，{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; } }
我添加一个细节来帮助居住在地球南部的人！ 如果你在巴西（这是我的情况），我们的GPS坐标都是负面的。 所有这些algorithm都给出了错误的结果。
最简单的方法是使用所有点的纬度和长度的绝对值。 在这种情况下，扬·科伯斯基的algorithm是完美的。
