найти штат/графство программно, учитывая границы каждой области и широты/долготы

Question

Предположим, что у вас есть границы штатов/округов любой страны в текстовом файле следующим образом:

State \t State Name \t Lat/Long of entire State Boundary(comma separated). 

Я хочу чтобы сохранить эту информацию в структуре данных **, а затем получить lat-long, получить состояние.

Я не хочу использовать API, и не хочу, чтобы сделать грубую силу подхода (то есть построить полигон для каждого состояния и затем сделать point in polygon алгоритм до попадания)

С моим ограниченным Я думаю, что KD-Trees или R-Trees - это способ сделать это? Хотя оба кажутся хорошим выбором, я не уверен, какой из них использовать. Было бы очень полезно, если вы можете предоставить подробное объяснение - от создания структуры данных до выполнения поиска.

Меня больше интересуют округа, чем государства из-за их более тонкой детализации. Возможно, стоит остановиться на построении дерева с большей степенью детализации, а затем сделать точку в многоугольном подходе для всех графств в этой гранулярности (минимальная ограничивающая область). Концептуально это кажется выполнимым, но я не уверен, как это реализовать.

Answer 1

Если вы еще не выбрали географически чистую базу данных, выберите Postgis. Mysql 5.7 также сделает трюк, но Postgis более зрелый и многофункциональный. 2

Скачать world borders shapefile.

Импорт шейпфайл в postgis или в mysql

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

Обратите внимание, что запрос ST_within выполняется быстро, и вам не нужно много заниматься самостоятельно. Это один лайнер.

Настройка базы данных и импорт базы данных может быть тяжелой работой, но вам все равно придется это делать, даже если вы придумаете решение для дома.