如何對點進行排序以便它們連接？

Question

我有一個向量對的數組，這些向量都是圍繞多邊形的順時針路徑中的所有邊。問題是，他們沒有按照正確的順序。我想對它們進行排序，以便數組的起點和終點是一樣的載體，和每一個人的一點重疊（端點到起始點）：

require 'matrix' 
unsorted_points = [[Vector[-5, 0], Vector[-3, 2]], 
        [Vector[-3, 2], Vector[3, 2]], 
        [Vector[-3, -2], Vector[-5, 0]], 
        [Vector[3, 2], Vector[5, 0]], 
        [Vector[3, -2], Vector[-3, -2]], 
        [Vector[5, 0], Vector[3, -2]]] 

sorted_points = [[Vector[-5, 0], Vector[-3, 2]], 
       [Vector[-3, 2], Vector[3, 2]], 
       [Vector[3, 2], Vector[5, 0]], 
       [Vector[5, 0], Vector[3, -2]], 
       [Vector[3, -2], Vector[-3, -2]], 
       [Vector[-3, -2], Vector[-5, 0]]] 

什麼是做到這一點的最紅寶石習慣的方法？

編輯：矢量是來自'矩陣'庫的對象，但它們可以像數組一樣索引，例如， unsorted_points[0][0][0]是-5。

Answer 1

首先打開原稿點對陣列到地圖與所述第一點處的鍵，並且所述第二值：

ptsMap = Hash[ * unsorted_points.flatten(1) ] 

=> {Vector[-5, 0] => Vector[-3, 2], 
    Vector[-3, 2] => Vector[3, 2], 
    Vector[-3, -2] => Vector[-5, 0], 
    Vector[3, 2] => Vector[5, 0], 
    Vector[3, -2] => Vector[-3, -2], 
    Vector[5, 0] => Vector[3, -2] } 

然後經由第一點對和鏈從第二點到第一啓動地圖（我注意到您的數組中不包含「點」，它包含兩個點之間的邊緣）：

ordered_edges = (1...unsorted_points.size).inject ([unsorted_points.first]) do |acc,_| 
    nextPt = acc.last[1] 
    acc << [ nextPt, ptsMap[nextPt] ] 
end 

=> [[Vector[-5, 0], Vector[-3, 2]], 
    [Vector[-3, 2], Vector[3, 2]], 
    [Vector[3, 2], Vector[5, 0]], 
    [Vector[5, 0], Vector[3, -2]], 
    [Vector[3, -2], Vector[-3, -2]], 
    [Vector[-3, -2], Vector[-5, 0]] ] 

注意點是在此方面不嚴格的可比性，所以沒有總排序（如需要一個簡單的sort。你的每個點pa irs描述了提供偏序的邊。上面發現候選總排序，假設第一個邊的頭是你想要的第一個點。

如果原始列表實際上並未描述一組離散連接點，則此技術將失敗。使用topological sorting可能會獲得更穩健的結果。 Ruby有這樣一個庫：TSort。有了這個，您可以檢測到原始邊緣集合不是單個強連通的組件。

Answer 2

[編輯：我最初提出了兩種做法，一種是使用排序，另一種是遞歸。 @dbenhur表明沒有sort可以工作，因爲沒有數組元素的完整排序。因此我刪除了這種方法。爲了記錄，我被誤導的心臟是：

unsorted.sort {|v1,v2| (v1 == first || v1[1]==v2[0]) ? -1 : 1} 

第二種方法是使用遞歸。經過思考，它的方式很明顯，我可以做同樣的事情在一個簡單的循環，這是繼]

sorted = [unsorted_points.shift] 
until unsorted_points.empty? 
    node = sorted[-1][1] 
    target = unsorted_points.find {|e| e[0] == node} 
    sorted << unsorted_points.delete(target) 
end 
sorted 
    # => [[Vector[-5, 0], Vector[-3, 2]], 
     [Vector[-3, 2], Vector[ 3, 2]], 
     [Vector[ 3, 2], Vector[ 5, 0]], 
     [Vector[ 5, 0], Vector[ 3, -2]], 
     [Vector[ 3, -2], Vector[-3, -2]], 
     [Vector[-3, -2], Vector[-5, 0]]]