鄰居搜索算法

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個用於三角形的點的索引。對它們進行排序（asc或desc）以提高匹配速度。

現在，如果任何三角形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[]通過檢查point已經存在於pnt的任何座標例如x並提高性能來分類的。

因此，儘管加點以來最大的x這是xi>=pnt[i0][0]通過二進制搜索，然後掃描所有點pnt直到x十字架xi所以xi<pnt[i1][0]這樣就不需要檢查所有點的(xi,yi,zi)到pnt[]發現指數。

如果這是太慢了（通常如果點的數量是更大然後40000），您可以通過細分指數進一步提高性能排序（將索引排序到尺寸有限的部分頁面，如8192點）

提高tri[]性能

您還可以按tri[i][0]對tri[]進行排序，因此您可以使用類似於pnt[]的二分查找。

Answer 2

我建議用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是對數所以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]]
的3 sets的
2. 獲取路口（不含triangle只拿到。它的旁邊鄰居）
3. 完成

關於獲得旁邊鄰居的複雜性：線性相關關於sets的大小並且與正常情況下的'n'相比相對較小。

注：要獲得不側 -neighbours但點 -neighbours（假設鄰居被稱爲任意2 Triangles與普通Point不Side）只需填寫sets與Points而不是Sides。上述有關時間複雜性的假設對常量保持不變。