3

我正在使用一个库（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;
}
4

3 回答 3

3

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

如果你只是想找到一个凸包，直接使用凸包算法，它是 O(n log n)，速度足够快，但你也可以在 javascript 中找到一个 Quickhull 算法here。quickhull 也在 中O(n logn)，但平均而言，最坏的情况是 O(n^2)，但它的速度很快，因为常数因素较少。

但在一般算法的情况下：

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

按第一个对您的段进行排序，x然后将其放入数组中，然后在数组中按第一个对具有相同第一个的First段进行排序，并将两个额外的部分放入您的结构中以保存具有相同 first 的项目的开始和结束位置。xyintx

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

以上动作都在 O(n log n) 中。

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

于 2013-01-10T10:08:44.307 回答
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;

如果您不想修改对象，EcmaScript6Map（带有对象键）会派上用场。作为一种解决方法，您可以使用点坐标的 JSON 序列化作为普通对象的键，但是您将被限制为不包含两次坐标的多边形。voronoiId或者只是使用您的库添加到顶点的唯一属性来识别它们。

于 2013-01-10T06:43:42.757 回答
2

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

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

排序的顶点在多边形周围是有序的。您可以删除一些冗余。1 次以线性时间运行，2 次以线性时间运行，3 次以 n log n 运行。

于 2013-01-10T18:15:27.703 回答