Divide up a rectangle based on pairs of points

Question

Example http://xthlegion.co.uk/images/dividerectangle.png Example http://xthlegion.co.uk/images/dividerectangle2.png

If you consider the images above, you can see they are comprised of a single large rectangle broken down into smaller rectangles by pairs of user defined coordinates (each pair in the example images are identified with a different color).

What I'm trying to do is obtain the co-ordinates of those rectangles by only defining the joins. Edges are treated as explicit joins. Order doesn't matter.

Does anyone know the name of the algorithm that does this (I'm sure there's one with a fancy name!) or have some example C# code? I've been struggling trying to do this myself for a while now but am having little success. Yet another total math fail!

Update:
Just thought I'd quickly update this question based on the comments I've received.

1. Lines must be straight, so each pair of co-ordinates will align on one axis
2. Co-ordinates must start from either an edge, or the intersection of another pair. The second co-ordinate must end in a similar fashion. Any "orphan" co-ordinates which don't start/end one another join are illegal and I should ignore them for now, snapping should be possible once I finally get my head in gear.
3. Although in this example all the pairs more or less neatly divide the rectangle, this will not be the case in practice and there could be many lines creating rectangles of many sizes.

2nd Update - it works :)
Example http://xthlegion.co.uk/images/dividerectangle3.png

Answer 1

What you are trying to compute is known an arrangement of line segments. (It's not a particularly good name, but it seems to be the name we're stuck with!) To compute it:

1. Find the set of intersections (all points where two line segments meet or cross). This can be computed by the Bentley–Ottmann algorithm. If there are n line segments and k crossings, this takes O((n + k) log n). (But if you only have a few line segments, it's probably better to use the simple O(n²) algorithm.)

2. With a bit of extra book-keeping you can record which edges were incident at each intersection, and so compute the planar straight-line graph (PSLG) corresponding your set of line segments.

3. Convert the PSLG to a quad-edge data structure. This takes two steps. First, find edge—edge connections in the data structure by ordering the edges incident to each vertex by angle.

4. Choose an edge that isn't yet connected to two faces, create a face on the unconnected side, and walk around the boundary of that face connecting it to each edge in turn. Repeat until every edge is connected to two faces.

In general, this results in faces other than rectangles (even if all the line segments are axis-aligned and all intersections have integer coordinates), but maybe in your application this doesn't happen, or you can discard the non-rectangular faces.