Quadrilateral Decomposition by Two-Ear Property Resulting in CAD Segmentation

Authors: Maharavo Randrianarivony

Abstract:

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.

Keywords: Quadrangulation, simply connected, two-ear theorem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056004

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.