將座標點排序到路徑

Question

我給出了一組座標。座標的順序有些隨意，但座標聚集在一起以形成不同的區域。我正在努力創建一個算法，以便按照正確的順序創建各個路徑。我一直在尋找通過尋路和圖像處理解決方案來解決這個問題，但迄今爲止沒有運氣。

座標可以如下所示。

任何人都可以提供一些幫助，創造一個算法將這些座標（以正確的順序）爲路徑排序？

Answer 1

該問題似乎有點具有挑戰性，因爲其中一條路徑實際上由兩個循環組成。在此圖像中它仍然是可行的，如果正確的起始位置選擇，但考慮到這一點：

XXX  XX XXX XXXXX 
    X X X XXX X X  X 
    X X X X X XXXXX X 
    XXX  XX XX X XXXX 
    XXXXXXX   XX 

很容易地看到，在任意路徑，我們將結束與柯尼斯堡*七橋」（順便說一句。 ，這個問題是時下可能的，因爲在橋的數量有些變化，解決...）

至少有兩種可能如何改變的問題，使之可解：

1. 允許穿越相同的路徑不止一次。
2. 僅考慮循環。
3. 只能使用不超過一次遍歷任何點的繪製路徑進行填充。

找到路徑段並不是很具有挑戰性，但將它們組合成循環需要更詳細地定義問題。

---

在路徑查找中，我們需要能夠確定路徑從屬於路徑的單個點開始走向的所有方向。這可以通過考慮像素的所有可能的3×3鄰域來完成。

還有一個額外的要求：如果一條路徑從像素A到相鄰像素B，則必須在這兩條路徑之間存在反向路徑。這個要求縮小了可能性。此外，還有很多對稱性（90°旋轉，鏡像）。

應當注意的是，可能有多達4個近鄰（以下配置）：

.X. X.X 
XXX .X. 
.X. X.X 

在評論中介紹的優先規則上面是一個很好的一個。所以：

• 所有直接鄰國代表從點
• 對角線鄰域代表的路徑，如果他們沒有在他們旁邊

後者規則可以由所示的直接鄰居路徑/ ：

.XX  .N. 
XX. => N . 
..X  ..N 

其中N代表鄰居。

因此，每個點都有一個0..4個相鄰點的列表。鄰近點有類似的列表，所以連接是一對一的。

---

但現在我們有挑戰性的部分。如何將連接信息合併到列表中？

最簡單的情況：

• 如果沒有鄰居（0），點自身形成的路徑
• 如果有一個鄰居，他們屬於同一個路徑
• 如果有是兩個鄰居，所有三個點屬於同一路徑

之後，我們有段和交叉口。以這個答案開頭的例子，我們有：

111  33 666 AAAAA 
    1 1 3 X5X 6 A  A 
    1 1 3 4 7 X8X99 A 
    11X  X4 77 B XAAA 
    2222222   BB 

這裏0..B表示段和X是他們的3或4交叉。

似乎是能夠被用來簡化該結果至少一種有用的規則：

• 如果有一個3交叉，其中兩個分支屬於同一環，它可以連接到一個循環通過啓動旁邊的路徑交叉

在我們的例子中這可以被應用到最左邊的循環：

111  33 666 AAAAA 
    1 1 3 X5X 6 A  A 
    1 1 3 4 7 X8X99 A 
    111  X4 77 B XAAA 
    1111111   BB 

然後對每3交叉，有三種方法來連接它：

 / / / 
    / / /
      / /
    -----  ---  -- | 
     \    \ 
     \  \  \ 
     \  \  \ 

對於每個4交叉有四種不同的可能性：

 |   |   |   | 
         /   \ 
--------- --- --- --- --- --- --- 
          /  \ 
    |   |   |   | 

正如我的圖具有五個3點和一個4交叉，有3^5 x 4 = 972不同的方式來連接這些段。這可以通過詳盡的搜索來完成，但是必須確定哪個解決方案最好。可能需要最小化路徑的數量，但是最大化最長路徑還是最大化最短路徑會更好？或者是其他東西？

還有一些優化的空間，因爲幾種不同的組合段的方式可能會得到基本相同的結果（在3個交叉點處的所有末端的迴路可以運行兩種方式）。

---

總結：

• 找到鄰近連接

  • 所有隔壁的鄰居是鄰居
  • 對角線鄰域是鄰居只是如果沒有隔壁鄰居在他們旁邊

• 易箱子連接成段（0，1，或2個鄰居）

• 創建交叉列表
• 組，以便完全獨立的分段組（獨立的路徑）被單獨處理
• 段消除瑣碎3交點（兩個鄰居屬於同一個網段）通過對其餘口岸的所有可能性
• 搜索，選擇你最喜歡的

的情況下，在曲中所示的結果estion不需要最後一條規則，因爲只有兩個微不足道的3交叉點。

Answer 2

一種解決方案：

• 採取隨機點和雖然當前點具有鄰居從圖像中刪除它
• ，移動到它（新的當前點=鄰居和從圖像中移除）
• 您現在有一系列形成路徑的節點。

重複此操作，直到圖像爲空。您將有一組路徑。