Clipping simple polygons with degenerate intersections. Issue 2 (December 2019)

• Record Type: Journal Article
• Authors: Foster, Erich L; Hormann, Kai; Popa, Romeo Traian
• Is Part Of: Computers & graphics. Issue 2(2019)
• Publication Date: 2019-12
• Subjects: Polygon clipping -- Degenerate intersections; 68U05; Computer graphics -- Periodicals; Computer graphics; Periodicals; 006.605
• DOI: 10.1016/j.cagx.2019.100007
• Languages: English
• ISSNs: 2590-1486

Abstract

Highlights: We develop an extension of the Greiner–Hormann algorithm. Our extension deals with degenerate cases. We demonstrate the new algorithm by several examples. Graphical abstract: Abstract: Polygon clipping is a frequent operation in many fields, including computer graphics, CAD, and GIS. Thus, efficient and general polygon clipping algorithms are of great importance. Greiner and Hormann (1998) propose a simple and time-efficient algorithm that can clip arbitrary polygons, including concave and self-intersecting polygons with holes. However, the Greiner–Hormann algorithm does not properly handle degenerate intersection cases, without the undesirable need for perturbing vertices. We present an extension of the Greiner–Hormann polygon clipping algorithm that properly deals with such degenerate cases.