I'm looking for an efficient puzzling algorithm (or source code), to fill up
a 2D area with multiple rectangle (of any size) without overlapping !
If anyone has an inteligent method, for this i would be please to ear from
him !
If anyone has an inteligent method, for this i would be please to ear from
him !
>If anyone has an inteligent method, for this i would be please to ear from
>him !
This is a recursive algorithum, you proberbly want to be able to specify a
minium width and height for the resulting rectangles so i'll include that in
my description.
Take the whole rectangular area and split it verticly from top to bottom at
a random position ensureing that the both sides conform to your minimum
width. Then take each resulting area and split it verticly using the same
method but horizontaly and checking for minimum height. Repeat this
recursivley creating smaller and smaller rectangles until you can no longer
create any rectangles that meet your width and height restrictions.
At a rough guess you proberbly need to check if a horizontal split is
possible even if a vertical split is not (and the other way around) to avoid
getting long thin peices left at the end.
Anyway, this should produce usable results.
James,
how many rectangles of the same size?
e.g. one, two, three or 1-3 or any makes a huge difference!
allow/disallow rotation?
if of any size the recursive algo posted by James Sharman looks fine
to me. but this doesn't take rotations into account. rotated recs may
needs less subdivisions and may require a small preprocessing step to
find a good rotation angle.
completely fill up or allow borders? (disallow slack)
if so optimize for the least
possible area of these or try to get connecting holes/borders
even if this area is not optimal then?
this fits only to the problem of a limited number of rectangle sizes,
which is quite common in real-world problems.
you have to specify the optimizations requirements:
fastest, good or best solution? least numbers of recs? least slack?
rectangles are very easy. allowing a limited number of arbitrary shapes
make a big difference, see the penrose tilings.
i could give you lisp sources but you wouldn't be happy :)
--
"The C language is particularly rich with ways of writing a program
that totally hides the original design intent." Stanley Crow
does anyone know where I can get gif alogrithms. I want to be able to
extract gray scale histogram data into an array. Anybody know?
Help appreciated!
4. Mr Furniture..collection of 3d furniture models
7. Anti-pixellating alogrithm: is it possible ?
8. Rasteriser
9. Wanted: Landscape Alogrithm
10. applications of convex hull alogrithms
11. 3-D View Interpolation - Any Alogrithms?
12. New Book: COMPRESSION ALOGRITHMS
13. simple 3d inverse kinematics alogrithms needed ...