Сравнение лат, длинные координаты

Question

У меня есть список из более чем 15 тысяч координат широты и долготы. При любых координатах X, Y какой самый быстрый способ найти ближайшие координаты в списке?

Answer 1

На какой площади расположены эти координаты? На какой широте они? Какую точность вы требуете? Если они довольно близко друг к другу, вы, вероятно, можете игнорировать тот факт, что Земля круглая, и просто рассматривать это как декартову плоскость, а не возиться со сферической геометрией и большим круговым расстоянием. Конечно, когда вы удаляетесь от экватора, градусы долготы становятся меньше по сравнению с градусами широты, поэтому может быть уместен некоторый коэффициент масштабирования.

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

Answer 2

Преждевременная оптимизация - корень всего зла.

15K координат не так много. Почему бы не перебрать координаты 15K и посмотреть, действительно ли это проблема с производительностью? Вы можете сэкономить много работы, и, возможно, она никогда не станет слишком медленной, чтобы даже заметить.

Answer 3

Даже если вы создадите диаграмму Вороного, это все равно означает, что вам нужно сравнить свои координаты x, y со всеми 15 тысячами созданных областей. Чтобы сделать это проще, первое, что пришло мне в голову, это создать некую сетку по возможным значениям, чтобы вы могли легко разместить координаты х / у в одном из полей сетки, если это Для списка областей вы должны быстро сократить возможные кандидаты для сравнения (поскольку сетка будет более прямоугольной, область может находиться в нескольких позициях сетки).