Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD

We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and...

Full description

Saved in:
Bibliographic Details
Published in:Computer aided design 2010-12, Vol.42 (12), p.1189-1196
Main Author: Simonson, Lucanus J.
Format: Article
Language:English
Subjects:
Algorithms
Application
Boost
Clipping
Computational geometry
Computer aided design
Computer programs
Integrated circuits
Map overlay
Polygon
Polygon clipping
Polygons
Robustness
Software
Sweep algorithm
Very large scale integration
VLSI
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and satisfies a strict set of post conditions suitable for immediate processing of output polygons by downstream tools. The algorithm uses sweepline to compute a Riemann–Stieltjes integral over polygon overlaps in O ( ( n + s ) log ( n ) ) time given n polygon edges with s intersections. The algorithm is efficient and general, handling degenerate inputs implicitly. Particular care was taken in implementing the algorithm to ensure numerical robustness without sacrificing efficiency. We present performance comparisons with other polygon clipping algorithms and give examples of real world applications of our algorithm in an industrial software setting. ► High performance, capacity and robust polygon clipping and related operations. ► Novel polygon representation and sweep line algorithm for polygon clipping. ► Performance study comparing several implementations of polygon clipping. ► Experience report of applications of polygon clipping and related operations.
ISSN:0010-4485
1879-2685
DOI:10.1016/j.cad.2010.06.008