有效地将线段排序成循环

我正在使用一个图书馆（JavaScript-Voronoi https://github.com/gorhill/Javascript-Voronoi），它生成表示闭合多边形的线段数组。这些线段显示无序，无论是线段出现的顺序还是线段每端点的顺序。

_{(Edit: As noted in a comment below, I was wrong: the segments from the library are well-ordered. However, the question stands as written: let's assume that the segments do not have any ordering, as this makes it more generally useful.)}

例如：

var p1 = {x:13.6,y:13.1}, p2 = {x:37.2,y:35.8}, p3 = {x:99.9,y:14.6},
    p4 = {x:99.9,y:45.5}, p5 = {x:33.7,y:66.7};
var segments = [
  { va:p1, vb:p2 },
  { va:p3, vb:p4 },
  { va:p5, vb:p4 },
  { va:p3, vb:p2 },
  { va:p1, vb:p5 } ];

请注意第一个片段如何链接到最后一个片段（它们共享一个公共点）以及倒数第二个片段。保证每个段与另一个段恰好共享一端。

我想将其转换为点列表以生成正确的 SVG 多边形：

console.log( orderedPoints(segments) );
// [
//   {"x":33.7,"y":66.7},
//   {"x":13.6,"y":13.1},
//   {"x":37.2,"y":35.8},
//   {"x":99.9,"y":14.6},
//   {"x":99.9,"y":45.5}
// ]

这些点是按顺时针顺序还是逆时针顺序并不重要。

以下代码是我想出的，但在最坏的情况下，它需要n^2+n点比较。是否有更有效的算法将所有这些连接在一起？

function orderedPoints(segs){
  segs = segs.concat(); // make a mutable copy
  var seg = segs.pop(), pts = [seg.va], link = seg.vb;
  for (var ct=segs.length;ct--;){
    for (var i=segs.length;i--;){
      if (segs[i].va==link){
        seg = segs.splice(i,1)[0]; pts.push(seg.va); link = seg.vb;
        break;
      }else if (segs[i].vb==link){
        seg = segs.splice(i,1)[0]; pts.push(seg.vb); link = seg.va;
        break;
      }
    }
  }
  return pts;
}

如果你的多边形是凸的，你可以选择每条线段的中点，然后使用凸包 http://en.wikipedia.org/wiki/Convex_hull算法通过中间项找到凸多边形，之后，因为你知道中间项的排列是什么，也知道哪个中间项属于哪一段，所以你可以在原始数组中找到一个排列。

如果你只是想找到一个凸包，直接使用凸包算法，它是O(n log n)，这已经足够快了，而且你也可以在javascript中找到一个Quickhull算法here http://en.literateprograms.org/Quickhull_%28Javascript%29。快船也在O(n logn)，但平均而言，最坏的情况是 O(n^2)，但由于常数因子较少，因此速度很快。

但在一般算法的情况下：

将每个段的一端设置为第一端，另一端设置为第二端（随机）。

按第一个细分对您的细分进行排序x并将其放入数组中First之后在数组中首先对具有相同第一个的段进行排序x由他们的第一个y并额外放两个int进入您的结构以保存具有相同第一个项目的开始和结束位置x.

然后再次用第二个对你的片段进行排序x值，....并制作数组second.

上述动作的复杂度都是 O(n log n)。

现在选择数组中的第一个段First, 寻找第二个x两个数组中的值First and second，如果您发现相似的值，请搜索它们y相关子数组中的值（您具有相同项目的开始和结束位置x）。您知道只有一个段具有此顺序（也不是当前段），因此查找下一个段需要O(log n)因为在一切之中都有n-1下一段需要O(n logn)（也是预处理），这比O(n^2).