CODEWITHSUNDEEP
c#algorithmmath
Richard Moss
Richard Moss

Reputation: 1620

Divide up a rectangle based on pairs of points

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

Upvotes: 8

Views: 1999

Answers (3)

Gareth Rees
Gareth Rees

Reputation: 65854

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

Upvotes: 5

Rotem
Rotem

Reputation: 21917

The answer assumes the following rule, which I believe is a necessity in any case:

The user may only subdivide an existing rectangle using a horizontal or vertical line.

This means that in your first example the order of subdivision would have to be:
Brown, yellow, blue green.

For whatever rectangle class you're using, define two extension methods: SubdivideHorizontal and SubdivideVertical, which will accept the coordinate of subdivision, and will return the two resulting rectangles of the subdivision.
For each rectangle you subdivide, replace it with the two resulting subdividing rectangles and repeat recursively for all subdivisions.

Upvotes: 2

Joel Kravets
Joel Kravets

Reputation: 2471

I would do the following.

  1. Create a point on each of the outer 4 corners.
  2. Create a point on each user defined point.
  3. Create a point whenever a line crosses over an empty point.
  4. Run through each square and check if there is a point on all four corners.

Upvotes: -1

Related Questions