javascript - 位置是否在多边形内找到 C#

Question

我正在 C# 中寻找一种完美的算法，用于确定是否在多边形内找到某个位置(纬度/经度)。

在谷歌地图上，我创建了不同的多边形区域。每个区域都可以用一组坐标表示。例如，下面是牙买加蒙特哥湾(A区)的坐标(经度、纬度组合):

-77.9531479,18.4565699,-77.9482339,18.4579542,-77.9443393,18.4615874,-77.9399726,18.4627373,-77.933943,18.4653526,-77.931272,18.4652763,-77.9282138,18.46578,-77.9267121,18.4645891,-77.924619,18.4625118,-77.923131,18.4689837,-77.924646,18.4727285,-77.924112,18.4763919,-77.9255882,18.4793735,-77.927573,18.4833522,-77.9234638,18.4888979,-77.92363,18.492311,-77.914973,18.4951459,-77.918355,18.4971759,-77.972733,18.4985953,-77.916291,18.527569,-77.8997725,18.56178,-77.8962851,18.58578,-77.873843,18.517512,-77.8772736,18.5228297,-77.9253387,18.521568,-77.9531479,18.4565699

现在假设我们需要查明牙买加蒙特哥湾的 Sunset beach Hotels 坐标(经/纬度):-95.030710, 29.148650 是否属于 A 区？

我已经测试了很多可用的算法，但没有一个能够完美运行。它适用于某些酒店，但不适用于所有酒店。

如有任何帮助，我们将不胜感激。

Answer 1

我已成功使用绕线编号:http://geomalgorithms.com/a03-_inclusion.html

第 1 步:定义绘制多边形的方向。

从根本上来说，多边形是静态的，没有方向。但是，请考虑在纸上绘制多边形时执行的移动。您从一个位置开始，然后移动笔为多边形的每一侧绘制一条线。如果你不把笔从纸上拿开，多边形的每条边要么全部按顺时针方向绘制，要么全部按逆时针方向绘制。

我们可以使用这个“方向”来确定多边形的边如何围绕该点“缠绕”(顺时针缠绕或逆时针缠绕)。

对于所讨论的真实多边形(尚未在某个方向上绘制)，您认为它是在哪个方向上绘制的并不重要，但重要的是每条边都被认为是在同一方向上绘制的.

第 2 步:将多边形的每一边视为具有两个顶点的单独对象。

如果我们知道多边形的顶点，我们就可以确定多边形每条边的端点。

第 3 步:确定每条边与点相交的方向(如果边确实与点相交)。

使用顺时针缠绕来查找多边形是否包围点的示例:

定义一个计数器来跟踪缠绕数。

对于多边形的每条边，取第一个顶点 vertex1 和第二个顶点 vertex2(这些点定义每条边的端点)。如果vertex1.x <point.x，则边从point.x的左侧开始。如果 vertex2.x > point.x 则侧面结束于 point.x 的右侧。如果边从左侧开始并在右侧结束，则该线穿过该点。

如果边穿过点，我们需要确定它穿过的方向。使用顺时针方向作为正方向，边必须穿过点上方才被视为正方向。如果点 x 位置处的线的 y 值大于点 的 y 值，则该线会穿过点上方。否则它会穿过该点下方。

如果它越过上方，则增加计数器。如果它越过下方，则减少计数器。

注意:请注意，如果线从左到右穿过，则正方向会看到线在点上方经过，但如果线从右到左(回绕到点下方)，则正方向会看到线通过低于该点。正方向为顺时针方向。

现在对多边形的下一条边执行相同的操作，其中 vertex1 将是前一条边的 vertex2，而新的 vertex2是按顺时针方向移动时多边形的下一个 Angular 。

对多边形的所有边执行此操作。

最后，您将得到一个带有正值、负值或 0 值的计数器。

如果计数器的值为0，则多边形不包含该点，否则包含该点。

这是因为，包含一个点的多边形总是有偶数条边经过该点。可以是 2 条边，也可以是 4 条边等。其中，一半将从点上方从左到右经过，一半将从点下方从右到左经过。

结果为 0 意味着没有边经过该点(因此多边形永远不会与该点的轴相交)，或者多边形在两个方向上经过该点的一侧(例如，从左到右在该点上方，然后在该点上方从右到左)。因此绕组数相互抵消。