We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line pla-narity. A paper in SODA 2013 gave a morph that consists of O(n~2) steps where each step is a linear morph that moves each of the n vertices in a straight line at uniform speed. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in O(n~2) linear morphing steps and improve the grid size to O(n) × O(n) for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic "flip" operations of Schnyder woods as linear morphs.
展开▼
机译：我们考虑在同一三角图的两个平面图之间变形，保持直线平整度的问题。 SODA 2013中的一篇论文给出了一个由O（n〜2）个步骤组成的变形，其中每个步骤都是一个线性变形，它以均匀的速度沿直线移动n个顶点中的每一个。但是，他们的方法模仿了边缘收缩，因此中间图形的网格大小不受限制，并且变形对于可视化效果也不佳。使用Schnyder嵌入，我们可以在O（n〜2）个线性变形步骤中进行变形，并针对重要的三角剖分绘图类（即加权Schnyder绘图类）将网格大小提高到O（n）×O（n）。 。这些变体在视觉上具有吸引力。我们的方法涉及将Schnyder木材的基本“翻转”操作实现为线性变体。
展开▼
