Пересечение географической системы координат

Question

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

Он должен охватывать всю Землю (оба полюса) и быть максимально точным.

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

Я почти уверен, что это было сделано раньше, но я не могу найти его с помощью Google.

Я использую Java, но Python тоже будет работать.

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

любая помощь будет принята!

Answer 1

Если точки находятся в базе данных, вы можете использовать для этого пространственный индекс. Довольно просто сделать пересечение грубой силы по всем вашим полигонам, но это займет много времени. Mysql, Oracle и SQLServer имеют пространственные расширения, которые позволяют создавать пространственные индексы и содержат функции против них. Это, вероятно, самый простой способ, если вы не против загрузки БД.

http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html

Если вы хотите сделать все это на Java, то вам, возможно, стоит поискать реализацию R-дерева. Это способ создать структуру, подобную B-дереву, с использованием прямоугольников, и с ее помощью будет проще определить, с какими полигонами необходимо выполнить проверку на наличие пересечений.