Decomposing a simple polygon into trapezoids

摘要: Chazelle's triangulation [1] forms today the common basis for linear-time Euclidean shortest path (ESP) calculations (where start and end point are given within a simple polygon). This paper provides an alternative method subdividing polygon into "basic shapes", using trapezoids instead of triangles. The authors consider presented as being substantially simpler than method. However, it requires sorting step (of subset vertices polygon); all other subprocesses linear time.