Задача поиска ближайшего соседа для гео-данных

Для этого есть r-tree

А куда относится точка C?

A(10, 0) C(10, 5) B(10, 10)

Именно для ответа на запросы типа «ближайшая точка из заданного множества к данной» вроде строят диаграмму Вороного (тебе даже индекс не нужен — сложные алгоритмы строят ее за NlogN).

перевести координаты в какую-то проекцию?

Думаю стоит почитать об отродромии (кратчайшее расстояние между двумя точками) и меркаторской проекции (проекции на цилиндр).

например: http://www.maritime.kiev.ua/book1/chpt26.html

для пограничных случаев любой ответ сойдет

то есть вы считаете что все же стоит работать с проекцией меркатора а не с широтой и долготой? насколько большую погрешность это даст если речь идет о городах России, которые расположены на половине Евразии?

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

время построения исходной структуры, будь то R-дерево, k-D дерево или диаграмма Вороного не так важно, потому что структура будет построена разово и из относительно небольшого числа элементов, намного важнее скорость и точность ответов на вопрос «к какому городу ближе данная точка». Таких точек будет намного больше чем исходных данных о городах.

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

Это и есть диаграмма Вороного.

не с широтой и долготой

потому что «расстояние в градусах» (что это?) которое вы собираетесь считать и «длина дуги» - расстояние в киломатрах на поверхности эллипсоида не пропорциональны.

Плюсую Вороного.

Только ТС, что-то у тебя с логикой не так:

нужно каждую точку отнести к некоторому городу по простому правилу - точку относим к тому городу, расстояние до центра которого минимально

Может, таки стоит учитывать границы субъектов федерации?

А насчет погрешностей — зависит от точности задания координат. Ясен пень, если там точность не превышает угловой минуты, то и аппроксимация геоида сферой даст нормальные результаты.

Ну задумка такая: В проекции Меркатора меридианы и параллели перпендикулярны/параллельны, а значит к координатам в таком случае в принципе можно применить kd-tree.

то есть идея такая: переводим координаты в меркатора и работаем как с декартовым пространством с использованием двумерного kd-tree?

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

попробуй minimal matching. Емнип алгоритм работает за полиномиальное время.

Может быть... Тут ещё вопрос... поскольку надо искать ближайшего соседа(ближайший город), то расстояния небольшие. И вот думаю, а имеет ли вообще смысл с проекциями возиться.