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

Я хотел бы сравнить точки из одного массива с точками из другого массива и найти ближайшую пару. До сих пор все, с чем я сталкивался, было с одним массивом. Я не хочу сравнивать точки из одного массива. Алгоритм грубой силы работает, но слишком медленно. Есть ли алгоритм или реализация для этого с использованием метода «разделяй и властвуй»?

РЕДАКТИРОВАТЬ 1: точка определяется как пара (широта, долгота) на поверхности земли.


java arrays algorithm closest-points divide-and-conquer
person Lawrence    schedule 01.08.2014    source источник
comment
Что здесь point? (x,y) координата точки в 2d пространстве или?   -  person Pham Trung    schedule 01.08.2014
comment
@PhamTrung Точка определяется как пара (широта, долгота) на поверхности земли.   -  person Lawrence    schedule 01.08.2014
comment
Другие уже указали вам на хорошие решения, как эффективно найти ближайшего соседа. Вероятно, хорошей идеей будет преобразовать ваши пары долгота/широта в пространственные точки, например, относительно Земли, Система координат, привязанная к Земле, поскольку отношение долготы к расстоянию не постоянно на всех широтах. (Вы можете сделать это преобразование один раз перед поиском ближайшего соседа.)   -  person M Oehm    schedule 02.08.2014
comment
@MOehm Большое спасибо. Я реализую это и дам вам знать, как это работает.   -  person Lawrence    schedule 04.08.2014
comment
@MOehm У меня был вопрос о преобразовании широты и долготы в пространственные координаты. Нужно ли преобразование, если мы имеем дело с такой небольшой территорией, как Париж?   -  person Lawrence    schedule 06.08.2014
comment
Если ваш домен поиска ограничен относительно небольшой областью, искажение значений широты и долготы незначительно, и вам не нужно использовать декартовы координаты. Но Париж находится примерно на 49 ° с. Поэтому я бы предложил ввести постоянный коэффициент для расчета расстояния: d² = (a*lng)² + lat², где a = 1/cos(lat_m) и lat_m — это средняя широта вашего поискового домена.   -  person M Oehm    schedule 06.08.2014
comment
@MOehm Большое спасибо. Это очень помогает.   -  person Lawrence    schedule 07.08.2014

Ответы (2)


arrow_upward
4
arrow_downward

Вы можете построить kd-дерево для первого массива точек, а затем найти ближайшую точку из первого массива для каждой точки второго массива, используя это дерево. Он работает за O (n log n) в среднем (n — размер наибольшего из двух массивов). Чтобы использовать kd-tree, вы можете преобразовать свои исходные координаты в координаты 3D-пространства.

person kraskevich    schedule 01.08.2014
comment
Спасибо за ваш ответ. Я реализую его и вернусь к вам. - person Lawrence; 04.08.2014
comment
У меня возник вопрос по переводу широт и долгот в пространственные координаты. Нужно ли преобразование, если мы имеем дело с такой небольшой территорией, как Париж? - person Lawrence; 06.08.2014
comment
@Lawrence Это зависит от необходимой точности, насколько близко могут быть точки и так далее. Может быть, вы можете просто попробовать запустить его с преобразованием и без него и посмотреть, не сломается ли что-нибудь. - person kraskevich; 06.08.2014
comment
В порядке. Я попытаюсь. Спасибо. - person Lawrence; 06.08.2014

arrow_upward
1
arrow_downward

вы можете использовать kd-tree, octo tree, rtree, rtree*. все эти алгоритмы O (log n) для поиска ближайшей точки. Имплементация rtree в библиотеке boost

person Constantine Kuznetsov    schedule 01.08.2014
comment
но у rtee нет функции сборки, только вставка (более медленная). Я пишу свою реализацию, но сейчас она такая сырая. если вы хотите, вы можете написать мне по почте, и я могу отправить вам свою реализацию. - person Constantine Kuznetsov; 07.08.2014
comment
Я пробую это с kd-tree. Будет интересно сравнить с вашей реализацией, если вы не против идеи. Если позволите, где с вами связаться? - person Lawrence; 07.08.2014
comment
чтобы построить дерево, я использую сортировку на месте. мы можем связаться по электронной почте. [email protected] - person Constantine Kuznetsov; 07.08.2014
comment
@ConstantineKuznetsov: Это неправда, можно создать R-дерево сверху вниз, например. из ряда геометрий. Это называется массовой загрузкой или созданием пакетов, и в целом это также алгоритм «разделяй и властвуй», выполняющий сортировку локально, как в случае kd-дерева. В частности, реализация R-дерева Boost.Geometry поддерживает этот метод, начиная с версии Boost 1.55. - person Adam Wulkiewicz; 06.01.2015