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

измените представление сетки на таблицу точек и таблицу граней треугольника. 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. обработать каждый треугольник STL

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[].

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

Какой-то алгоритм:

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

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

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

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

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

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

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