ruby - 如何对点对进行排序以便它们连接？

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]]]

执行此操作最符合 Ruby 习惯的方法是什么？

编辑:向量是来自“矩阵”库的对象，但它们可以像数组一样被索引，例如unsorted_points[0][0][0] 是 -5。

Answer 1

首先把原来的点对数组变成一个 map ，第一个点是键，第二个点是值:

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] }

然后从第一个点对开始，通过 map 从第二个点链接到第一个点(我注意到你的数组不包含“点”，它包含两点之间的边):

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]] ]

请注意，在这种情况下，点并不是严格可比的，因此没有全序(简单的排序需要)。每个点对都描述了一条提供部分排序的边。假设第一个边缘的头部是您想要的第一个点，上面找到了一个候选总排序。

如果原始列表实际上没有描述一组离散的连接点，则此技术将失败。使用 topological sorting 可能会得到更可靠的结果. Ruby 有一个库:TSort .有了这个，您可以检测到您的原始边集何时不是单个强连接组件。