如何索引非結構化網格？

Question

我想導入非結構化的2D/3D網格是這樣的：

或本

到我的模擬。

我認爲非結構化網格用頂點列表和邊緣列表（即哪些頂點連接到哪個頂點）來描述。我不知道如何從中獲得能夠索引網格中的子卷。

然後我想在網格上運行一個模擬。爲了做到這一點，我需要能夠：

1）指數網 2）生成鄰居列表

如何實現這個目標？

Answer 1

使用頂點和邊，可以得到無向圖。用於表示圖形的不同數據結構以及用於遍歷它們的不同算法。它不像遍歷圖那麼簡單，因爲你需要卷。

，如果你有兩個列表這將是很好：

1. 頂點座標列表卷
2. 名單這將通過各自的指數從第一列表中的列表來描述。

喜歡的東西：

LIST 1

0.4 0.7 0.8 
0.4 0.8 0.9 
0.6 0.8 0.9 
0.7 0.7 0.8 
.... 

說明2：

1 2 3 
4 2 3 
.... 

（即假定卷四面體如果他們quadralaterals或棱鏡。 ，你必須指出哪些頂點）

如果是這樣，您只需將第二個列表編入索引。

---

如果您只有頂點（座標向量）和邊（頂點索引對），那麼您必須弄清楚如何將邊轉換爲體。

邊緣的頂點和整數索引對（到第一個列表）的座標向量列表可能是存儲頂點的最有效的方法，但您可能需要使用不同的數據結構來提高效率，如列表用於頂點的座標向量和作爲邊緣的稀疏矩陣存儲的鄰接矩陣。矩陣中的每個元素表示是否存在一對頂點的邊（1是，0否）。行號是一個頂點的索引，列號是另一個頂點的索引。 （它是一個對稱矩陣。）

您可以通過找到三個頂點（1,2,3）（每個頂點共享一個帶有0的邊）和另外兩個頂點（0）來形成一個四面體，但不想包含四面體相交，所以你必須小心。然後，您可以按照升序（或降序）順序將頂點索引編制爲四面體，以便每個四面體具有唯一的索引。對於具有更多頂點的體積，您必須想出更復雜的索引方案，例如按升序（或降序）按邊緣索引。例如（42,54）會在上升的系統中出現（67,89）。因此，一個卷將包括幾個這些有序對，按順序列出這些對，並按順序排列在一對中的頂點索引。