Converting Triangulations to Quadrangulations


Summary:

Sam Sanjabi, Rachel Potvin

Original Paper:

Ramaswami, Ramos, and Toussaint




Abstract

We study the problem of converting triangulated polygons to quadrangulations. We obtain a variety of characterizations for when a triangulation admits a quadrangulation without the use of (or with a bounded number of) Steine r points. We also examine the effects of demanding that the Steiner points be added in the exterior of a triangulated simple polygon. We propose an O(n) algorithm for accomplishing this task whic h uses at most floor(n/3) Steiner points. We show that this bound is always sufficient and sometimes necessary to quadrangulate a simple polygon.

Top / Bottom

Introduction

The process of creating a "mesh" from a given set of data points has many applications, for example, data interpolation and terrain modeling. Traditionally, the favoured mesh used in these applications was the triangular mesh (or tri angulation of the data points). However, in some situations, a quadrangular mesh is preferable. Unfortunately, not much is known about quadrangulations, and good quadrangular meshes are more difficult to generate than good triangular ones. In fact, it is shown that a set of points admits a quadrangulation (without the addition of Steiner points) if and only if the number of points on the convex hull is even. Hence, some attention has been devoted to the problem of converting triangulations to quadrangulations.

We note here that we are concentrating on simple polygons. We also demand that the quadrangles obtained be strict quadrangles (i.e. they do not contain three collinear vertices), and that Steiner points are not added on boundaries or diagonals. We only allow Steiner points in the strict exterior (outer Steiner points), or the strict interior, (inner Steiner points) of the polygon in question.

Top / Bottom

Quadrangulating a Simple Polygon Triangulation

In this section we examine a couple of simple methods of converting triangulations to quadrangulations. Since not all polygons admit a quadrangulation, it is often necessary to add Steiner points, (i.e. points that are not vertices of the original polygo n). We allow the deletion of existing diagonals, but no new diagonals can be inserted between pairs of original vertices. Also, we do not allow the deletion of vertices from the original polygon.


I. NAIVE BRUTE FORCE ALGORITHM

INPUT : T, a triangulated polygon
OUTPUT : Q, a quadrangulated polygon
  1. Insert a Steiner point along the interior of every edge and diagonal of the triangulated polygon, T.
  2. Insert an extra Steiner point in the interior of each triangle such that it is not collinear with any other pair of Steiner points in the triangle.
  3. Connect the Steiner point inside each triangle to the Steiner points on the edges of that triangle.
The correctness is trivial since each triangle is converted into three quadrangles.


Figure 1:
Example of simplest construction of a quadrangulation
from a triangulated polygon

Advantages

  1. By choosing the Steiner point on the interior of the triangle carefully, (i.e. within the triangle defined by the other three Steiner points of the triangle), we can obtain a quadrangulation such that all the quadrangles are convex. [ref]
  2. This algorithm is trivial to implement.
  3. This algorithm runs in O(n) time.
  4. Finally, this algorithm works for any triangulated domain and always produces a strict quadrangulation.
Disadvantages

  1. There are far too many Steiner points needed when using this algorithm (3n-5 in a triangulated simple n-gon).

II. QUADRANGULATION VIA HAMILTONIAN TRIANGULATIONS

INPUT : T, a triangulated polygon with n vertices
OUTPUT : Q, a quadrangulated polygon
  1. Obtain a Hamiltonian-cycle triangulation (Arkin et al.) [ref]
    1. Consider T, insert its planar dual graph D. (This can always be done as per Bern and Gilbert [ref])
    2. Connect each node of D to the vertices of its correspoding triangle in T.
    3. Remove the original diagonals of T.
  2. Obtain the Hamiltonian order by performing a tree traversal on the dual graph.
  3. Follow the Hamiltonian order (starting from a triangle that has at least one edge on the boundary of the polygon), and delete every other diagonal.
  4. The last element may be a triangle, (if the number of diagonals is odd). If this is the case then add one extra outer Steiner point to convert it to a quadrangle.
(a) (b)
(c)
(d)


Figure 2: Quadrangulation via Hamiltonian triangulation. (a) Original triangulated polygon. (b) Geometrical dual tree inserted with each node of the tree connected to the three vertices of its correspondin g triangle. (c) Original diagonals removed. (d) A resulting quadrangualtion with a single triangle remaining, where an outer Steiner point is inserted.

Analysis

Although this method does give a substantial improvement over the previous one, we can still do much better.

Top / Bottom

Outer Steiner Points Theorem

