Separate 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 look at the images above, you can see that they consist of one large rectangle, divided into smaller rectangles, in pairs of user-defined coordinates (each pair in the image samples is identified with a different color).

What I'm trying to do is get the coordinates of these rectangles, only defining the joins. Edges are considered as explicit associations. The order does not matter.

Does anyone know the name of the algorithm that does this (I'm sure it's there with a fancy name!) Or is there an example code in C #? I have been struggling to do this myself for a while, but I have little success. Another common math fails!

Update:
Just thought that I would quickly update this question based on the comments I received.

• The lines must be straight, so each pair of coordinates will be aligned on one axis
• Coordinates must begin either at the edge or at the intersection of another pair. The second coordinate should end in the same way. Any "orphan" coordinates that do not start / end each other are illegal, and I must ignore them at the moment, binding should be possible as soon as I finally get my head.
• Although in this example all the pairs divide the rectangle more or less neatly, in practice this will not be the case, and there may be many lines creating large rectangles.

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

Answer 1

What you are trying to calculate is known for the location of the line segments . (This is not a very good name, but it looks like the name we are stuck for!) To calculate it:

• Find the set of intersections (all points where two segments correspond or intersect). This can be calculated using the Bentley-Ottmann algorithm . If there are n segments and k intersections, this takes O ((n + k) log n). (But if you have only a few line segments, it is probably best to use the simple O (n ² ) algorithm.)

• With a little extra accounting, you can record which edges were incidents at each intersection, and therefore calculate a planar straight line chart (PSLG) that matches your set of line segments.

• Transform PSLG into a quad-core data structure . It takes two steps. First, find the border connections in the data structure by arranging the edges incident to each vertex by an angle.

• Select an edge that is not yet connected with two faces, create a face on the unbound side and go along the border of this face connecting it to each edge in turn. Repeat until each edge is joined to two faces.

In the general case, this leads to the fact that faces other than rectangles (even if all segments of the line are aligned along the axis, and all intersections have integer coordinates), but perhaps this does not happen in your application or you can refuse non-rectangular facets.

Answer 2

The answer implies the following rule, which, in my opinion, is necessary in any case:

The user can only split an existing rectangle using a horizontal or vertical line.

This means that in your first example, the division order should be:
Brown, yellow, blue.

For any rectangle class you use, define two extension methods: SubdivideHorizontal and SubdivideVertical , which will take the coordinate of the subsection and return two resulting division rectangles.
For each rectangle that you split, replace it with two resulting dividing rectangles and repeat recursively for all divisions.

Answer 3

I would do the following.

• Create a point on each of the outer 4 corners.
• Create a point at each user-defined point.
• Create a point when the line crosses an empty point.
• Go through each square and check if there is a point at all four corners.