Algorithm to divide a rectangle to smaller retangles?
What's the algorithm to divide a rectangle (c struct
with 4 int
s) to a random number of smaller rectangles (return a list of struct
s)? 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.
精彩评论