Избегайте вложенных циклов на расстоянии

Question

У меня есть два списка объектов; Я хотел бы выполнить операцию над данным объектом списка 2, только если он находится в границах текущего объекта списка 1.

Что-то вроде этого:

for k=1:size(object_list1) 
    for l=1:size(object_list2) 
     if euclideanDstSqt(object_list1(k).centroid,object_list2(l).centroid) < toleranceRadius then 
      // do something ... 
     end 
    end   
end 

, что случилось с этим, то, что я буду проверять расстояние каждый раз, даже для объектов, которые очень далеки друг от друга. Есть ли алгоритмический более разумный способ сделать это? Может быть, какое-то дерево?

Этот алгоритм затем может быть переведен на C++, поэтому я должен забыть обо всех матрично-ориентированных трюках Matlab.

Answer 1

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

Answer 2

Возможно, поместите объекты в список 2 в k-d tree, а затем для объектов в списке 1, продолжайте поиск ближайших соседей, пока расстояние до ближайшего соседа не будет за пределами границы.