Quadrilateral Decomposition by Two-Ear Property Resulting in CAD Segmentation

The objective is to split a simply connected polygon into a set of convex quadrilaterals without inserting new boundary nodes. The presented approach consists in repeatedly removing quadrilaterals from the polygon. Theoretical results pertaining to quadrangulation of simply connected polygons are derived from the usual 2-ear theorem. It produces a quadrangulation technique with O(n) number of quadrilaterals. The theoretical methodology is supplemented by practical results and CAD surface segmentation.

Authors:

• Maharavo Randrianarivony

Keywords:

• Quadrangulation
• simply connected
• two-ear theorem.

References:

[1] M. Bern and D. Eppstein, "Quadrilateral Meshing by circle packing",
Int. J. Comput. Geom. Appl., vol. 10, no. 4, pp. 347-360, 2000.
[2] D. Bremner, F. Hurtado, S. Ramaswami and V. Sacristan, Small convex
quadrangulations of point sets, in: Proc. 12th international symposium,
ISAAC 2001, Christchurch, New Zealand, 2001, pp. 623-635.
[3] G. Brunnett, "Geometric design with trimmed surfaces", Computing
Supplementum, vol. 10, pp. 101-115, 1995.
[4] C. Lee and S. Lo, "A new scheme for the generation of a graded
quadrilateral mesh", Comput. Struct., vol. 52, no. 5, pp. 847-857, 1994.
[5] G. Meister, "Polygons have ears", Amer. Math. Mon., vol. 82, pp. 648-
651, 1975.
[6] S. Owen, "Non-simplicial unstructured mesh generation". Ph.D. dissertation,
Dept. Civil Envir. Engin., Carnegie Mellon University, Pennsylvania,
1999.
[7] S. Ramaswami, P. Ramos and G. Toussaint, "Converting triangulations
to quadrangulations", Comput. Geom., vol. 9, no. 4, pp. 257-276, 1998.
[8] M. Randrianarivony, "Geometric processing of CAD data and meshes
as input of integral equation solvers". Ph.D. dissertation, Dept. Comput.
Science, Chemnitz University of Technology, Chemnitz, Germany, 2006.
[9] M. Randrianarivony and G. Brunnett, "Molecular surface decomposition
using geometric techniques", in Proc. Conf. Bildverarbeitung f¨ur die
Medizine, Berlin, 2008, pp. 197-201.
[10] M. Randrianarivony and G. Brunnett, "Preparation of CAD and Molecular
Surfaces for Meshfree Solvers", in Proc. Int. Workshop Meshfree
Methods for PDE, Bonn, 2007, pp. 231-245.