Самый быстрый способ определения расстояния между объектами?

Question

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

Я попробовал следующий псевдокод, и мне нужен ваш комментарий по этому поводу.

 for (int y=0; y<blobList.size();y++){
       for (int x =1; x<blobList.size();x++)
       {
           CvPoint *blob_a = new CvPoint();
           CvPoint *blob_b = new CvPoint();
           blob_a->x = blobList[x].second->maxx;
           blob_a->y = blobList[x].second->maxy;
           blob_b->x = blobList[y].second->maxx;
           blob_b->y = blobList[y].second->maxy;

           double dist = distance(blob_a,blob_b);
           cout<< " distance between blob "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           cout<<dist<<endl;

           if( dist<ParamMgr.fDistance)
           {

           cout<< " Collision between "<<blobList[y].second->label<<"and "<<blobList[x].second->label<<endl;
           }
           else {
               cout<< " "<<endl;
           }
       }

Answer 1

Я могу придумать три решения, каждое из которых имеет свой компромисс между временем и пространством.

n x n массив

Если у вас есть небольшое количество n объектов и функция расстояния D (n ₁ , n ₂ ), вы можете рассчитать расстояния заранее .

Создание 2D n x n массива. В массиве [i, j] хранится результат D (n _i , n _j ).

Плюсы:

• После первоначального расчета ответ для любых двух объектов дается в O (1).
• Простота

Минусы:

• неэффективность для больших наборов данных
• Не может легко добавлять новые объекты на лету

запоминание

Запоминание функция расстояния для запоминания предыдущих вызовов.

R-Tree

Стандартная структура данных для хранения объектов в 2D \ 3D-объектах, таких как точки и Многогранники , равна R-Trees . Короче говоря, ваши объекты сгруппированы в трехмерные кубы соседних предметов. Он обеспечивает эффективное время вставки и просмотра журнала (n), а поиск порогового расстояния чрезвычайно эффективен, особенно когда ответ отрицательный.

Цитирование статьи Википедии :

Обычное использование R-дерева в реальном мире может заключаться в хранении ... полигонов, типичных для карт. состоят из: улиц, зданий, очертаний озер, береговых линий и т. д. а затем быстро найти ответы на такие вопросы, как «Найти все музеи» в пределах 2 км от моего текущего местоположения "," восстановить все участки дороги в пределах 2 км от моего местоположения "

И

Ключевая идея структуры данных состоит в том, чтобы сгруппировать близлежащие объекты и представлять их с их минимальным ограничительным прямоугольником в следующем более высокий уровень дерева; «R» в R-дереве для прямоугольника.

У вас есть реализации R-Tree на большинстве современных языков программирования.

Answer 2

Аналогично принятому решению для В поисках алгоритма без "грубой силы" для удаления пересекающихся областей коллекции Rects вы можете отсортировать объекты по одному из x, y или z измерения и для каждого объекта просто искать вперед в отсортированном списке по порогу (возможно, масштабируется для учета дополнительных измерений). Это по крайней мере даст вам все объекты, которые определенно не рядом. Для остальных вы можете либо проверить их расстояние и принять решение, либо лучше поделить остальные измерения на несколько секций одинакового размера и классифицировать каждый объект как находящийся в разделе, если его значение j-измерения находится в этом раздел. Вы можете быстрее прийти к решению относительно того, находится ли объект определенно за порогом. В целом, для данного объекта этот подход уменьшит количество вычислений фактического расстояния до небольшого числа, и проблема будет эффективно увеличена.

Answer 3

Если трехмерное пространство ограничено, то мы можем разделить пространство на маленькие кубики.Длина каждого ребра является пороговым значением.Мы принимаем это как d .Затем мы просто помещаем объекты в кубики.Подберите кубики B (x_i, y_j, z_k) , которые содержат объекты.Тогда мы просто проверяем соседние кубики.Максимум, для каждого куба у нас будет 27 кубов, включая самого себя.Мы можем игнорировать другие кубы, так как они определенно имеют расстояние дальше порога.

Это решение хорошо работает только в том случае, если узлы разрежены.Если все узлы находятся в пространстве 3d * 3d * 3d .Тогда алгоритм будет в худшем случае.Вы не можете фильтровать никакие узлы.