算法從節點和關係

Question

我有他們之間的節點和線路的列表塊產生，它看起來像這樣：

我需要的是產生塊，在這種情況下，它會像這樣的： 塊1：1,2,14,11 塊2：2,13,12,14 塊3：2,3,4,5,6,12,13 塊4：6,7,12 等。

Doeas有人有任何想法如何爲此創建算法？ thx

Answer 1

您可以先將每個節點的邊緣按順時針順序排序。 （例如，根據關鍵字atan2（dy，dx）進行排序，其中dx，dy是沿邊緣的向量）

然後以每條邊（以及沿邊的兩個方向）爲起點，繞着這些街區向左轉。

要按照逆時針方向進行操作，可在排序列表中找到目標節點的傳入邊沿，然後沿列表中的下一個邊沿退出。例如，如果您從邊11→14開始，那麼當您到達節點14時，您將知道接下來的邊14→2（因爲節點14的邊將按照順時針順序14→12,14→11,14→2）。當你到達起始節點時，你已經識別出一個塊。

您可以將邊緣標記爲跟隨它們時使用的邊緣，以避免產生兩次相同的塊。 （如果它們已經被標記爲在該方向上使用，則跳過起始邊緣）。

這也會生成由背景區域組成的塊0。

Answer 2

在我看來，你正試圖生成一個平面圖的對偶。

http://en.wikipedia.org/wiki/Dual_graph

可能是一個良好的開端。