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

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:

- 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^{1}, 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. - Each water jug gets a portion
of the reservoir (be the number of
water jugs in the
**i**th iteration). Step 1 may have caused for different water levels of the jugs. Therefore, every jug is filled to a common minimal level - Caused by the minimum satisfaction guarantee, the level
^{2}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 (). - 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**. This algorithm terminates when all jugs are inactive () or the water reservoir is empty._{j}

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.^{3}

**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

Tue Jun 11 13:34:48 MET DST 1996