Encontrar la unión de N círculos aleatorios colocados arbitrariamente (o conspiradoramente) en una superficie bidimensional

Question

Considere una superficie bidimensional poblada por un conjunto de coordenadas cartesianas $(x_i, y_i)$ para $N$ círculos con radios individuales $r_i$ , donde $r_{min} < r_i < r_{max}$ .

Aquí, el número de círculos, $N$ pueden ser grandes, desde cientos hasta decenas de miles. Los círculos pueden poblar escasamente el plano en algunos lugares, y en otros, estar "conspiradoramente" apiñados. Además, $r_{min}$ / $r_{max}$ no es necesario que estén definidos de tal manera que permitan un casco convexo preciso, una interpolación spline, etc.

Aunque siempre podemos realizar un muestreo monte carlo de coordenadas en el plano (o sobre alguna red definida), ¿existe un método determinista eficiente para calcular el área exacta dada por la unión de todas las $N$ ¿Círculos?

---

Actualización - Tras una búsqueda bibliográfica más exhaustiva (¡y gracias a "jc" por mencionar a Edelsbrunner!), he podido encontrar algunos artículos relevantes en la literatura. En primer lugar, el problema de encontrar la unión de 'N' discos fue propuesto por primera vez por M. I. Shamos en su tesis de 1978:

Shamos, M. I. "Computational Geometry" Tesis de doctorado, Yale Univ., New Haven, CT 1978.

En 1985 Micha Sharir presentó una solución O(n $log^2n$ ) de tiempo y O(n) de espacio para el problema de intersección/unión de discos (basado en diagramas de Voronoi modificados): Sharir, M. Problemas de intersección y de pares cercanos para un conjunto de discos planos. SIAM .J Comput. 14 (1985), pp. 448-468.

En 1988, Franz Aurenhammer presentó otro algoritmo más eficiente en tiempo O(n log n) y espacio O(n) para la intersección/unión de círculos (discos) utilizando diagramas de potencia (generalizaciones de los diagramas de Voronoi): Aurenhammer, F. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms 9 (1985), pp. 151-161.

Sería muy bueno si alguien pudiera indicarme una implementación de uno de los dos algoritmos deterministas anteriores, tal vez en un paquete de geometría computacional (ninguno parece trivial de poner en práctica)...

Answer 1

CGAL tiene un módulo general de diagramas de Voronoi que es bastante personalizable. Aunque nunca lo he utilizado para construir diagramas de potencia, no debería ser difícil añadir el tipo correcto de función de distancia para generar los diagramas que necesitas:

http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Voronoi_diagram_2/Chapter_main.html

Answer 2

Creo que Herbert Edelsbrunner ha escrito algunos artículos sobre el tema (para las bolas en $\mathbb{R}^d$ ), aunque su principal interés era d=3. Puede intentar empezar con "La unión de las bolas y su doble forma" que discute alguna estructura útil en todas las dimensiones.

Answer 3

Yo realizaría el DFS en un quadtree hasta el nivel de profundidad deseado. No puedo demostrar que sea óptimo, pero es muy eficiente en cuanto a espacio y puede hacerse en paralelo.

At each level you need to determine::
  If one of the circles does not touch this box then I return empty.
  If all remaining circles cover this box then I return the size of the box.
  Any circles that cover this box I ignore them on future recursions.

Answer 4

El problema fue resuelto completamente por los siguientes documentos:

Un nuevo algoritmo para el cálculo dinámico del perímetro de la unión de arcos circulares， CHEN Jian-xun ZHAO Hui Dept. of Computer Science & technology, Wuhan University of Science & Technology, Wuhan Hubei 430081; Journal of Computer-Aided Design & Computer Graphics，1998-03