rectangular areas of free space i've been working with an algorithm which places rectangles within a grid (itself a rectangle) so they do not overlap. based on an algorithm used by the fluxbox window manager, and unlike traditional bin-packing algorithms, the placement of the windows/rectangles within the workspace/bin/grid has the emphasis on position rather than best-fit.
the algorithm always tries to place the rectangle in the top-left of the grid. if it cannot place it there, it moves a little to the right, and tries again. if it reachs the far right, it then moves down a little and starts over at the left side again. an important consideration here, is that this algorithm does not require the complete set of rectangles to be placed, it places the rectangles as and when requested to do so. Here is an illustration showing three rectangles that have been placed in a grid by the algorithm: +----+-----+------+-------+ |1 |2 |3 | | | | | | | | +-----+ | | | | | | | +----+ | | | | | | | | | | | | +------+ | | | | | | | | | | | | | | | +-------------------------+ i have been testing the algorithm for suitability in a real time scenario. any algorithm which operates in a real time context must be coded to gracefully handle the worst case scenario. i decided upon a worst case scenario of 255 rectangles (for good reasons i won't go into here). i soon discovered this scenario failed to meet the timing deadlines of real time operation. taking the algorithm out of the real time context, and displaying data about it as it ran, i discovered that when 254 rectangles have been placed by it, in order to add the 255th rectangle, the algorithm scans the entire list of all 254 rectangles over 1400 times. in a nutshell, this is very bad. after pondering about it for some days, i have come up with a different idea for an approach which stores not only the rectangles which have been placed, but the free unoccupied space also. i began by envisioning that the free space rectangles would be connected to each other. this soon presented the problem of how many links each rectangle would have, and has been potentially solved by a single characteristic or rule: each free space rectangle has a maximum of 4 free space rectangles directly adjacent to it. The following diagram illustrates how the free space would be divided when the same three rectangles as shown in the first diagram have been placed: +----+-----+------+-------+ |1 |2 |3 |a | | | | | | | +-----+ | | | |b | | | +----+.....| | | |c | | | | | | | |..........+------+.......| |d .e .f | | . . | | . . | | . . | | . . | | . . | | . . | +-------------------------+ The numbered rectangles are the rectangles which have been placed by the algorithm. The dotted rectangles are the subdivisions of the area of free space. When placing a fourth rectangle (4) which is small enough to be contained entirely within free space rectangle a, the result is free space a being split to form free space g: +----+-----+------+---+---+ |1 |2 |3 |4 |a | | | | | | | | +-----+ | | | | |b | +---+...| +----+.....| |g | |c | | | | | | | |..........+------+.......| |d .e .f | | . . | | . . | | . . | | . . | | . . | | . . | +-------------------------+ However if only the width of new rectangle 4 is smaller than the width of frespace a, (ie only the height is greater) then free space f is split: +----+-----+------+----+--+ |1 |2 |3 |4 |a | | | | | | | | +-----+ | | | | |b | | | | +----+.....| | | | |c | | | | | | | | | |..........+------+ | | |d .e | | | | . | | | | . +----+ | | . .f . | | . . . | | . . . | | . . . | +-------------------------+ Lastly, the width of new rectangle 4 may be larger than that of a, in which case it's width is measured against the first free space in a lower row. which in this case is b, but the width of b is too small, so the next free space down, c, is found, and the width of 4 is smaller than the width of c. but, the height of 4 is greater than the height of c, which means 4 extends into d like so: +----+-----+------+-------+ |1 |2 |3 |a | | | | | | | +-----+ | | | |b | | | +----+--+..| | | |4 |c | | | | | | | | | |..+------+.......| | | .e .f | | | . . | | | . . | | | . . | | | . . | +-------+ . . | |d . . | +-------------------------+ There are two ways to solve this: the first is to subdivide d, creating g: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |4 |c | | | | |..+------+.......| | |g .e .f | | | . . | | | . . | | | . . | | | . . | +-------+ . . | |d . . . | +-------------------------+ the second crops d and extends e: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |4 |c | | | | |..+------+.......| | |e .f | | | . | | | . | | | . | | | . | +-------+ . | |d . . | +-------------------------+ the second solution is prefered. _______________________________________________ NetBehaviour mailing list [email protected] http://www.netbehaviour.org/mailman/listinfo/netbehaviour
