找到四面體網格的邊的算法

Question

我有幾千個爲建模而生成的四面體網格。我有頂點和表面信息被索引到兩個矩陣中，這些矩陣有些是相關的。曲面的節點鏈接到頂點的矩陣。我想找出哪些頂點相互連接形成一個四面體。有沒有一種算法來檢測形成四面體邊的頂點的連通性？

Answer 1

如果您的節點矩陣是鄰接矩陣，即最近的鄰居，然後選擇任何頂點，一些四面體它形成其他剩餘頂點必須滿足：

（我）他們是近鄰（ii）它們是彼此的直接鄰居。如果這不是真的，那麼你將最終與四面體相交。

---

如果我誤解你的說法，也就是說，它的不是鄰接矩陣，那麼你就必須做Delaunay三角，即計算您的點雲中的3D Voronoi單元圖的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. 'sort'命令對所有行進行排序。這將確保 所有重複的邊緣在一起
3. 的「uniq的」命令禁止 重複的行

如果你是在Windows下，你可以安裝cygwin（有AWK，sort和uniq）。在其他腳本語言（如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個邊，每條邊一個邊。

很明顯，您可以將兩個命令組合起來，直接從四面體文件中提取唯一的邊緣列表。