Решаю такую задачку на Си: есть набор город России (~ 2.5k) представленных двумя координатами его центра, соответственно широтой и долготой. На вход подаются точки опять же с широтой и долготой и нужно каждую точку отнести к некоторому городу по простому правилу - точку относим к тому городу, расстояние до центра которого минимально. То есть по сути, решается задача поиска ближайшего соседа. Данные о городах статичны, входных точек может быть порядка нескольких миллионов. Необходимо чтобы программа отрабатывала достаточно быстро. Возникает вопрос: какие алгоритмы (и может быть библиотеки) здесь использовать?
Проверять все 2.5к городов брутфорсом - не вариант, нужно построить какой-нибудь индекс типа k-D дерева или R-дерева. Какой индекс в моей задаче будет работать лучше? Как лучше работать с исходными данными: считать расстояние между точками на сферойде и соотвественно строить дерево с расчетом на то, что пространство не евклидово или же перевести координаты в какую-то проекцию? Города расположены по всей России, не будет ли перевод в какую-то проекцию давать настолько большие погрешности, что точку можно будет отнести не к тому городу?
Какие библиотеки на Си (не С++, именно С) посоветуете для работы с гео-данными в рамках указанной задачи (основной вопрос - работа именно с гео-данными, представленными широтой и долготой, найти нужно именно один ближайший город, может ли это упростить задачу?)
