Efficient algorithms for polygon to trapezoid decomposition and trapezoid corner stitching
Qiao Li, Sung‐Mo Kang · 2000
In non-Manhattan geometry layout extraction, polygon to trapezoid decomposition is an indispensable step. Its efficiency and the organization of generated trapezoids significantly affect the performance of layout extractors. We present a new polygon to trapezoid decomposition algorithm used in our layout extractor iLEX. The concept of edge pair and scanline interval are introduced to provide improved efficiency over conventional scanline algorithms. Definitions for trapezoid corner stitches are provided as well as integrated algorithms on corner stitching trapezoids generated. Complexity analysis shows that our scanline algorithm has an expected computation time of O(n log n), and an expected space of O(√n), where n is the number of non-vertical edges in the given layout.