Точка внутри или снаружи полигона, который находится на поверхности земного шара
Как я определяю, ли точка внутри или снаружи полигона, который находится на поверхность земли?
Внутренняя часть полигона может быть определена через правило правой руки, т.е. внутренняя часть полигона находится на Вашей правой стороне, когда Вы идете вокруг полигона.
Полигон может
- Круг любой полюс
- Пересеките 180 долгот
- Покройте больше чем 50% земного шара
Поскольку земной шар является сферой, нормальные алгоритмы пересечения луча не работают правильно.
2 ответа
На самом деле подходы обычной трассировки лучей и правила намотки отлично работают на поверхности сферы с небольшим корректирование.
На поверхности сферы «прямая линия» представляет собой большой круг, а расстояния измеряются в угловых единицах, а не в метрах или дюймах. Чтобы нарисовать луч из произвольной точки на поверхности сферы, просто сформируйте большой круг через эту произвольную точку и любую другую точку на поверхности сферы. Чтобы математика не усложнялась, выберите вторую точку примерно на π / 2 от точки, местоположение которой вы проверяете. Примените обычное правило четности-нечетности к большому кругу и вашему испытательному многоугольнику.
Правило поворота также непосредственно переводится с прямых на плоскости в (сегменты) больших окружностей на сфере.
Все, что вам сейчас нужно, это реализация Java основных операций сферической геометрии. У меня нет никаких рекомендаций по этому поводу, но я думаю, что Интернет поможет. Для математики начните с Mathworld .
Другой подход заключается в проецировании ваших точек и многоугольников с поверхности сферы на плоскость - что и делают картографические проекции - такое преобразование не повлияет на топологические отношения внутренней сущности.
Да, и вам нужно будет решить, что делать, если ваш многоугольник описывает большой круг
Используйте плоскости вместо лучей. Линия" на поверхности сферы, заданная двумя точками, является дугой большого круга (круг, центр которого - центр сферы) и также содержится в плоскости, содержащей эти две точки и центр сферы.
Проверьте, является ли точка "больше" или "меньше" соответствующей плоскости для каждого края "многоугольника", чтобы определить, на какой стороне "прямой" она находится.