Найти ближайшего соседа по коду

Question

Я реализовал decode/encode метод для преобразования 2d точек в их соответствующие morton code,

То, что я ищу, это найти ближайшего соседа (под min_distance) Так например вот так:

points=[(200,300),(500,150),(100,50)]
mortonCodes = {}
for p in points:
    mortonCodes[encode(p)] = p

nearest = findNearestNeighbor(mortonCodes, (201,305))
print(nearest) # ---> should return (200,300)

Это возможно?

Answer 1

Вы можете сделать следующее, используя min_distanceНапример, 120: используйте точку запроса qp=(201,305) и создайте минимальные и максимальные точки, вычтя / добавив расстояние: min=(81, 185) а также max=(321,425), Теперь вы создаете коды для этих двух точек.

Все точки, которые находятся на расстоянии до 120 от (210,305), будут иметь код минота mcWithin120 с mortonCode(min) <= mcWithin120 <= mortonCode(max), Если у вас есть список точек, упорядоченных по коду Morton, это должно немного сузить область поиска.

Обратите внимание, что диапазон будет содержать ложные срабатывания! Не все точки с минимальным и максимальным кодами находятся на заданном расстоянии 120, поэтому необходимо проверить все точки в диапазоне, находятся ли они "на самом деле" на правильном расстоянии.

Если вы заинтересованы в пространственном поиске, посмотрите на PH-Tree, это пространственный индекс, похожий на quadtree, который использует порядок следов для оптимизации древовидной структуры и поиска.