Algorithm to divide a rectangle to smaller retangles?

What's the algorithm to divide a rectangle (c struct with 4 ints) to a random number of smaller rectangles (return a list of structs)? Even better if the max and min dimension of the smaller rectangles can be controlled by a parameter.

e.g.

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -开发者_开发百科->     |---+---+--| (good)
|          |            |   |      |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

smaller shapes should be 4-sided, the following is not good:

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -->     |---+---+--| (not good)
|          |            |          |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

Thanks!

Appendix: (rectangle for Moron's discussion)

  +----+--------+
  |    |        |
  |    +---+----+
  |    |   |    | (rectangle-chase)
  +----+---+    |
  |        |    |
  +--------+----+

---

Split the rectangle into two. Recurse.

---

It's a bit odd to ask this question without specifying what conditions under which the rectangles are split.

However, I suspect that what you're looking for is a kd-tree. The kd-tree is a binary tree in which nodes are split with two resulting child nodes based on a condition. http://en.wikipedia.org/wiki/Kd-tree

There's also a quad-tree which can be slightly simpler to implement. It involves splitting nodes into 4 equal-sized children. Each child is recursively split this way until some stop condition. http://en.wikipedia.org/wiki/Quadtree

[Edit: Updated in response to op's edits.] For what you are doing, might it be simpler to start off dividing the rectangle into an even grid and decide which elements to merge? Basically a bottom-up approach: simply pick one and start merging adjacent cells randomly. Don't do this for cells which have already been traversed, and the merged structure should have a width and height so that expanding a 2x1-cell grid will expand to 2x2 or 3x1 to ensure you constantly keep a 4-sided rectangle shape for the merged node.

If you want a fancier approach, you can approach this like a kd-tree and build it top-down but you'd need to be merging whole sub-trees as you're splitting based on random conditions and the min/max width/height parameter.

---

Choose a random point p on one edge and divide the rectangle there with a line to the opposite edge. You can then recurse on both halves, stopping the recursion randomly or at a specified limit.