检测地理位置是否在复杂多边形内部

Question

我们目前使用以下算法来检测地理点是否在复杂多边形内部。这个算法运行良好，但当多边形穿过180°经线时会出现问题。

例如，点(-170, 60)未被检测为在多边形内，而该多边形顶点坐标为160,65,0 160,15,0 -160,15,0 -160,65,0 160,65,0。

请查看以下图像： [Img]http://tinypic.com/r/14x2xl1[/img] 我想要红框内的内容，而不是黄框内的内容！

    public static bool IsCoordinateInPolygon(IList<KMLCoordinate> polygon, KMLCoordinate testPoint)
    {

        bool result = false;
        int j = polygon.Count - 1;
        for (int i = 0; i < polygon.Count; i++)
        {
            if (polygon[i].Latitude < testPoint.Latitude && polygon[j].Latitude >= testPoint.Latitude || polygon[j].Latitude < testPoint.Latitude && polygon[i].Latitude >= testPoint.Latitude)
            {
                if (polygon[i].Longitude + (testPoint.Latitude - polygon[i].Latitude) / (polygon[j].Latitude - polygon[i].Latitude) * (polygon[j].Longitude - polygon[i].Longitude) < testPoint.Longitude)
                {
                    result = !result;
                }
            }
            j = i;
        }
        return result;

    }

有没有更好的算法？

- TWT

---

https://en.wikipedia.org/wiki/Point_in_polygon - Paul Ruane

如果您有一个跨越 +/- 180 的多边形，只需将所有经度偏移 +180。这种转换不会影响该点是否在多边形内。您甚至不需要测试多边形的位置和偏移是否处于奇怪的位置，您可以为所有测试执行该转换。 - High Performance Mark

球面上的多边形将其分成两个区域。你如何确定哪个区域是“内部”，哪个是“外部”？（在平面上，这很容易：无限远的那一侧是外部） - RBarryYoung

请修正图片。它无法工作。 - Gangnus

Answer 1

球面坐标系 有其特殊性

为避免这些问题，使用 三维正交/标准直角坐标系 更好

1. 将多边形的顶点和地理位置转换

   使(long,lat,alt) -> (x,y,z)。 在这里，你可以找到如何做到这一点。你不需要应用本地转换，只需要进行第一个球面到三维笛卡尔转换（bullet #1.）。

2. 使用任何内部多边形测试...

   我通常计算从你的地理位置向任何方向投射的线与多边形边界线之间的交点数。

   • 如果是奇数，则点在内部
   • 如果是偶数，则点在外部
   • 如果点位于多边形的任何一条线上，则它在内部
   • 如果你投射的线撞到任何顶点，则要么考虑（不要计算此顶点的多次击中），要么稍微改变方向再试一次

   

[注]

不要忘记将所有内容处理为3D向量而不是2D！

- Spektre