کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
440278 690990 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر گرافیک کامپیوتری و طراحی به کمک کامپیوتر
پیش نمایش صفحه اول مقاله
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 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))O((n+s)log(n)) time given nn polygon edges with ss 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.

Research highlights
► 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer-Aided Design - Volume 42, Issue 12, December 2010, Pages 1189–1196
نویسندگان
,