Точка внутри или снаружи многоугольника, который находится на поверхности земного шара

Question

Как определить, находится ли точка внутри или снаружи многоугольника, лежащего на поверхности земли?

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

Полигон может

1. Обвести любой полюс
2. Пересечь 180 долготу
3. Покрыть более 50% земного шара

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

Answer 1

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

На поверхности сферы «прямая линия» представляет собой большой круг, и расстояния измеряются в угловых единицах, а не в метрах или дюймах.Чтобы нарисовать луч из произвольной точки на поверхности сферы, просто сформируйте большой круг через эту произвольную точку и любую другую точку на поверхности сферы.Чтобы сохранить математику в чистоте, выберите вторую точку около pi / 2 от точки, местоположение которой вы тестируете.Примените обычное четно-нечетное правило к большому кругу и вашему тестовому многоугольнику.

Правило намотки также переводит прямо с прямых линий на плоскости (сегменты) больших кругов на сфере.

Все, что вам сейчас нужно, это реализации Java базовых операций сферической геометрии.У меня нет никаких рекомендаций на этот счет, но я думаю, что Интернет поможет.Поскольку математика начинается с Mathworld .

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

О, и вам придется решить, что делать, если ваш многоугольник описывает большой круг

Answer 2

Используйте самолеты вместо лучей. «Линия» на поверхности сферы, определяемая двумя точками, представляет собой дугу большого круга (круг, центр которого является центром сферы), а также содержится в плоскости, содержащей эти две точки и центр сферы. .

Проверьте, является ли точка "больше" или "меньше", чем соответствующая плоскость для каждого края "многоугольника", чтобы определить, на какой стороне "линии" она находится.