算法：從地圖上的點創建線段

Question

我想知道現在有一個算法或一種方法來做到這一點： 我有許多代表道路位置的2D點（比方說x，y）。每條道路可以採取不同的方向和「分裂」。我只需要生成分段之前的段。與圖片更好地解釋：

這是我的觀點

而這些都是3個區段產生

我想用樣條插值但不會對工作這和Ant Colony在這裏可能不會有多大幫助，因爲他們可能會採取捷徑。 有沒有辦法做到這一點，如果是的話，你會怎麼做？

Answer 1

我可以想到兩種方法來解決這個問題，包括一個一個尋找衣櫃。

第一種方法將涉及沿任一軸對點列表進行排序，然後從第一個點開始，通過點向前搜索，測量之間的距離。以Pn爲第n個點，我們可以說最接近P1的點最多是從P1到P2的距離。那麼我們就可以在最遠的地方搜索排序後的數組，如果我們遇到另一個更接近的點，比如說P4，我們會將搜索距離縮短得更遠。一旦找到最近的點，在兩者之間畫一段，然後繼續點P2。你可能會優化一些存儲有關P1和P2的相對位置的信息，然後自動跳過你比較P1的一些元素，因爲你已經知道它們不是P2的最佳解決方案。

我能想到的另一種方法是使用四叉樹。將整個網格劃分爲4個正方形，如果這些正方形中的任何一個包含超過1個元素，則將它們也劃分爲4個正方形，然後重複，直到每個正方形包含0或1個元素。然後看看包含這些單個正方形（僅包含1個元素）的正方形，然後比較最近的鄰居。現在，這意味着你將不得不手動檢查與正在搜索的方塊直接相鄰的方塊，因爲它可能位於一個邊界上（想象一個剛剛在網格上方的1/2上方，一個剛好在1/2以下），並且在「展開」回到最初的網格原始方塊之前，您不會找到其他點。這個解決方案對我來說編程會有點困難，但在密集的地圖中可以肯定會更快。