Нахождение всех точек на расстоянии от конкретного lat long java

Question

Нахождение всех точек на расстоянии от конкретного lat long java

У меня есть csv-файл с кучей длинных координат lat, у меня также есть csv-файл с кучей позиций, на которых будет стоять конкретный человек. Для каждой из точек во втором файле мне нужно выяснить, находятся ли они рядом (менее 1 мили) с любой из точек в первом файле. У меня есть около 500 пунктов в каждом из файлов.

Я пытаюсь решить эту проблему на java и подумал, что я мог бы использовать что-то вроде чтения первого файла и поместить его в какой - то вид структура, которая легко поддается поиску, таким образом, мне не нужно продолжать делать io. Мне неясно, в какой структуре данных я должен хранить точки, чтобы я мог легко искать те, которые находятся в радиусе данной точки, может ли кто-то указать мне правильное направление, есть ли способ организовать это так, чтобы мне не нужно было делать N^2 сравнений? Спасибо Вам большое

684 3

java io data-structures csv

3 ответов:

Comments

Ничего не найдено.

pobrelkey · Accepted Answer · 2013-10-31 17:29:26

Похоже, что вы хотите сохранить свои точки вK-d дереве , основанном на широте и долготе.
Если мы знаем, что нам нужны все точки в пределах некоторого заданного расстояния D от некоторой точки (lat, lon), то несложно вычислить разницу в широте d_lat, соответствующую D единицам расстояния на север/юг, и разницу в долготе d_lon, соответствующую D единицам расстояния на восток/запад в любой из широт lat-d_lat или lat+d_lat, ближайшей к полюсу. Используя это мы выполните поискортогонального диапазона в дереве для всех точек с широтой между lat-d_lat и lat+d_lat и долготой между lon-d_lon и lon+d_lon. Затем нам нужно вычислить расстояние для каждого из них и отклонить те, которые находятся над D от (lat, lon) - но нам не нужно будет делать столько вычислений, сколько без дерева (мы должны только в конечном итоге отклонить примерно 1-pi/4 = 21,5% точек, которые попадают на эту стадию).
Конечно, вам нужно будет учитывать крайние случаи, если они имеют отношение к вы:

Если вы находитесь в пределах d_lon 180 градусов долготы, вам нужно будет выполнить два различных поиска в дереве (по обе стороны от 180 градусов).

если (lat, lon) находится в пределах d_lat широты полюса, просто ищите все к северу/югу от того, что из lat-d_lat или lat+d_lat Дальше всего от полюса.

Dawood ibn Kareem · Accepted Answer · 2013-10-30 20:39:21

Вот что я бы сделал.

Отсортируйте все точки в обоих файлах в порядке широты. Затем повторите оба списка одновременно, чтобы для каждой точки в файле 1 Вы получили список точек в файле 2, широтный круг которых находится в пределах одной мили от точки из файла 1. Вероятно, вы можете использовать метод subList List где-то здесь.

Все еще находясь в контексте точки из файла 1, отфильтруйте точки из этого подсписка, долгота которых отличается от точка 1 более чем на одну милю. Тогда у вас будут пары точек, которые находятся как в пределах долготы мили, так и в пределах широты мили друг от друга.

Для каждой такой пары сделайте точный расчет, чтобы увидеть, действительно ли они находятся в пределах мили "реального расстояния" друг от друга.

Rodion Degtyar · Accepted Answer · 2013-10-31 02:26:07

Самый простой способ-определить грубую сетку и поместить ваши точки из первого списка в ячейки сетки. Вам нужно вычислить ячейку " id " для каждой точки и поместить ее в хэш-таблицу, основанную на этом id. После этого вы можете легко искать близлежащие точки для данного lat/long, находя нужную ячейку и перечисляя ее содержимое (и содержимое соседних ячеек). Фокус в том, чтобы преобразовать lat / long в идентификатор ячейки. Один из способов-округлить lat / long. Так, например, преобразовать (47.43402067, -121.89068567) пара в строку" 47_-121". Это может быть слишком грубо, потому что один градус составляет приблизительно 70 миль на экваторе. Вы можете подтянуть его, округлив до определенной десятичной точки: например, "47.43_-122.89". Обратите внимание, что ширина ячеек будет сужаться по мере продвижения на север или юг. Например, на 60 градусах северной широты ячейка будет в два раза уже, чем на экваторе (она будет покрывать только 35 миль).

Вы также можете использовать существующие геопространственные индексы из библиотеки, такие как JTS Topology Suite, обеспечивают гораздо большую гибкость.