高效订货线段成一个圈 [英] Efficiently ordering line segments into a loop

问题描述

我使用的库（ JavaScript的沃罗诺伊），它产生的线段组成的数组那些重新present一个封闭的多边形。这些段出现无序的，两者的顺序段出现以及点的段的每个端部的顺序。

I'm using a library (JavaScript-Voronoi) which produces an array of line segments that represent a closed polygon. These segments appear unordered, both the order in which the segments appear as well as the ordering of the points for each end of the segment.

<子>的（修改：正如评论指出下面，我错了：从库段的是秩序井然然而，问题站作为书面：让我们假定该链段不具有任何顺序，因为这使得它更普遍有用）的

_{(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 } ];

注意如何第一段链接到最后（它们共享一个公共点），以及到下一个到最后一个。这是保证每一个片段股正好一个其它部分的结束。

Notice how the first segment links to the last (they share a common point), and to the next-to-last. It is guaranteed that every segment shares an end with exactly one other segment.

我想转换成点的列表，这产生适当的SVG多边形：

I would like to convert this into a list of points to generate a proper SVG polygon:

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

有无关紧要点是否在顺时针或逆时针顺序

It doesn't matter whether the points are in clockwise or counter-clockwise order.

下面code是我想出来的，但在最坏的情况下将采取 N ^ 2 + N 点比较。有没有更有效的算法用于连接所有这些结合在一起？

The following code is what I've come up with, but in the worst-case scenario it will take n^2+n point comparisons. Is there a more efficient algorithm for joining all these together?

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

推荐答案

有应该是可能的转动点到（双，无序？）链表线性时间：

It should be possible to turn the points into a (double, unordered?) linked list in linear time:

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

现在，你可以迭代它建立数组：

Now you can iterate it to build the array:

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 地图 （具有对象键）会派上用场。作为一种解决方法，你可以使用你的观点的JSON序列化坐标为普通对象的钥匙，但你再局限于多边形不包含坐标的两倍。或者只是使用了独特的 voronoiId 属性，您的库添加到顶点识别它们。

If you do not want to modify the objects, an EcmaScript6 Map (with object keys) would come in handy. As a workaround, you could use a JSON serialisation of your point coordinates as keys of a normal object, however you are then limited to polygons that do not contain a coordinate twice. Or just use the unique voronoiId property that your library adds to the vertices for identifying them.

这篇关于高效订货线段成一个圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！