RE2L: An Efficient Output-sensitive Algorithm for Computing Boolean Operation on Circular-arc Polygons

Zhi Jie Wang, Xiao Lin, Meie Fang, Bin Yao, Haibing Guan, Minyi Guo

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

  1. 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).
  2. 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.
X-monotone decomposition of circular arcs into simpler segments.
  1. 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.
Identification of related edges using horizontal and vertical spans of intersecting MBRs.
  1. 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

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. The natural problem — boolean operation on linear polygons, has been well studied. Surprisingly, (almost) no article focuses on the problem of boolean operation on circular-arc polygons, which actually can also find many applications, implying that if there is a targeted solution for boolean operation on circular-arc polygons, which should be favourable for potential users. In this article, we devise a concise data structure, and then develop a targeted algorithm called RE2L. Our method is surprisingly simple, easy-to-implement but without loss of efficiency. Given two circular-arc polygons with m and n edges respectively, we prove that the proposed method runs in O(m + n + (l + k) log l) time, using O(m + n + l + k) space, where k is the number of intersections, and l is the number of related edges. The experimental results show our proposed algorithm is significantly faster than the ones that are by directly appealing to the existing algorithms. Index Terms—Boolean operation, circular-arc polygons, related edges, sequence lists, appendix points F 1
BibTeX
@misc{wang2012re,
  author = {Zhi Jie Wang and Xiao Lin and Meie Fang and Bin Yao and Haibing Guan and Minyi Guo},
  title = {{RE2L: An Efficient Output-sensitive Algorithm for Computing Boolean Operation on Circular-arc Polygons}},
  year = {2012},
  eprint = {1211.0729},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.0729},
}
Figure