Portal de Periódicos da CAPES

Algorithms for the decomposition of a polygon into convex polygons

2000; Elsevier BV; Volume: 121; Issue: 2 Linguagem: Inglês

10.1016/s0377-2217(99)00033-8

1872-6860

José Fernández, L. Cánovas, Blas Pelegrı́n,

Robotic Path Planning Algorithms

Decomposing a non-convex polygon into simpler subsets has been a recurrent theme in the literature due to its many applications. In this paper, we present different algorithms for decomposing a polygon into convex polygons without adding new vertices as well as a procedure, which can be applied to any partition, to remove the unnecessary edges of a partition by merging the polygons whose union remains a convex polygon. Although the partitions produced by the algorithms may not have minimal cardinality, their easy implementation and their quick CPU times even for polygons with many vertices make them very suitable to be used when optimal decompositions are not required, as for instance, in constrained optimization problems having as feasible set a non-convex polygon (optimization problems are usually easier to solve in convex regions and making use of a branch and bound process or other techniques, it is not necessary to find the optimal solution in all the subsets, so finding convex decomposition with minimal cardinality may be time-wasting). Computational experiments are presented and analyzed.