Слияния/соединения геометрических объектов

Question

У меня есть контейнер геометрических объектов. Предположим, что есть круг, эллипс, линия, дуга. Для каждого объекта я могу получить конечную точку конечной точки и сущность объекта.

Объекты могут быть подключены, так что конечные точки объекта могут быть также конечной точкой другого объекта.

Итак, мы имеем: сущность, начальные конечную точку, ID

Я хочу, чтобы назначить для каждого подключенного объекта одинакового идентификатора.

Если три объекта имеют одну общую точку, поскольку связанные объекты должны обрабатываться более длинным путем.

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

Надеюсь, что проблема хорошо определена, а метки - в порядке. Если нет, прокомментируйте или отредактируйте. Я постараюсь предоставить более подробную информацию.

Answer 1

В дополнение к предложению @ RafaelBaptista о хэш-точке конечной точки для эффективного общего решения требуется disjoint-set datastructure, что решает проблему назначения одного идентификатора для связанных групп объектов.

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

Answer 2

Для небольшого числа лиц:

for (u32 i = 0; i < numEntities; i++) 
{ 
    for (u32 j = i+1; j < numEntities; j++) 
    { 
     if (hasCommonEndpoint(entity[i], entity[j])) 
      setSameId(entity[i], entity[j]) 
    } 
} 

Это масштабируется, как O (N^2), так что он взорвется, если у вас есть большое количество лиц. Он также предполагает, что объекты, которые соответствуют конечной точке, не будут совпадать ни на одной другой конечной точке. Если это произошло, вам нужно разрешить сущностям иметь более одного идентификатора.

Обратите внимание, что внутренний цикл начинается для j> i, поэтому вы не сравниваете один и тот же объект более одного раза. Это сократит время пополам.

Если у вас есть большое число количество объектов вы хотите сделать что-то вроде:

HashTable<endpointHash, entity> dict; 
for (u32 i = 0; i < numEntities; i++) 
{ 
    dict.insert(entity[i].endpointHash(), entity[i]); 
} 

Где HashTable хостов список всех лиц, которые имеют конечные точки с одной и той же конечной хэш. Затем для каждого списка перебирайте элементы списка, соответствующие конечным точкам, таким же образом, как и первый цикл. Это будет намного лучше примерно O (n) + O (m^2), где N велико, а M мало. Фактическая производительность будет зависеть от качества хеш-функции и количества хэш-бункеров.