Polygon Partitioning

The key strategy for solving problems on simple polygons is to decompose simple polygons in simpler polygons. A trapezoid is a quadrilateral with at least two parallel edges. Note that a triangle is a degenerated trapezoid with a zero-length edge. The trapezoidalization algorithm relies on the sweep line technique and it has three major steps: This implies looking for the nearest edge of P, above v or below v, with the constraint that a vertical segment (called the visibility segment) drawn from v to such an edge lies entirely within P. For example, in the above figure, for vertex v1 there are two such edges, for vertex v2 there is only one such edge, and for vertex v3 there is no such edge. The visibility segments define the trapezoidalization. The polygon is decomposed into trapezoids with vertical parallel edges (visibility segments) It remains to describe how we can compute visibility segments quickly. We can use the rectangle_intersection algorithm with following changes: Hence, e

The key strategy for solving problems on simple polygons is to decompose simple polygons in simpler polygons. A trapezoid is a quadrilateral with at least two parallel edges. Note that a triangle is a degenerated trapezoid with a zero-length edge. The trapezoidalization algorithm relies on the sweep line technique and it has three major steps: This implies looking for the nearest edge of P, above v or below v, with the constraint that a vertical segment (called the visibility segment) drawn from v to such an edge lies entirely within P. For example, in the above figure, for vertex v1 there are