алгоритм поиска соседей

Question

У меня есть STL файл, который содержит координаты (x,y,z) из 3 баллов (p0, p1, p2) треугольника. эти треугольники представляют собой 3D поверхность f(x,y,z). Файл STL может иметь более 1000 треугольников для представления сложной геометрии.

для моего приложения, мне нужно знать соседние треугольники для каждой записи треугольника из файла stl. что для каждого треугольника я должен выбрать 3 пары точек pair1=(p0,p1), pair2=(p0,p2), pair3= (p1,p2) и сравнить их с парой точек в других треугольниках в наборе

Какой лучший и самый эффективный алгоритм для достижения этой цели? могу ли я использовать hashtree, hashmap?

Answer 1

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

double pnt[points][3]; 
int tri[triangles][3]; 

pnt должен быть список всех различных точек (индекс разбирайтесь, чтобы улучшить скорость для подсчета высокой точки). tri должен содержать 3 указателя точек, используемых в треугольнике. Сортируйте их (по возрастанию или по убыванию), чтобы улучшить скорость совпадения.

Теперь, если любой треугольник tri[i] разделяет тот же край, что и tri[j], тогда эти два являются соседними треугольниками.

if ((tri[i][0]==tri[j][0])&&(tri[i][1]==tri[j][1]) 
    ||(tri[i][0]==tri[j][1])&&(tri[i][1]==tri[j][2])) triangles i,j are neighbors 

Добавить все комбинации ...

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

Чтобы загрузить STL в такой структуре сделать это:

1. ясно pnt[],tri[] списки/таблицы
2. процесс каждый треугольник СТЛ

3. для каждой точки треугольника

   посмотреть, если он находится в pnt[] если да использовать свой индекс для нового triangle. если не добавить новый point в pnt и использовать его индекс для новых triangle. Когда все 3 очка сделают, добавьте новый triangle в tri.

Повышение производительности pnt[]

Добавить индекс сортировки для pnt[] отсортированные по любой координате, например x и улучшить производительность проверки, если point уже присутствует в pnt.

Так при добавлении (xi,yi,zi) в pnt[] индекс Находят точки, которые имеют самый большой x, который xi>=pnt[i0][0] через бинарный поиск, а затем сканировать все точки в pnt, пока x крестов xi так xi<pnt[i1][0] таким образом, что вам не нужно, чтобы проверить все точки ,

Если это слишком медленно (как правило, если количество точек больше, то 40000) вы можете повысить производительность более по индексу сегмента сортировки (разделив индекс сортировки в сегменте страниц конечного размера, как 8192 точек)

Улучшение tri[] производительность

вы также можете отсортировать tri[] по tri[i][0], так что вы можете использовать бинарный поиск аналогично pnt[].

Answer 2

Я предложил бы идти с hashmap где значения являются sets (на основе дерева) ссылок на Tringles, ключи те пары Points (позволяет называть эти пары просто Sides) и некоторые хэширования функцию, которая будет принимать в что свойство hash Side (a, b) должно быть равно хешу (b, a).

Своего рода алгоритм:

1. Read 3 Points и создать из них 3 Sides и Triangle.
2. Добавить все, что hashmap: map[side[i]].insert(tringle)
3. Повторить 1-2, пока не прочтете все данные

Теперь у вас есть карта с заполненными данными. О сложности наполнения: вставках в hashmap является постоянная временем при среднем (это также зависит от хэша-функции) и сложность вставки в set является логарифмической поэтому полная сложность данных filleng является O(n*logm), где n является номер Sides и m - среднее число Tringles с тем же Side.

Обычно каждый set будет содержать около 4 Triangles: 1 + 3 побочных соседей, поэтому logm является относительно небольшим (по сравнению с n) и могут быть не приняты во внимание (предположим, что это константа). Эти предложения приводят нас к какому-то вывод: наилучший случай сложность для заполнения не O(n) (без столкновений, не перепевы, и т.д.) и худшее O(n*logn) (в худшем случае вставка nSides по 1 усредненных по карте и logn случае вставки в один комплект, означающий все Tringles, то же самое Side).

Теперь, чтобы получить все боковые сосед по некоторым Triangle:

1. Получить все 3 sets для каждого Side того Triangle (например set[i] = map[triangle.sides[i]]
2. Получить пересечение этих 3 sets (исключить triangle получить только. его соседние соседи).
3. Выполнено.

О сложности получения соседей: linearly-depent размером sets и относительно небольшим по сравнению с 'n' в нормальном случае.

Примечание: Чтобы не боковые -neighbours но точка -neighbours (предполагающие соседи называют любой 2 Triangles с общим Point не Side) просто заполнить sets с Points вместо Sides. Вышеприведенные предположения о временных сложностях имеют место и для констант.