Next: Meta-Level Techniques for Up: No Title Previous: User-Defined Layout Schemes

The Box Layout Algorithm Revisited

The important features of our basic box layout algorithm have already been explained in the previous sections. This formalism provides the user with a fast and flexible layout algorithm, which is also easy to understand and anticipate. In order to keep this formalism simple, we decided to restrict the dependencies between boxes and fillers, i.e. their mutual influence on size and position of graphical objects. Boxes may be arbitrarily nested, but only fillers on the same box level compete for the available space. Figure 7 exemplifies this feature.

  
Figure 7: Schematic representation of nested boxes. Arrows represent fillers.

The (vertical) fillers of level 1 are independent of the (vertical) fillers of level 3. This restriction reduces considerably the computational complexity of the layout algorithm. Another advantage is that the semantics of constrained fillers are easy to comprehend by the user. Even this scheme requires a simple relaxation algorithm for constraint satisfaction. Figure 8 illustrates our algorithm.

  
Figure 8: Water jugs modeling fillers.

Each water jug models a filler having a minimal and maximal expansion value. The current extension of a filler corresponds to the water level of a jug. The total space available to fillers is modeled by an external water reservoir with capacity . The extension of a filler is computed by the following steps:

1. Initially each water jug j is filled to a level . It is guaranteed that every water jug j is at least filled to its minimum . In case of an additional demand for water, which cannot be supplied by an empty water reservoir¹, this demand is satisfied by a ``water pipe''. If there is any water in the reservoir left, the remainder of this water is distributed according to the following steps.

2. Each water jug gets a portion of the reservoir (be the number of water jugs in the ith iteration). Step 1 may have caused for different water levels of the jugs. Therefore, every jug is filled to a common minimal level

   

3. Caused by the minimum satisfaction guarantee, the level² of a jug j may already be higher than or its maximum . The amount of water exceeding either or is returned to the reservoir. A jug which has reached its maximal level becomes inactive ().

4. Start again with step 2 (; i=i+1) provided the water reservoir is not empty and there is at least one jug j left whose water level is below max_j. This algorithm terminates when all jugs are inactive () or the water reservoir is empty.

The termination of this algorithm is guaranteed since each cycle either makes one jug inactive or removes water from the reservoir. If no jug becomes inactive at least one jug is filled to the level . The computation of the relaxation process uses integer arithmetic. Therefore, rounding errors are summed up and as final step this sum is rounded and added to the last filler.³

1

This is an indication that the available space is not sufficient to fulfill the space requirements. Items could extend beyond the boundary of their surrounding box.

2

The capacity of a jug be temporarily unlimited.

3

This is needed for frame-boxes, which may otherwise not exactly fit to the lower border of their box.

Next: Meta-Level Techniques for Up: No Title Previous: User-Defined Layout Schemes