How to create closed areas (convex polygons) from set of line segments ?

Question

The following problem is in 2D, so some simplifications can be made when suggesting answers.

I need to create closed areas (defined either by line segments or just set of points - convex polygon) from a set of points/line segments.

Basically I used Voronoi to generate "roads". Then I changed some of the data. Now I need a way to loop through that data (which is still line segments but doesn't comply with Voronoi anymore) and generate "neigbourhoods" that are bordered with the "roads".

I looked at some graph diagrams and shortest path theories, but I could not figure it out.

Logically it could be done by starting at left edge from one point, finding the way back to that point using the shortest path with available lines (using only clockwise directions). Then mark this line set down and remove from the data. Then you can repeat the same process and get all the areas like that.

I tried to implement that but it did not get me anywhere as I could not figure out a way to write a C++ code that could do that. Problem was with choosing the most counterclockwise line from available lines from a specific point. All angle based math I did gave wrong answers because the way sin/cos are implemented in c++.

So to summarize - if you can help me with a totally new approach to the problem its good, if not could you help me find a way to write the part of the code that finds the shortest clockwise path back to the beginning point using the line segment set as paths back.

EDIT: Added a picture to illustrate what I want to do.

Check the image here - (need 10 reputations before I can post it here :P)

I have a set of points (purple small dots). Another array defines what points make up a line (road). I want a way to define the area that is surrounded by roads so I can put buildings or smaller roads inside that and test against the edges so every region is separated. Hope this gives you more info on how to solve this problem.

Thank you for your help!

Answer 1

Your idea to follow the line segments along the shortest path (e.g. follow the most clockwise one if you have multiple choices) is good.

And you can find this line without any sin/cos calls.

The idea goes like this:

Assume that you have two lines to choose from. Call the point where the lines meet A (e.g. your current position). The endpoints of your two lines are called B and C.

These three points build a triangle. Now take a look how the three points are oriented. If you follow the points from A to B to C the direction will either be clockwise or counter-clockwise. Obviously if the order is clockwise, the line that goes from A to C will be the most clockwise one. Otherwise it's the line that goes from A to B.

If you have more than two lines to choose from just pick the first two, discard the line that goes into the wrong direction and do the same test until you end up with a single line. That's the most clockwise one.

Now about the math: how do you find out the winding-order of three points without calling sin/cos or even worse: atan:

You can do this with the cross product. First build two vectors that give you the direction from A to B and from A to C:

   u.x = B.x - A.x
   u.y = B.y - A.y

   v.x = C.x - A.x
   v.y = C.y - A.y

Now we can calculate the signed area of the parallelogram spawned by these two vectors:

   signed_area = (u.x * v.y) - (u.y * v.x);

The winding is the sign of the area. e.g.

  if (signed_area > 0)
  { 
     // order is clockwise. Pick Line B
  }
  else if (signed_area < 0)
  { 
     // order is counter-clockwise. Pick Line A
  }
  else 
  {
    // the lines are colinear.
  }

Note: I haven't tied the code and the decision on the sign could be exactly the other way around. That's a detail of the math that I will never get into my head. I always have to try it out with known data.

Answer 2

It sounds like you want to partition the some region into non-overlapping convex polygons. If I'm understanding you correctly, you can't just toss segments after using them to form a polygon, because each internal segment will border on two polygons.

Instead, you should have two flags for each segment, for whether you have built a polygon to the segment's "left" and "right". If you have a bordered area, the border segments need to have their "outer" side flag set to start with since you don't want to use that side in a polygon. Then find segments with either flag unset, and use Nils's answer to work your way around the polygon. Some segments will be "reversed"; if you're going clockwise, you want to set the 'left' flag on the 'forward' segments and the 'right' flag on the 'backward' ones, and vice versa. (You can build all the polygons in one order, it just doesn't matter which you choose.) Note that the first segment can be interpreted as either depending on which of its flags you need to set. When all segments are flagged in both directions, you are done.

If you're partitioning the plane rather than a bounded region, some segments will be rays; you'll also need some special code to connect rays that are adjacent when sorted by slope into fake "polygons".

Pseudocode for the bounded case:

foreach seg in boundary segments {
    if left of seg is outside region {
         seg.leftDone = true
    } else {
         seg.rightDone = true
    }
}
while any seg.leftDone or seg.rightDone is false {
    seg = pick a segment with either flag unset
    start = seg
    polygon = new Polygon()
    reversed = not start.rightDone
    do {
        if reversed {
            seg.rightDone = true
            endpoint = seg.start
            polygon.addSegment(seg.reverse())
        } else {
            seg.leftDone = true
            endpoint = seg.end
            polygon.addSegment(seg)
        }

        next = findNextClockwiseSeg(seg, endpoint); // Nils's answer works

        seg = next
        reversed = (seg.end == endpoint)
    } while start != seg;
    result.addPolygon(polygon)
}