Abstract
The boundaries of conic polygons consist of conic segments or second-degree curves. The conic polygon has two degenerate or special cases: the linear polygon and the circular-arc polygon. While Boolean operations on linear polygons are well-studied, targeted solutions for circular-arc polygons have been surprisingly scarce. In this article, we devise a concise data structure and develop a targeted algorithm called RE2L. Our method is simple and easy to implement without sacrificing efficiency. Given two circular-arc polygons with $m$ and $n$ edges, we prove that RE2L runs in $O(m + n + (l + k) \log l)$ time, where $k$ is the number of intersections and $l$ is the number of related edges. Experimental results demonstrate that our algorithm is significantly faster than existing general-purpose alternatives.
Introduction
Boolean operations—such as union, intersection, and difference—are fundamental building blocks in computational geometry, supporting applications in CAD, GIS, and computer graphics. While these operations are mature for polygons with straight-line boundaries, circular-arc polygons present unique challenges.
Currently, practitioners typically choose between two suboptimal paths: linearization, which approximates curves with many tiny line segments (losing precision and increasing complexity), or general conic solvers, which are designed for complex curves like ellipses and parabolas. The authors of RE2L argue that general solvers are "overkill" for circular arcs, leading to unnecessary computational overhead. RE2L fills this gap by providing a specialized, efficient algorithm specifically for circular-arc geometry.
The RE2L Algorithm
The name RE2L represents the three core pillars of the algorithm: Related edges, Entry-exit properties, and 2 sequence Lists.
Technical Innovations
- APDLL (Appendix Point based Double Linked List): A circular arc cannot be uniquely defined by just two endpoints. RE2L introduces a third "appendix point" to each arc, creating an unambiguous and concise data structure that avoids the complexity of Doubly Connected Edge Lists (DCEL).
- X-monotone Decomposition: To simplify intersection calculations, any arc that "doubles back" on itself horizontally is split into 2 or 3 x-monotone segments. This ensures that any vertical line crosses a segment at most once.
- Related Edges Pruning: Most edges in two overlapping polygons do not actually intersect. RE2L identifies "related edges" by calculating the intersection of the polygons' Minimum Bounding Rectangles (MBRs). By focusing only on edges within the resulting horizontal and vertical spans, the algorithm drastically reduces the search space for intersections.
- Two-Label Sweep-line: During the intersection phase, the algorithm assigns dual labels to each edge to prevent "false" intersections (such as shared vertices) and to accelerate the insertion of new intersection points into the sequence lists.
Performance and Results
The authors evaluated RE2L against industry standards, including the CGAL library and the Berberich algorithm.
- Speed: RE2L was approximately 24x to 25x faster than CGAL and Berberich in initial test cases.
- Scalability: The performance gap widened as the number of edges increased. For polygons with 50 edges, RE2L remained several orders of magnitude faster than general-purpose alternatives.
- Output-Sensitivity: Because the complexity is tied to the number of related edges ($l$) and intersections ($k$), the algorithm is exceptionally efficient when polygons have minimal overlap.
Conclusion
RE2L demonstrates that specializing an algorithm for circular arcs, rather than treating them as general conics, yields massive performance gains. While currently optimized for 2D circular-arc polygons, future work could extend this framework to handle polygons with holes more natively or expand into 3D circular-arc polyhedra for advanced modeling and robotics applications.
Summary updated