CODEWITHSUNDEEP
javascriptalgorithm
Phrogz
Phrogz

Reputation: 303440

Efficiently ordering line segments into a loop

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.)

For example:

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.

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.

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

Upvotes: 3

Views: 1698

Answers (3)

thang
thang

Reputation: 3466

For a convex polygon, you don't even need to know the side segments. You just need a bunch of vertices. The procedure to order the vertices is pretty simple.

  1. average all the vertices together to get a point inside the polygon. note that this doesn't even need to be the centroid. it just needs to be a point inside the polygon. call this point C.
  2. for each vertex V[i], compute the angle the line segment from V[i] to C forms with the line segment from V[i] to V[i]+(1,0). call this a[i].
  3. sort the angles of vertices using the vertices as satellite data.

the sorted vertices are in order around the polygon. there are some redundancies that you can remove. 1 runs in linear time, 2 runs in linear time, 3 runs in n log n.

Upvotes: 2

Bergi
Bergi

Reputation: 665316

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;

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.

Upvotes: 2

Saeed Amiri
Saeed Amiri

Reputation: 22565

If your polygon is convex, you can pick middle point of each line segment, then use convex hull algorithm to find convex polygon by middle items, after that, because you know what is the arrangement of middles and also you know which middle belongs to which segment, you can find an arrangement in original array.

If you just want to find a convex hull, use convex hull algorithm directly, it's O(n log n), which is fast enough, but also you can find a Quickhull algorithm in javascript here. quickhull is also in O(n logn), but in average, the worst case is O(n^2), but it's fast because of less constant factor.

but in the case of general algorithm:

Set one end of each segment as First, and another end as second (randomly).

Sort your segments by their first x and put it in array First after that in array first sort segments with same first x by their first y and put two extra int into your structure to save start and end position of items with same first x.

Then again sort your segments with the second x value, .... and make array second.

Above actions both are in O(n log n).

Now pick first segment in array First, search for its second x value in both arrays First and second, in the case you find similar values, search for their y values in related subarray (you have start and end position of items with same x). You know there is only one segment with this order (also is not current segment), so finding next segment takes O(log n) and because in all there is n-1 next segment it takes O(n logn) (also preprocessing), which is extremely faster than O(n^2).

Upvotes: 3

Related Questions