Create rectangles from an array of Coordinates/Points

Question

http://img853.imageshack.us/img853/2475/picture1eu.jpg

I've got an ArrayList of Points/Coordinates which represents a Rectilinear Polygon. I now want to break this shape up into rectangles using the stored Points in my ArrayList.

I've started an algorithm, but I can't finish it and I feel there's got to be an easier way:

The ArrayList is called "allCoordinates".
ArrayList "xMatch" and "yMatch" are subsets of allCoordinates.

Algorithm:

ArrayList yMatch = All matching Coordinates in respect to 'y'

So in the case of this diagram above:
(Set 1=[x1, y1]-[x8, y8],
Set2=[x7, y7]-[x2, y2],
Set3=[x4, y4][x5, x5],
Set4=[x3, y3][x6, x6])

ArrayList xMatch = All matching Coordinates in respect to 'x'

So in the case of this diagram above:
(Set 1=[x1, y1]-[x2, y2],
Set2=[x3, y3]-[x4, y4],
Set3=[x5, y5][x6, x6],
Set4=[x7, y7][x8, x8])

So now I have two arrayLists, all vertical Edges and all horizontal Edges. Now I need some way of checking whether they all connect together? Like I said there's got to be an easier way...?

Edit:

Can I just clarify that the rectangles have to be formed from using intersecting lines that start and finish on existing coordinates. For example, a line could be drawn from (x6, y6) horizontally and finish on edge (x1,y1)-(x8,y8). This line would start from an existing coordinate, however it wouldn't finishing on an existing coordinate. Therefore the line would be invalid.

Answer 1

As you may have noticed by now, I keep coming back to this problem. Partly because I like to puzzle out these kinds of problems, but also because it annoyed me a little that I couldn't find an elegant algorithm for something that seems so easy.

Well, don't be fooled, this is not a trivial problem that you can solve with some simple point manipulation, although it certainly looks that way. Part of the reason for this is that, although you think you're only working with points, you're implicitly also manipulating line segments and the areas enclosed by them, which also have their own constraints (i.e. the segments should always form one or more closed chains, and cannot intersect except at the vertices we define them with).

Also, your algorithm has to work for any kind of input you feed it. That is, it is not allowed to produce no answer or a wrong answer just because the polygon you fed it is oriented in a way that your algorithm doesn't like.
What you can do however, is restrict the type of input that your algorithm accepts. Requiring that the input polygon contains only axis-aligned segments is therefore perfectly valid.
(The difference between "oriented the wrong way" and "only axis-aligned segments" is that the first is a vague criteria that cannot be determined without testing it on the algorithm - whereas the second requirement can).

To recapitulate, we're looking for a way to horizontally partition any rectilinear polygon (i.e. consisting of only axis-aligned line segments) into rectangles.

Example of a rectilinear polygon

Here's the plan:

1. Pick our building blocks
2. Allow extra vertices
3. Aligning on a grid.
4. Working with unequally-sized grid cells.
5. Which cells are inside your polygon?
6. Constructing rectangles.

Pick our building blocks

Even though these are implementation details, getting this clear up front might help you getting a better picture of how the algorithm works.

In code, we'll be using the objects of the following types as basic building blocks to represent our polygon with:

• Point, consisting of an x and y coordinate. (e.g use Point2D.Double)
• Segment, consisting of a start and end Point (e.g. use Line2D.Double)
• Polygon, consisting of a closed chain of Segments (e.g. use an ArrayList of Line2D.Double), where one segment ends on the same point as the starting point for the next segment.

Also, we'll be using a grid, which can be modelled as a 2-dimensional array.

Allow extra vertices.

You stated that "the rectangles have to be formed from using intersecting lines that start and finish on existing coordinates.". However, observe that most rectilinear polygons cannot be partitioned into rectangles by only using the existing vertices - see the example above (as well as the caravan examples you provided earlier).

Hence, this constraint will have to go - even though we won't actually be creating new vertices explicitly.

Aligning on a grid.

Thought experiment: What if your polygon existed only of (axis-aligned) segments of length 10, 20, 30 or 40... i.e. multiples of 10? We could then project our polygon on a grid, and use the grid cells that lie inside the polygon to compose the rectangles with. Also, determining the dimensions of these rectangles would be a breeze: just count the number of horizontally consecutive cells that lie inside the polygon and multiply by 10; that's your width.

Grid-aligned polygon

Good idea, except:

• The polygon doesn't consist of only segments of same-or-multiple length
• How do we determine which grid cells lie inside the polygon?

We'll tackle each of these problems next.

Working with unequally-sized grid cells.

If you think about it, there is no real reason for all the grid cells to have the same width and height. Hence, we can devise a grid that is spaced in such a way that our polygon aligns perfectly onto it.

To get the widths of the grid's horizontal axes:

• Collect all x-coordinates of the vertices of which the polygon is composed.
• De-duplicate and sort them on increasing value.
• The difference between two subsequent values then define the width of that column.

Grid aligned to the polygon

Obviously, the cell's heights can be determined in the same way. You should determine these widths and heights, and store them into two arrays called gridWidths and gridHeights, respectively.

Now that we know the number of cells and their dimensions, we can start modelling the grid contents.

Which cells are inside your polygon?

Remember that our polygon is stored as a chain of line segments. To determine if a grid cell lies inside this polygon we can use the even-odd rule: Construct a line segment from outside* the polygon to the center of the cell we want to test, and count the number of intersections between this line segment and the segments of the polygon (i.e. use Line2D.Double's intersectsLine() method). If the number is even it lies outside the polygon, if it is odd it is inside the polygon.

*- It's best to construct only horizontal line segments between center of the cells (as shown in the example), so that you don't risk intersecting the segment endpoints - this may could count as 0 or 2 intersections, messing up your count total.

So, we will model this grid as grid, a 2-dimensional array of booleans. Process each cell of the grid this way, and mark the corresponding spot in grid as either true (inside polygon) or false (outside polygon).

Inside (T) or outside(F) based on the even-odd rule

Constructing rectangles.

Now that we have grid representation of the polygon, as well as the actual widths and heights of each cell, we can start constructing rectangles. I will assume that you're only interested in the widths and heights of each rectangle, and not in the actual vertex coordinates that form the rectangle (although that is now easy too).

Foreach row in grid
  run_start = null
  Foreach cell C in row
    if C is marked as true and run_start = null
      //Found the start of a new run
      run_start = C
    else if C is marked as false and run_start != null
      //Found the end of a run
      The cells [run_start...C] form a horizontal rectangle.
      Use the gridWidths and gridHeights arrays to determine the 
      dimensions, and report this rectangle as a result
      
      //Prepare for the next run
      run_start = null

The polygon, partitioned into rectangles.

Note that the two rectangles in the top left share the same starting and ending x-coordinates, and could therefore be considered as one rectangle. If you wanted, you could implement an additional pass that merges these type of rectangles.

Conclusion

By mapping the rectilinear polygon onto a grid, we can easily partition it horizontally in rectangles without having to resort to more advanced geometric data structures.
Note that there are some optimizations possible to make this algorithm run faster, but I don't think it really matters for the current input sizes, and it would make the implementation more difficult.