Break a rectangle into randomly shaped polygons

Question

Just like the title says, I need to break a rectangle into randomly shaped polygons.

Example, with 7 polygons:

+--------+--------+
|\       |   2    |
| \  1   |''--..__|
|  ------|  5     |
| 3  /   \________|
|   /    /\   6   |
|__/ 4  /  \______|
|      /  7       |
+-----+-----------+

I don't know if there's an algorithm already out there for this, but I can't seem to get my head around this.

I don't particularly care what language you answer in, but I'll be implementing in Java/Swing.

Answer 1

You may drop a bunch of random points on the rectangle, and calculate the Voronoi Diagram.

Here is a Java/Swing implementation.

I did some samples (but using Mathematica, not the above implementation)

HTH!

Answer 2

I'd draw a bunch of random lines across the full rectangle and then "split" the lines at each line intersection, so that you basically have some kind of net of lines. Then remove as many random line segments as you like until you reach the desired number of polygons.

Edit: So for your sample it would have been like this after adding the lines:

+----+---+----+---+
|\'--.\_/|   /    |
| \    X |''/-..__|
|--\--+-\+-/------|
|___\/___\/_______|
|   /\   /\       |
|__/__\_/|_\______|
| /    X |  \     |
++----+-++---+----+