從頂點參考曲面的圖形中識別體積

這裏有一個問題，在過去的幾天裏一直困擾着我 - 我的同事認爲這是一個經過深入研究的問題，但我在網上找不到任何論文（可能是我用的關鍵詞是不正確的）。給定一個圖，其中每個頂點對應於一個曲面，並且如果相應的曲面在一條線上相交，則兩個頂點之間存在邊，我該如何確定組合形成閉合曲面的曲面？從頂點參考曲面的圖形中識別體積

因此，舉例來說，多維數據集的鄰接表（用編號爲1至6面）可能是這個樣子：

1 -> [4,2,5,6] 
2 -> [1,3,5,6] 
3 -> [2,4,5,6] 
4 -> [3,1,5,6] 
5 -> [1,2,3,4] 
6 -> [1,2,3,4]

除了這個信息，我也知道一些表面具有自由邊緣（即那些邊緣不與任何其他表面共享），這意味着我可以立即排除這些表面，因爲具有自由邊緣的表面不能成爲腔邊界的一部分。此外，如果兩個表面相遇，它們將在邊界處乾淨地相遇 - 不會發生一些打擊等。

我希望能夠做的不僅僅是識別存在腔體，還要輸出表面與它們包含的空腔。例如，在其中在邊緣滿足兩個立方體的情況下（沒有足夠的聲譽後的圖像，所以這裏的一個側面視圖）：

----------- 
|   | 
|   | 
|   | 
--------------------- 
      |   | 
      |   | 
      |   | 
      -----------

...這將是所希望的輸出假定表面1- 6彌補立方ONE和7-12組成的立方體二：

Volume 1 -> [1,2,3,4,5,6] 
Volume 2 -> [7,8,9,10,11,12]

需要注意的是，在這種情況下，一些表面具有在圖形SIX鄰居而有的只有四個鄰居。

任何幫助將不勝感激！

來源

2013-11-01 user37769

看起來像一個家庭作業或面試問題。你到達了多遠？任何代碼，算法？ –

我到達了多遠？我唯一能夠弄清楚的是具有自由邊的表面應該被丟棄。我簡要地考慮了循環識別 - 但反例很容易找到。至於這是一個家庭作業或面試問題，我不在學校，我現在不在找工作，所以不，這不是。 – user37769

是的，這個區域被稱爲計算拓撲。它的中心對象是循環的代數組，稱爲同源組（H1當循環由1-dim邊形成時，H2當我們談論2-dim時面）。

可以通過形成同源組矩陣來分析這樣的組。對於一些查詢，需要H1和H2矩陣。

當矩陣可以重新排列成獨立塊時，意味着形狀不會相互影響。當單塊同源矩陣具有N級時，意味着形狀具有N個空穴（空穴）。簡單形狀像立方體有0個孔，圓環面有1個等。

可以找到用於這些計算的C++和MATLAB開源軟件包。

希望它提供了一些有用的關鍵字。

來源

2013-11-02 19:27:41

Michael，謝謝你！一定會看這個！ – user37769

不客氣。我知道這個題目很粗糙，你可以如何爲一個簡單的圖形建立同源矩陣（本質上是關聯矩陣）[這裏]（http://www.math.nmsu.edu/~pmorandi/math683f00/GraphHomology.pdf）。這個矩形矩陣的等級告訴了很多關於圖結構。類似的矩陣可以建立面向邊緣的發生等，他們的排名會告訴關於洞的故事。（順便說一句，如果你喜歡這個答案，你可以將它標記爲「已接受」和/或「註銷」它;將不勝感激） –

從頂點參考曲面的圖形中識別體積

回答

相關問題