Implementation of the Sharir or Aurenhammer deterministic algorithm for calculating the intersection / union of circles N

Question

The problem of finding the intersection / union of 'N' discs / circles on a flat plane was first proposed by M. I. Shamos in a 1978 thesis:

Chamos, M. I. "Computational Geometry" Candidate of Technical Sciences. Thesis, Yale University, New Haven, CT 1978.

Since then, in 1985, Misha Sharir introduced O (n log2n) time and O (n) spatial deterministic algorithm for the intersection / union of a disk (based on modified Voronoi diagrams): Sharir M. Intersection and the nearest pairs for a set of flat disks. SIAM.J Comput. 14 (1985), pp. 448-468.

In 1988, Franz Aurenhammer introduced a more efficient O (n log n) time and O (n) spatial algorithm for intersecting / joining circles using force diagrams (generalization of Voronoi diagrams): Aurenhammer, F. Improved algorithms for disks and balls using force diagrams. Journal of Algorithms 9 (1985), pp. 151-161.

Earlier in 1983, Paul G. Spirakis also introduced the O (n ^ 2) deterministic time algorithm and the O (n) probabilistic algorithm: Spirakis, PG Very fast algorithms for the many-union area. Report 98, department. Sci., Courant Institute, New York University, 1983.

---

I searched for any implementation of the algorithms above, focusing on computational geometry packages, and I haven't found anything yet. Since not one of them seems trivial for practical use, it would be really neat if someone could point me in the right direction!

Perhaps a structural solid geometry (CSG) design would have the function of a surface region for overlapping environment primitives?

Answer 1

I spent some time studying algorithms for calculating the union of multiple balls — as you have noticed, this is done using generalized Voronoi diagrams.

The CGAL library has a package that implements the union of balls . This one dimension is higher than what interests you, and it does not handle intersections. therefore there is probably no cigar.

If you work in 2 dimensions, the problem is equivalent to detecting a convex hull in three dimensions. You can use convex body material from CGAL or another package.

If you are looking for implementations of your defined algorithms, I cannot help you. But if you just want to find a power diagram that makes it easy to calculate alliances and intersections, it might be easier than you think to roll your own using the 3D convex hull algorithm.

Sorry for the half-baked answer, but we can start with something and see how flexible you are.

Edit: There is also a CGAL package for two-dimensional power management diagrams: http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html .

In addition, @RGrey found a CGAL library for computing two-dimensional Boolean numbers for generalized polygons, including circles at http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html .

Answer 2

CGAL does not have a two-dimensional force diagram implementation. The link suggested above (http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html) is for an additive weighted Voronoi diagram that uses Euclidean weight + instead of Euclidean ^ 2 + weight (as power charts do this).