We prove here an upper bound on the number of outer Steiner points required to quadrangulate a triangulated simple polygon of n vertices.

Theorem 1: Floor(n/3) outer Steiner points are always sufficient, and sometimes necessary, to quadrangulate a triangulated simple polygon of n vertices. Furthermore, these Steiner points may be located in O(n) time.


PROOF OF SUFFICIENCY

Since the vertices of a triangulated polygon can be three-coloured, every triangulation of an n-gon, P, can be partitioned into <= floor(n/3) fans by choosing the least-covering colour (Fisk). A fa n is a triangulation where one vertex, the "fan center", is shared by all the triangles. It also follows from Fisk's argument that there always exists a decompostion such that these fans start and end at edges of the polygon. Therefore, each fan arm app ears in only one fan.




The triangles in the fan can be sequentially paired up to form quadrangles. If there are an odd number of triangles, we will be left with one unpaired triangle which will require one Steiner point, p, in a suitable location outside the fan arm e=vv'. De leting e and joining p to v and v' completes the quadrangulation of the fan.

Since P can be partitioned into <= floor(n/3) fans, and we need at most one Steiner point per fan, it follows that floor(n/3) outer Steiner points are always sufficient to quadrangulate a triangulated simple polygon.


PROOF OF NECESSITY

Observe the triangulated polygon below.




  1. If v1 is chosen as a fan center, then the other fan centers must be the vertices v4, v7, v10, ..., vn-2. These fans will consist of single triangles and will each need one outer Steiner po int.

  2. If v3, v6, v9, ..., vn-3, vn are chosen as fan centers, each fan will have an odd number (3 or 1) of triangles and each will need one outer Steiner point.

  3. If v2, v5, v8, ... , vn-1 are fan centers, the situation is similar to b.

In each of the above cases, floor(n/3) outer Steiner points are necessary in order to obtain a quadrangulation.


Finding the Steiner points in O(n) time:

  1. First, three colour the triangulated polygon to find fans : O(n).

  2. To locate Steiner points
    1. Triangulate the pockets of P using Chazelle's algorithm. Place Steiner points anywhere inside an exterior triangle incident to fan edge e : O(n).
    2. If e is on the convex hull, then place the point inside the triangle defined by e, and the extension of the convex hull edges adjacent to e.
Q.E.D.

Top / Bottom

Optimal Outer Steiner Points Algorithm

The dual graph of a triangulation is one where there is a node for each triangle, and an edge between two nodes if the triangles share an edge. When computing quadrangulations, we would like to match pairs of adjacent triangles so that we can remove the edge that they share to form a quadrangle. In order to minimize the number of Steiner points used, our goal becomes finding the maximum number of such pairings.

This corresponds precisely to a maximum cardinality matching problem on the dual graph of the triangulation, (a maximum matching of a graph is an edge set of maximum size such that no two edges share a node).

It follows from this that the dual graph of a triangulation, T, admits a perfect matching, (a matching such that all nodes are matched), iff T can be quadrangulated with no Steiner points.

Furthermore, we know that the dual graph of a triangulated simple polygon is a binary tree, since it contains no holes, and every node has degree at most three, (a triangle can only share edges with three other triangles). Hence, we can exploit this stru cture to obtain a fast algorithm.

In order for our algorithm to use only outer Steiner points, we would need to find a maximum matching of the dual tree such that the unmatched nodes are at the leaves. That way, the unmatched nodes would correspond to a triangle which shares an edge with the boundary of the polygon. Hence we could pair up this unmatched triangle with an outer Steiner point. In the remainder of this section, we show that such a maxiumum matching can be computed in linear time. Before we proceed, we give some definition s and lemmas.

MATCHING EDGE : edge, e, in a matching, M, of an undirected graph G=(V,E)
FREE EDGE : edge, e, an element of G=(V,E) but not of the matching, M
MATCHED NODE : a node on a matching edge of G=(V,E)
FREE NODE : a node not on a matching edge of G=(V,E)
MATE(u), where u,v
are elements of V(G)		: v = mate(u) AND u = mate(v)
iff edge(u,v) is an element of the matching, M
ALTERNATING PATH : An alternating path is a simple path in G whose edges are alternately matching and free.
AUGMENTING PATH : An alternating path such that both of its enpoints are unmatched nodes.


Lemma 1: M is a maximum matching of a graph G=(V,E) iff G has no augmenting path with respect to M.


THE ALGORITHM - Percolate UP

Let T=(V,E) be a binary tree, and without loss of generality assume that T is rooted at a node of degree 1.

