2012/11/12 by Erich L Foster, Foster, Erich L, James Overfelt +2
Computer Science · Engineering · #3D Shape Modeling and Analysis #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1211.3376
The paper has been withdrawn due to not being able to truly handle all degenerate cases as claimed
openalex publication_date 2012/11/12 · arxiv created 2014/06/16 · arxiv updated 2014/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Polygon clipping is a frequent operation in Arbitrary Lagrangian-Eulerian methods, Computer Graphics, GIS, and CAD. In fact, clipping algorithms are said to be one of the most important operations in computer graphics. Thus, efficient and general polygon clipping algorithms are of great importance. Greiner et al. developed a time efficient algorithm which could clip arbitrary polygons, including concave and self intersecting polygons. However, the Greiner-Hormann algorithm does not properly handle degenerate cases, without the undesirable need for perturbing vertices. We present an extension to the Greiner-Hormann polygon clipping algorithm which properly deals with degenerate cases. We combine the method proposed by Kim et al. and the method mentioned by Liu et al. to remove or properly label degenerate cases. Additionally, the algorithm presented avoids the need for calculating midpoints, doesn't require additional entry/exit flags, and avoids changing the vertex data structure used in the original Greiner-Hormann algorithm, which was required by the extension presented by Kim et al.