Clipping simple polygons with degenerate intersections

Journal article (2019)

Authors

E.L. Foster Robotics Institute, Carnegie Mellon University
Kai Hormann Università della Svizzera Italiana
Affiliation
External organisation
More Info
expand_more

Published Date

2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.