I need a method to divide 3d space into random axis aligned box shapes. For now I am currently dividing the 2d space for testing purposes. The most immediate approach I came up with was to define a rectangle of size (1, 1) and then recursively split all existing rectangles to two uneven rectangles alternating between axis X and Y.
The problem here is obvious. This approach results in long stretching lines (marked in red)
What I would like is something more organic looking (I included an example)
See, no long straight lines from top to bottom or left to right.
The only constraint is that I may wish to limit the minimal size of the rectangle without affecting the granularity of the sizes. i.e. if the smallest rect is 1 square centimeters than the seconds smallest room should not be 2 square units.
So ideally the algorithm should meet all three following constraints:
- Rectangles are not infinitesimally small.
- Rect sizes aren't discrete multiplication of the smallest rect size. i.e. if the smallest rect is 3 square unit than larger rects are not constrained to be 6, 9, 12 and so forth square units and instead could be 3.2 or 4.7 for that matter).
- The algorithm runs in polynomial time (needs to compute fast).