Алгоритм поиска краев ячеек тетраэдров

Question

У меня есть несколько тысяч ячеек тетраэдров, которые генерируются для моделирования. У меня есть информация о вершинах и поверхностях, которые индексируются на две матрицы, некоторые из которых связаны друг с другом. Узлы поверхностей связаны с матрицей вершин. Я хочу найти, какие вершины связаны друг с другом, чтобы образовать тетраэдры. Существует ли алгоритм обнаружения связности вершин, образующих ребра тетраэдров?

Answer 1

Если матрица узел представляет собой матрицу смежности, т.е. ближайших соседей, а затем выбрать любую вершину, остальные три остальные вершины некоторых тетраэдра она образует должны удовлетворять:

(я) они являются непосредственными соседями выбранная вершина,

(ii) Они являются ближайшими соседями друг другу. Если это не так, вы получите тетраэдры, пересекающие друг друга.

---

Если я неправильно понял ваше заявление, т.е. это не матрицы смежности, то вам придется сделать 3D-версию триангуляционной, т.е. вычислительного график ячейки 3D Вороного для вашего облака точек , https://en.wikipedia.org/wiki/Voronoi_diagram

Answer 2

Эта ссылка может помочь вам найти алгоритм. http://mathworld.wolfram.com/Tetrahedron.html

Answer 3

Начиная из списка, возможно, дублированных краев:

Предположим, что вы получили файл ASCII с возможно дублировать края. В системе Unix, вот простой способ извлечения из него список уникальных краев:

cat edges.txt | awk '{printf "%d %d\n", ($1 < $2 ? $1 : $2), ($1 > $2 ? $1 : $2)}' | sort | uniq > unique_edges.txt 

Что он делает:

1. Команда «AWK» гарантирует, что в каждом ребре, вершины нижнего id на первом месте (таким образом, в файле будет один способ представления одного и того же ребра)
2. Команда сортировки сортирует все строки. Это гарантирует, что все дублированные края вместе
3. команда «уник» подавляет дублированные строки

Если вы под Windows, вы можете установить Cygwin (иметь AWK, сортировать и уник). Также довольно легко сделать что-то подобное на других языках сценариев (например, perl).

Начиная из списка тетраэдров:

Теперь, если вы начинаете с файлом с тетраэдров, вы можете создать список (дублируется) ребер следующим образом (то вы можете выполнить команду выше, чтобы удалить дубликатов):

cat tetrahedra.txt | awk '{printf "%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n", $1, $2, $1, $3, $1, $4, $2, $3, $2, $4, $3, $4}' > edges.txt 

Что делает: он генерирует для каждого тетраэдра его 6 ребер, одно ребро в каждой строке.

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