Information Technology Reference
In-Depth Information
to the interior faces. A Schnyder wood is a special type of partition (colouring)
and orientation of the edges of a planar triangulation into three rooted directed
trees. Schnyder [15,16] used them to obtain straight-line planar drawings of tri-
angulations in an O ( n )
O ( n ) grid. To do this he defined barycentric coordinates
for each vertex in terms of the number of faces in certain regions of the Schnyder
wood. Dhandapani [7] noted that assigning any positive weights to the faces still
gives straight-line planar drawings. We call these weighted Schnyder drawings
they are the drawings on which our morphing algorithm works.
Two weighted Schnyder drawings may differ in weights and in the Schnyder
wood. We address these separately: we show that changing weights corresponds
to a single planar linear morph; altering the Schnyder wood is more significant.
The set of Schnyder woods of a given planar triangulation forms a distributive
lattice [5], [11], [14] possibly of exponential size [12]. The basic operation for
traversing this lattice is a “flip” that reverses a cyclically oriented triangle and
changes colours appropriately. It is known that the flip distance between two
Schnyder woods in the lattice is O ( n 2 ) (see Section 2). Therefore, to morph
between two Schnyder drawings in O ( n 2 ) steps, it suces to show how a flip
can be realized via a constant number of planar linear morphs. We show that
flipping a facial triangle corresponds to a single planar linear morph, and that a
flip of a separating triangle can be realized by three planar linear morphs.
×
3
2
2
3
2
1
1
1
4
1
3
3
3
1
2
2
1
2
1
4
4
4
Fig. 1. A sequence of triangle flips, counterclockwise along the top row and clockwise
along the bottom row. In each drawing the triangle to be flipped is darkly shaded, and
the one most recently flipped is lightly shaded. The linear morph from each drawing
to the next one is planar. Vertex trajectories are shown bottom right.
There is hope that our method will give good visualizations for morphing.
See Figure 1. The edge-contraction method of Alamdari et al. [1] is not good
for visualization purposes—at the end of the recursion, the whole graph has
contracted to a triangle. The method of Floater and Gotsman [13] gives good
visualizations, based on experiments and heuristic improvements developed by
Search WWH ::




Custom Search