Определить, находится ли геолокация в сложном многоугольнике или нет

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;

    }

У кого-нибудь есть лучший алгоритм?

Answer 1

Сферическая система координат имеет свои причуды

Чтобы избежать их, используйте вместо этого трехмерную ортогональную / ортонормированную декартову систему координат

1. конвертировать вершины полигонов и геолокации

   так (long,lat,alt) -> (x,y,z), Здесь вы найдете, как это сделать. Вам не нужно применять локальное преобразование только для первого сферического преобразования в трехмерное декартово (пункт 1).

2. использовать любой внутренний тест полигона...

   Я обычно считаю количество пересечений между линией, отведенной от вашего геолокации к любому направлению, и границей многоугольника.

   • если это нечетно, то точка находится внутри
   • если это даже тогда, точка находится вне
   • если точка лежит на любой линии многоугольника, то она внутри
   • если ваша приведенная линия попадает в какую-либо вершину, помните (не считайте несколько попаданий в этой вершине) или измените направление немного и попробуйте снова

   

[Заметки]

Не забудьте обработать все, так как 3D векторы не 2D!!!