Résumé: A new algorithm for decomposing non-monotone planar polygons, which may contain holes, into trapezoids is described. The holes may be nested and may have common edges. In the first part of the paper, the main idea is explained for non-monotone polygons without holes, and the algorithm is then extended to polygons containing holes; the holes can also be decomposed into trapezoids, if desired. Finally, it is shown that the algorithm performs trapezoidation of general polygons in O(n2 log 2 n) time, where n is the common number of polygon vertices.

Langue: Anglais