×

A practical algorithm for decomposing polygonal domains into convex polygons by diagonals. (English) Zbl 1154.68542

Summary: 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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
90B85 Continuous location
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry
52B55 Computational aspects related to convexity

Software:

FIST
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Chazelle B, Dobkin DP (1985) Optimal convex decompositions. In: Computational geometry. Elsevier, Amsterdam, pp 63–133
[3] Denardo EV (1982) Dynamic programming: models and applications. Prentice-Hall, New York
[4] Drezner Z (ed) (1995) Facility location. A survey of applications and methods. Springer series in operations research. Springer, New York
[5] Elmaghraby SE (1970) The concept of ’State’ in discrete dynamic programming. J Math Anal Appl 29:523–557 · Zbl 0191.49201 · doi:10.1016/0022-247X(70)90066-1
[6] 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
[7] 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) · Zbl 0948.90153 · doi:10.1016/S0377-2217(97)00225-7
[8] 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
[9] 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 · Zbl 0973.90058 · doi:10.1016/S0377-2217(99)00033-8
[10] 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
[11] Havran V, Purgathofer W (2003) On comparing ray shooting algorithms. Comput Graph 27:593–604 · doi:10.1016/S0097-8493(03)00103-1
[12] Held M (2001) FIST: Fast industrial-strength triangulation of polygons. Algorithmica 30:563–596 · Zbl 0980.65019 · doi:10.1007/s00453-001-0028-4
[13] Held M (2008) Private communication
[14] 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 · Zbl 0521.68040
[15] Keil JM (1985) Decomposing a polygon into simpler components. SIAM J Comput 14:799–817 · Zbl 0575.68077 · doi:10.1137/0214056
[16] Keil JM, Snoeyink J (2002) On the time bound for convex decomposition of simple polygons. Int J Comput Geom Appl 12:181–192 · Zbl 1152.68670 · doi:10.1142/S0218195902000803
[17] Lien JM, Amato NM (2004) Approximate convex decomposition of polygons. In: Proceedings of the 20th annual ACM symposium on computational geometry, pp 17–26 · Zbl 1376.68152
[18] Lingas A (1982) The power of non-rectilinear holes. In: Automata, languages and programming, Aarhus, 1982. Springer, Berlin, pp 369–383
[19] 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
[20] O’Rourke J (1994) Computational geometry in C. Cambridge University Press, Cambridge
[21] O’Rourke J (1996) Computational geometry column 29. Int J Comput Geom Appl 6:507–511 · Zbl 0900.68427 · doi:10.1142/S0218195996000319
[22] 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 · Zbl 0733.68092
[23] Toussaint GT (1989) Computing geodesic properties inside a simple polygon. Rev d’Intell Artif 3:9–42
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.