高效地将线段排序成一个循环

Question

我正在使用一个库（JavaScript-Voronoi），它生成代表封闭多边形的线段数组。这些线段是无序的，既包括线段出现的顺序，也包括每个端点的顺序。

_{（编辑：如下评论所述，我错了：库中的线段是有序的。然而，问题仍然按照原文提出：假设线段没有任何顺序，因为这样更具有普遍意义。）}

例如：

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

- Phrogz

---

这个多边形是凸多边形吗？或者说这不是一个合理的要求吗？ - thang

@thang 我相信所有的沃罗诺伊图单元都是凸的，是的。 - Phrogz

对于那些使用 JavaScript-Voronoi 的人来说，我发现你可以通过以下方式非常容易地获取单元格的多边形顶点：cell.halfedges.map(function(he){ return he.getStartpoint() })；尽管我之前所说的，这些边缘实际上已经按逆时针顺序排序了。 - Phrogz

Answer 1

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

如果你只想找到一个凸包，直接使用凸包算法，它是O(n log n)的，足够快，但你也可以在javascript 这里 找到Quickhull算法。quickhull也是O(n logn)，但平均情况下，最坏情况是O(n^2)，但由于较小的常数因子，速度很快。

---

但是对于通用算法的情况：

将每个线段的一端设置为First，另一端设置为second（随机）。

按照它们的第一个x排序，并将其放入数组First中，然后在数组中按照相同第一个x的线段的第一个y排序，并在您的结构中添加两个额外的int来保存具有相同第一个x的项的起始和结束位置。

然后再次根据第二个x值对线段进行排序，... 并创建数组second。

上述操作都是O(n log n)。

现在选择数组中的第一个段落First，在两个数组First和second中搜索其第二个x值，在找到相似值的情况下，在相关子数组中搜索它们的y值（您具有具有相同x的项目的起始和结束位置）。您知道只有一个具有此顺序的段（也不是当前段），因此查找下一个段需要O(log n)，并且因为总共有n-1个下一个段，所以需要O(n logn)（还要预处理），这比O(n^2)快得多。

- Saeed Amiri

Answer 2

应该可以在线性时间内将这些点转换为（双，无序？）链表：

for (var i=0; i<segments.length; i++) {
    var a = segments[i].va,
        b = segments[i].vb;
    // nexts being the two adjacent points (in unknown order)
    if (a.nexts) a.nexts.push(b); else a.nexts = [b];
    if (b.nexts) b.nexts.push(a); else b.nexts = [a];
}

现在你可以迭代它来构建数组：

var prev = segments[0].va,
    start = segments[0].vb, // start somewhere, in some direction
    points = [],
    cur = start;
do {
    points.push(cur);
    var nexts = cur.nexts,
        next = nexts[0] == prev ? nexts[1] : nexts[0];
    delete cur.nexts; // un-modify the object
    prev = cur;
    cur = next;
} while (cur && cur != start)
return points;

如果您不想修改对象，可以使用具有对象键的EcmaScript6 Map。作为解决方法，您可以将点坐标的JSON序列化作为普通对象的键，但是这样会限制多边形不包含重复坐标的情况。或者只需使用库添加到顶点的唯一voronoiId属性来识别它们。

- Bergi

---

这看起来很有前途。请注意，在某些情况下，e1.vb将指向e3.vb，而不是e3.va；我假设这会影响您的算法，我的理解正确吗？ - Phrogz

是的，我在重新阅读你的问题时意识到了这一点。是的，它变得有点更加复杂，但你已经有了想法 :) - Bergi

为了使这个算法适用于其他语言，请澄清“nexts” - 这是指向下一个元素的链表指针吗？即另一个段落元素。 - acraig5075

@acraig5075：不，它是一个包含指向下一个和上一个元素的链表指针的数组。我本可以说“元组”，但那意味着有顺序，而我不知道是下一个和上一个还是上一个和下一个。这是因为“segments”可能或可能不形成一个有向圆。 - Bergi

Answer 3

对于一个凸多边形，你甚至不需要知道边缘线段。你只需要一堆顶点。排序顶点的过程非常简单。

1. 将所有顶点平均在一起，以得到多边形内部的一个点。请注意，这甚至不需要是质心。它只需要是多边形内部的一个点。称此点为C。
2. 对于每个顶点V[i]，计算从V[i]到C的线段与从V[i]到V[i]+(1,0)的线段形成的角度。将其称为a[i]。
3. 使用顶点作为卫星数据对顶点的角度进行排序。

排序后的顶点按照多边形的顺序排列。您可以删除一些冗余。步骤1和步骤2都是线性时间，步骤3是n log n。

- thang

---

有点晚了，但是感谢这个非常好的方法。我在一个 FEM 程序中使用它，解决方案可以在几行代码（用 R 语言）中计算出来。 - Graham G