h = height of T (with root at level 1)
level(u) = depth of node u an element of T
vh = v is an element of V(T) such that level(v) = h

Note that the nodes of vh are leaves, but not necessarily all the leaves in T. Let par(v) denote the parent of v. We have the following cases:

CASE[0] : degree(par(v)) = 1 => T consists of two nodes and an edge, match v and par(v)

CASE[1] : degree(par(v)) = 2 => match v and par(v)

CASE[2] : degree(par(v)) = 3 => AND v is the left child of par(v) => match v and par(v)

CASE[3] : degree(par(v)) = 3 => AND v is the right child of par(v) => leave v unmatched


After performing these matchings on all elements of vh, prune the tree by deleting v and par(v) for each occurrence of cases [0,1,2] and each time there is an occurrence of case[2] delete the sibling of v, (this is because for every case[2] the re will be an occurrence of a case[3]).

After the pruning step, the remaining tree will have height h-1 or h-2. Repeat the matching and pruning until we are left with an empty tree. (Note that this takes k <= h iterations.

Theorem 2: The matching, M, found by the above algorithm for the tree, T, cannot have any augmenting paths with respect to M.

PROOF

Consider two unmatched nodes u and v in T. Without loss of generality let level(u) >= level(v). By the algorithm, u must be the right child of a node of degree three, (since it is unmatched). In this case par(u) is matched to its left child. Since level(u) >= level(v) the path from u to v must go through par(u) and par(par(u)), (which are also not matched toghter). Therefore there cannot be a path of alternating free and matching edges from u to v. Q.E.D.

To see that the algorithm is linear, observe that the vi can be found in O(n) time by using strategies such as depth-first-search and breadth-first-search. We also see that each node is considered once and then deleted. It follows that the wh old algorithm is linear.

This has given us a maximum matching in which some of the unmatched noeds could be internal. We will now show that this can be modified to yield a matching with the unmatched nodes at the leaves while keeping linear running time.

Lemma 2: There exists a maximum matching for a tree, T, such that all its unmatched nodes are leaves of T.

PROOF

Let M be the maximum matching found by algorithm Percolate UP. Let u be an unmatched interior node of T.

  1. We show that there is an alternating path from u to a leaf.

    • u's children must be matched, (otherwise we could match one with u and increase the size of M).

    • Let u1 <- leftChild(u) , (or just the child if there is only one)
      u2 <- mate(u1)
      => children of u2 must be matched, otherwise there would be an augmenting path from u to one of u2's children.

    • Let u3 <- leftChild(u2) , (or just the child if there is only one)
      u4 <- mate(u3)

    • Continue in this manner until we reach a leaf lu, (which must be matched in order to keep this path non-augmenting).

    • This path Pu is an alternating path where (u1,u2) , (u3,u4), ... , (um-1,lu) are matching edges.

  2. We now show that there is a unique such path to a unique leaf for each internal unmatched node.

    Let u and v be two unmatched internal nodes, we show that Pu and Pv are disjoint.

    1. if level(u) = level(v), then Pu and Pv lie in subtrees rooted at u and v and are hence disjoint since the subtees are disjoint.

    2. assume without loss of generality that level(u) <= level(v)


Finally:

  1. If v isn't in the subtree rooted at u, then Pu and Pv are disjoint for the same reason as i.

  2. if v is in the right subtree of u, then Pv is entirely in that subtree and can't overlap Pu (since Pu lies in the left subtree.

  3. If v is in the left subtree of u, then v cannot lie on Pu since all nodes in Pu are matched nodes. This implies that v must lie in one of the subtrees Tu1, Tu2, ..., Tum-11 and hence so must Pv, therefore Pu and Pv don't overlap.
    Q.E.D.


Next, to modify the algorithm, we simply exchange the matching and free edges along Pu so that (u,u1), (u2, u3), ..., (um-2, um-1) are now matching edges...

--> lu is now unmatched and u is matched, the unmatched node has been percolated down to the leaf.

This can be done for each interior unmatched node along a unique path, therefore we have modified the matching M to yield a matching M' with unmatched nodes at the leaves in O(n) time.

THEREFORE: we have the following result:

Theorem 3: The Percolate-UP and DOWN algorithm quadrangulates a triangulated simple n-gon using a minimmum number of outer Steiner points. This algorithm runs in O(n) time.

Top / Bottom

Interactive Java Applet

Instructions:

  1. Create a Simple Polygon.

    Use your mouse to enter points one by one. When finished, close the polygon by clicking on the initial vertex. This applet will not let you create a polygon that is not simple.

  2. Triangulate the polygon.

    Add diagonals by using your mouse to click on pairs of vertices, then hit the continue button. This applet will not let you add edges that are not proper diagonals.

    If you would rather triangulate the polygon automatically then just click the continue button. However, we recommend triangulating the polygon yourself for several reasons:

    • You will most likely make a cleaner triangulation from which it will be easier to see each step of the chosen quadrangulation algorithm.

    • Our algorithm will always triangulate the polygon in the same way. You can learn more about the quadrangulation algorithms by triangulating similar polygons in different ways.


  3. Quadrangulate the polygon

    Choose one of the two algorithms, either brute force or percolate up-down, in order to convert the triangulation into a quadrangulation. When either algorithm is complete, hit the unquadrangulate button to return to the original triangulated polygon.

    Both quadrangulation algorithms are presented in a series of steps. Hit the next button to move on to the following step, (Depending on the complexity of your polygon some of the more complicated steps might take a few seconds, be patient!).

  4. Start again from the beginning.

    At any point the applet can be restarted by clicking the reset button.

Note: When testing the percolate up-down algorithm, see if you can create a polygon that requires both the percolate up and percolate down steps. Hint : look for polygons that require free triangles, (triangles that share no edges with the original polygon).




Applet Source Code


Top / Bottom

Definitions

Triangulated Polygon

A decompostition of a polygon, P, into triangles by a maximal set of diagonals that may intersect only at their endpoints. [back]

Quadrangulations

A decomposition of a polygon, P, such that the finite elements are quadrilaterals (as opposed to triangles). [back]

Steiner Point

An Additional point added to a given triangulated domain so that the set admits a given quadrangulation. [back]

Simple Polygon

An ordered set of vertices P={p1,...,pn} which form a single, closed, non-intersecting polygonal chain. [back]

Convex Hull

The convex hull of a set, S, (denoted CH(S)), is the intersection of all convex sets that contain S. Intuitively, the "smallest" convex set which contains S. e.g. The convex hull of a set of points is the convex polygon, P, with points of the set as vertices such that P contains all the points. [back]

Simple n-gon

Simple polygon with n vertices. [back]

Dual Graph of a Triangulation

Given a triangulated domain T, it's dual graph, D, is the graph which has one node for each triangle in T. There is an edge between two nodes if their corresponding triangles share an edge. [back]

Three-Coloring of a Triangulation

Given a triangulated domain, T, it can be three-colored if the vertices of the domain can be colored with THREE colors such that no triangle in the domain is assigned the same color to two of its vertices. [back]

Pocket of a Simple Polygon

The pockets of a simple polygonal are regions which are not in the polygon, but are within it's convex hull. [back]


Top / Bottom

References


  1. R. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993

  2. D.J. Allman. A quadrilateral finite element including vertex rotations for plane elasticity analysis. International Journal for Numerical Methods in Engineering, 26:717-730, 1988.

  3. E. Arkin, M. Held, J. Mitchell, and S. Skiena. Hamiltonian triangulations for fast redering. In J. van Leeuwen, editor, Algorithms-ESA'94, LNCS 855, pages 36-47, Utrecht, The Netherlands, September 1994.

  4. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308-340, 1991.

  5. C. Berge. Two Theorems in Graph Theory. In Proc. National Acad. of Science, volume 43, pages 842-844, 1957.

  6. M. Bern and D. Eppstein. Mesh generation and optimal triangulation. In F.K. Hwang and D.-Z. Du, editors, Computing in Euclidean Geometry. World Scientific, 1992.

  7. M. Bern and J. R. Gilbert. Drawing the planar dual. ,i> Information Processing Letters, 43:7-13, August 1992.

  8. M. W. Bern, E. L. Lawler, and A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs. Hournal of Algorithms, 8:216-235, 1987.

  9. P. Bose, S. Ramaswami, G. Toussaint, and A. Turki. Experimental comparison of quadrangulation algorithms for sets of points. In Proc. of the 12th European Workshop on Computational Geometry, Munster, Germany, March 1996.

  10. P. Bose and G. T. Toussaint. No quadrangulation is extremely odd. In Proc. of the International Symposium on Algorithms and Computation, Cairns, Australia, December 4-6 1995.

  11. J. Bown. Injection Moulding of Plastic Components. McGraw-Hill, New York, 1979.

  12. B. Chazelle. Triangulating a simple polygon in linear time. Discrete and Computational Geometry, 6:485-524, 1991.

  13. V. Chvatal. A combinatorial theorem in plane geometry. J. Combin. Theory Ser. B, 18:39-41, 1975.

  14. H. S. M. Coxeter. Projective Geometry. Springer-Verlag, New York, 1987.

  15. L. De Floriani, B. Falcidieno, and C. Pienovi. Delaunay-based representation of surfaces defined over arbitrarily shaped domains. Computer Vision, Graphics and Images Processing, 32:127-140, 1985.

  16. H. Edelsbrunner, H. O'Rourke, and E. Welzl. Stationing guards in rectilinear art galleries. Computer Vision, Graphics and Image Processing, 27:167-176, 1984.

  17. H. Everett, W. Lenhart, M. Overmars, T. Shermer, and J. Urrutia. Strictly convex quadrilateralizations of polygons. In Proc. of the 4th Canadian Conference on Computational Geometry, pages 77-82, St. Johns, Newfoundland, 1992.

  18. S. Fisk. A short proff of Chvatal's watchman theorem. J. Combin. Theory Ser. B, 24:374, 1978.

  19. E. Heighway. A mesh generator for automatically subdividing irregular polygons into quadrilaterals. IEEE Transactions on Magnetics, 19(6):2535-2538, 1983.

  20. K. Ho-Le. Finite element mesh generation in polygonal regions. Computer Aided Design, 20:27-38, 1988.

  21. B. Joe. Quadrilateral mesh generation in polygonal regions. Computer Aided Design, 27(3):209-222, March 1995.

  22. B. P. Johnston, J. M. Sullivan, and A. Kwasnik. Automatic conversion of triangular finite meshes to quadrilateral elements. International Journal of Numerical Methods in Engineering, 31(1):67-84, 1991.

  23. J. Kahn, M. Klawe, and D. Kleitman. Traditional galleries require fewer watchmen. SIAM Journal of Algorithms and Discrete Methods, 4(2):194-206, June 1983.

  24. V. Klee and Pl van den Driessche. Linear algorithms for testing the sign stability of a matrix and for finding z-maximum matchings in acyclic graphs. Numerische Mathematik, 28:273-285, 1977.

  25. A. A. Kooshesh and B. M. E. Moret. Three-coloring the vertices of a triangulated simple polygon. Pattern Recognition, 25, 1992.

  26. M. J. Lai and L. L. Schumaker. Scattered data interpolation using C2 piecewise polynomilas of degree six. In Third Workshop on Proximity Graphs, Starkville, Mississippi, December 1-3 1994. Mississippi State University.

  27. A. Lubiw. Decomposing polygonal regions into convex quadrilaterals. In Proc. of the 1st ACM Symposium on Computational Geometry, pages 97-106, 1985.

  28. S. Micali and V. V. Vazirani. An O(|V|1/2|E|) algorithm for finding maximum matchings in general graphs. In Proc. 21st Annual IEEE Symposium on the Foundations of Computer Science, pages 17-27, 1980.

  29. R. Z. Norman and M. O. Rabin. An algorithm for a minimum cover of a graph. In Proc. American Math. Society, volume 10, pages 315-319, 1959.

  30. C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc., 1982.

  31. J. R. Sack. An O(nlogn) algorithm for decomposing simple rectilinear polygons into convex quadrilaterals. In Proc. 20th Annual Allerton Conference on Communication, Control and Computing, pages 64-75, Urbana, Illinois, October 1982.

  32. J.-R. Sack and G. T. Toussaint. Alinear-time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals. In Proc. 19th Annual Allerton Conf. on Communications, Control and Computing, pages 21-30, Urbana, Ill iois, 1981.

  33. J.-R. Sack and G. T. Toussaint. Guard placement in rectilinear polygons. In G. T. Toussaint, editor, Computational Morphology, pages 153-175. North-Holland, 1988.

  34. L. L. Schumaker. On the dimension of spaces of piecewise polynmials in two variables. In W. Schempp and K. Zeller, editors, Multivariate Approximation Theory, pages 396-411. Birkhauser Verlag, 1979.

  35. V. Srinivasan, L. R. Nackman, J-M. Tang, and S. N. Meshkat. Qutomatic mesh generation using teh symmetric axis transformation of polygonal domains. Proceedings of the IEEE (Special Issue on Computational Geometry), 80(9):1485-1501, 1992 .

  36. G. Toussaint. Quadrangulations of planar sets. In Proc. 4th International Workshop on Algorithms and Data Structures (WADS), volume 955 of LNCS, pages 218-227. Springer-Verlag, 1995.

Top

Please send any comments or questions to: Sam Sanjabi or Rachel Potvin