Определите, находится ли широта / долгота в пределах многоугольника на поверхности Земли - PullRequest
3 голосов
/ 18 ноября 2011

Я пытаюсь выяснить, содержится ли точка широты / долготы в многоугольнике, определяемом вершинами, которые представляют точки на земле (также широта / долгота, по часовой стрелке). Это тривиально для многоугольников, которые можно отобразить в двумерное пространство широты / долготы.

Где это становится все труднее, это круги (теперь переключающиеся обратно в 3D), которые могут переходить от полюса к полюсу, покрывая половину земли. Перевод в лат / лон выглядит как синусоида. 2D точка в полигональном тесте больше не применима к этому случаю. Существует ли алгоритм, который решает эту проблему?

================== Пояснения к комментариям ниже: =================== Многоугольник определяется как (lon, lat) пары в градусах, то есть (60, 90), (60, 110), (-30, 110), (-30, 90).

У меня есть код, который реализует алгоритм приведения лучей, и это работает. однако некоторые многоугольники на поверхности Земли не переводятся в замкнутые многоугольники в двумерном пространстве.

Ответы [ 3 ]

1 голос
/ 19 ноября 2011

Как заявляет denniston.t, если вас интересуют только круги, и у вас есть радиус, вы можете просто проверить, меньше ли Расстояние по большому кругу между центральной точкой и точкой, чемрадиус.Чтобы найти расстояние большого круга, вы обычно используете формула Haversine .Ниже приведена моя реализация в Python:

from math import radians, sin, cos, asin, sqrt

def haversine(point1, point2):
    """Gives the distance between two points on earth.

    The haversine formula, given two sets of latitude and longitude,
    returns the distance along the surface of the earth in miles,
    ignoring potential changes in elevation. The points must be in
    decimal degrees.
    """
    earth_radius_miles = 3956
    lat1, lon1 = (radians(coord) for coord in point1)
    lat2, lon2 = (radians(coord) for coord in point2)
    dlat, dlon = (lat2 - lat1, lon2 - lon1)
    a = sin(dlat/2.0)**2 + cos(lat1) * cos(lat2) * sin(dlon/2.0)**2
    great_circle_distance = 2 * asin(min(1,sqrt(a)))
    d = earth_radius_miles * great_circle_distance
    return d
0 голосов
/ 13 июля 2012
containsLocation(point:LatLng, polygon:Polygon)
0 голосов
/ 18 ноября 2011

Если у вас есть центральная точка и радиус вашего круга, нарисованный на поверхности сферы, вычислите Расстояние большого круга между центральной точкой и целевой точкой. Если он меньше радиуса круга, целевая точка лежит в круге.

Это не будет распространяться на произвольные многоугольники, нарисованные на вашей сфере, но вы спрашивали только о кругах, поэтому я не знаю, имеет ли это значение для вас.

...