高效订货线段成一个圈 [英] 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屋!