Найти ближайшего соседа в радиусе

Question

У меня есть набор пунктов A в моем пространстве (географические точки, но я могу предположить, что они находятся на двумерной плоскости).

У меня есть еще один набор пунктов B.

За каждую точку в B Я хочу найти каждую точку в A внутри радиуса R с центром в рассматриваемой точке от B набор.

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

Минимальный пример сбоя KDTree:

При исследовании KDTree целевая точка (красная) находится под линией точки под номером 1.Это приведет к исследованию точки под линией, при этом реальная точка внутри радиуса красной точки будет отсутствовать.

Какой алгоритм или структура данных обеспечивают 100% корректность?

Я точно знаю, что буду работать хуже, но я ищу баланс между скоростью поиска и полной корректностью.

Answer 1

Дерево K-D является хорошей структурой данных для решения этой проблемы.Однако вы не можете слепо применять процедуру поиска только к центральной точке, вы должны быть немного умнее.

При поиске точек в K-D дереве каждый раз, когда вам нужно выбрать левый или правый дочерний элемент для поиска, проверьте, находится ли разделяющая плоскость слева от вашей окружности, пересекает ее или находится справа от окружности.

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