Information Technology Reference
In-Depth Information
l
y
i
x
i
x
[400, 450]
[100, 100]
[0, +∞[
s
y
l
y
n
y
]-∞, 0]
]-∞, 0]
a
x
a
x
[600, 600]
[0, +∞[
]-∞, 0]
]-∞, 0]
]-∞, 0]
a
y
[0, +∞[
[0, +∞[
]-∞, 0]
p
x
p
x
[400, 400]
c
y
[1024,
1200]
[400, 400]
[0, +∞[
]-∞, 0]
]-∞, 0]
]-∞, 0]
]-∞, 0]
]-∞, 0]
n
x
n
x
a
y
]-∞, 0]
h
x
[600, 700]
h
x
]-∞, 0]
[0, +∞[
[400, 400]
[0, +∞[
[0, 0]
]-∞, 0]
]-∞, 0]
[150,
200]
[0,+∞[
[0, +∞[
]-∞, 0]
c
y
]-∞, 0]
c
x
[400, 400]
c
x
[1024, 1024]
[0, +∞[
]-∞, 0]
]-∞, 0]
i
y
]-∞, 0]
[0, +∞[
[0, 0]
[0, +∞[
]-∞, 0]
l
x
l
x
[200, 200]
n
y
[450, 550]
i
y
]-∞, 0]
[0, 0]
s
x
s
x
[700, 850]
]-∞, 0]
p
y
[400,
400]
s
y
p
y
]-∞, 0]
]0, 1024]
Fig. 4.
Graph representation of part of the
xSTP
and
ySTP
of Example 3. For the sake of
readability, constraints involving
h
in the
ySTP
and the universal constraint are omitted.
In this section, we focus our attention on an application of the cmRCD-calculus to
the automatic web page layout generation, inspired by a work by Borning et al. [4].
On the one hand, current web authoring tools do not allow home page designers to
specify how the document should change in response to viewer's needs; on the other
hand, web browsers do not really allow their users to express their requirements about
the layout, except for those about the dimension of the font and few other features. The
work by Borning et al. aims at allowing both the designer and the viewer to specify the
positioning of the document elements by means of linear equalities and inequalities over
their minimum bounding boxes, in such a way that the layout of the web page becomes
the result of a negotiation between them (designer and viewer). In the following, we
show how to apply cmRCD-calculus to allow the user (author or viewer) to specify
both cardinal and metric constraints on the layout elements. Notice that, in doing that,
we reduce the expressive power of Borning et al.'s proposal; nevertheless, the problem
they consider is in fact an optimization problem, which is solved by means of a linear-
programming algorithm that has an exponential worst-case time complexity.
Example 3.
Let us consider a Facebook-like social network, that allows the user to
personalize the contents of his/her home page by making use of directional constraints.
We can assume each element the user can add to be represented by a MBR, or box,
whose sides are parallel to the axes of the reference system centered at the lower left
vertex of the home page. As an example, we may have a box containing information
about his/her (gender, birthday, etc.), a box containing his/her profile picture, and so
on. In addition, it makes sense to assume that the system requires all user pages to
share some common presentation features like, for instance, the system logo and some
general presentation directives.
In this scenario, we can imagine that a user enters the following requirements to
some design tool that interacts with the layout designer (user's specifications are given