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

I found a solution but its probably not the most optimal.




So here we have our coordinates and my two ArrayLists mentioned earlier - xMatch and yMatch.

xMatch = ArrayList of Coordinates pairs with matching x-coordinates
yMatch = ArrayList of Coordinates pairs with matching y-coordinates

I made a class called "Point2Point" which saves two lots of coorindates in a specific order. Both xMatch and yMatch are of the "Point2Point" type. Like any vector the order is important. The order I used was:

Point1 = starting point
Point2 = finishing point.

So now using a "for" loop I matched an element from xMatch with an element from yMatch in respect to Point1 (the starting point). Pairing these up would give you the following shape:

Now this diagram you can see that in order for these two vectors to be part of a rectangle the coordinate (?, ?) must exist. Using the properties of a rectange I know that (?, ?) is equal to (yMatch.Point2.x, xMatch.Point2.y) or in respect to this diagram (x3, y2).

So now that I know which coordinates to look for I can search my ArrayList "allCoordinates" to see whether this coordinates exists. If it does - I have a rectangle, if not - its a dud!!

Answer 2

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.

Answer 3

Note: I'm not going for a theoretically optimal solution here, but just for an approach that produces the correct answer and works fast enough on an input polygon of say 100 vertices. Also, special cases such as an input polygon with holes in it are not considered now. Also, polygons that are not x-monotone* need pre-processing which I won't discuss yet.
*Meaning: starting at any leftmost position in P, you can reach any other position by moving up, down or right, but without ever going left.

Assumptions
As stated in your earlier post, part of the question is in which direction to lay the decking boards (or "rectangles") in order to minimize the number of decking boards used. I will assume that your input polygon P will consist of mostly axis-aligned segments, so that the choice in direction is reduced to either horizontal or vertical. For the remainder, I will assume that a single decking board is always oriented vertically (i.e. runs from top to bottom). For calculating the result with horizontal decking boards, just rotate P by 90 degrees.

Problem statement
We'll be trying to cover P with decking boards, each with an unlimited length and a maximum width of W. More specifically, we're looking for a coverage that minimizes the total length of all decking boards used. The parts of the used decking boards that fall outside P (i.e. the wastage) cannot be used to cover other parts of P. In order to minimize the wastage, it makes sense to align either the left or the right border of a decking board against a vertex of P, or to place a decking board right next to another decking board.

Solution
The first step towards this is to partition P into a collection of vertical slabs: take the distinct x-coordinates of all vertices in P and sort them: each pair of consecutive x-coordinates then defines a slab S of P.

Next recognise that, for each slab S, we have 4 possible ways to align the (one or more) decking boards to it:
* (SL) Start Left, i.e. align the left side of the decking board with the left side of the slab.
* (CL) Continue Left, i.e. continue the pattern of decking boards as determined by the slab to the left of it.
* (CR) Continue Right, i.e. continue the pattern of decking boards as determined by the slab to the right of it.
* (SR) Start Right, i.e. align the right side of the decking board with the right side of the slab.

Hence, if we consider all possible combinations of the 4 alignments for each of the slabs S, we have all the possible decking configurations. Note that not all combinations of alignments are allowed; SL and SR can be used for any slab, but CL can only be used if the slab to the left of it is either SL or CL, and CR can only be used if the slab to the right of it is either SR or CR.

-Snip- The problem appears to be significantly different from what is attempted to solve here, so I won't be finishing this post.

Answer 4

This is not easy:

I think you will not successfull solving that on your own:

More info see

Preparata, Shamos: Computational Geometry: Chapter 8: The Geometry of Rectangles.

You should first be familar with Plane Sweep Algorithms and Intervall Trees.

If I find more, i will update. Found more:

Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping