Какую структуру данных я должен использовать для индексации географических координат?

Question

У меня есть набор объектов, имеющих координаты широты и долготы, и мне нужно иметь возможность сопоставить другой набор с ближайшим элементом. Простые вещи ближайшего соседа. Моя лучшая мысль - преобразовать координаты широты / долготы в трехмерные координаты, а затем сохранить их в дереве K-d или в октрее для последующего поиска. Он должен работать и быть достаточно хорошим для всех практических целей (см .: kdtree для поиска геопространственных точек ), но кое-что в этом не чувствуется. Я думаю, что это та часть, где на самом деле это просто 2D-коллектор в 3D-пространстве.

Есть ли более подходящая структура для использования или я просто переосмыслил это?

Answer 1

Даже в Википедии сказано:

дерево kd (сокращение от k-мерного дерева) - это структура данных с пространственным разделением для организации точек в k-мерном пространстве.

, так что продолжайте и используйте ваши 2D точки ( без проецирования их в 3D или что-то подобное).

Вставьте их в дерево, а затем выполните запросдерево в логарифмическом времени - и там все счастливы!