Abstract
We present algorithms for decomposing a polygon (with holes) into convex polygons by diagonals. The methods are computationally quick, and although the partitions that they produce may not have minimal cardinality they usually have a low number of convex pieces. Thus, the methods are suitable for being used when achieving a modest load on the CPU time is more important than finding optimal decompositions as, for instance, in location problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Auer T, Held M (1996) RPG—Heuristics for the generation of random polygons. In: Proc 8th Canad conf comput geom. Carleton University Press, Ottawa, pp 38–44
Chazelle B, Dobkin DP (1985) Optimal convex decompositions. In: Computational geometry. Elsevier, Amsterdam, pp 63–133
Denardo EV (1982) Dynamic programming: models and applications. Prentice-Hall, New York
Drezner Z (ed) (1995) Facility location. A survey of applications and methods. Springer series in operations research. Springer, New York
Elmaghraby SE (1970) The concept of ‘State’ in discrete dynamic programming. J Math Anal Appl 29:523–557
Fernández J (1999) New techniques for design and solution of continuous location models (in Spanish). PhD dissertation thesis, Dpto. Estadística e Investigación Operativa, Universidad de Murcia, Murcia, Spain
Fernández J, Cánovas L, Pelegrín B (1997) DECOPOL—codes for decomposing a polygon into convex subpolygons. Eur J Oper Res 102:242–243 (ORSEP section)
Fernández J, Cánovas L, Pelegrín B (1998) Decomposing a polygonal region with holes into convex polygonal subregions. In: X meeting of the Euro working group on locational analysis (EWGLA10), Murcia, Spain
Fernández J, Cánovas L, Pelegrín B (2000) Algorithms for the decomposition of a polygon into convex polygons. Eur J Oper Res 121:330–342
Greene DH (1983) The decomposition of polygons into convex parts. In: Preparata FP (ed) Computational geometry. Adv comput res, vol 1. JAI Press, Greenwich, pp 235–259
Havran V, Purgathofer W (2003) On comparing ray shooting algorithms. Comput Graph 27:593–604
Held M (2001) FIST: Fast industrial-strength triangulation of polygons. Algorithmica 30:563–596
Held M (2008) Private communication
Hertel S, Mehlhorn K (1983) Fast triangulation of simple polygons. In: Proc 4th internat conf found comput theory. Lecture notes in computer science, vol 158. Springer, New York, pp 207–218
Keil JM (1985) Decomposing a polygon into simpler components. SIAM J Comput 14:799–817
Keil JM, Snoeyink J (2002) On the time bound for convex decomposition of simple polygons. Int J Comput Geom Appl 12:181–192
Lien JM, Amato NM (2004) Approximate convex decomposition of polygons. In: Proceedings of the 20th annual ACM symposium on computational geometry, pp 17–26
Lingas A (1982) The power of non-rectilinear holes. In: Automata, languages and programming, Aarhus, 1982. Springer, Berlin, pp 369–383
Narkhede A, Manocha D (1995) Fast polygon triangulation based on Seidel’s algorithm. In: Paeth AW (ed) Graphics gems V. Academic Press, San Diego, pp 394–397
O’Rourke J (1994) Computational geometry in C. Cambridge University Press, Cambridge
O’Rourke J (1996) Computational geometry column 29. Int J Comput Geom Appl 6:507–511
Seidel R (1991) A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput Geom Theory Appl 1:51–64
Toussaint GT (1989) Computing geodesic properties inside a simple polygon. Rev d’Intell Artif 3:9–42
Author information
Authors and Affiliations
Corresponding author
Additional information
In memory of Lázaro Cánovas (1967–2006).
Part of the results in this paper are from Fernández (1999), and were presented in Fernández et al. (1998). This work has been supported by the Ministry of Science and Technology of Spain under the research projects BEC2002-01026, SEJ2005-06273/ECON (J. Fernández, B. Tóth and B. Pelegrín) and TIC2003-05982-C05-03 (L. Cánovas), in part financed by the European Regional Development Fund (ERDF).
Rights and permissions
About this article
Cite this article
Fernández, J., Tóth, B., Cánovas, L. et al. A practical algorithm for decomposing polygonal domains into convex polygons by diagonals. TOP 16, 367–387 (2008). https://doi.org/10.1007/s11750-008-0055-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-008-0055-2