Área combinada de círculos superpuestos

Recientemente me encontré con un problema en el que tenía cuatro círculos (puntos medios y radio) y tenía que calcular el área de la unión de estos círculos.

Imagen de ejemplo:

Para dos círculos es bastante fácil

Puedo calcular la fracción del área de cada círculo que no está dentro de los triángulos y luego calcular el área de los triángulos.

Pero, ¿hay algún algoritmo inteligente que pueda usar cuando hay más de dos círculos?

Encuentre todas las intersecciones de círculos en el perímetro exterior (por ejemplo, B, D, F, H en el siguiente diagrama). Conéctelos con los centros de los círculos correspondientes para formar un polígono. El área de la unión de los círculos es el área del polígono + el área de los cortes del círculo definidos por puntos de intersección consecutivos y el centro del círculo entre ellos. También deberá tener en cuenta los agujeros.

Estoy seguro de que hay un algoritmo inteligente, pero aquí hay uno tonto para evitar tener que buscarlo;

• poner un cuadro delimitador alrededor de los círculos;
• generar puntos aleatorios dentro del cuadro delimitador;
• averigua si el punto aleatorio está dentro de uno de los círculos;
• Calcule el área mediante una simple suma y división (proporción_de_puntos_dentro * área_de_caja_de_borde).

Seguro que es tonto, pero:

• puede obtener una respuesta tan precisa como desee, solo genere más puntos;
• funcionará para cualquier forma para la que pueda calcular la distinción interior / exterior;
• se paralelizará maravillosamente para que pueda usar todos sus núcleos.

La respuesta de Ants Aasma dio la idea básica, pero quería hacerlo un poco más concreto. Observe los cinco círculos a continuación y la forma en que se han descompuesto.

• Los puntos azules son centros circulares.
• Los puntos rojos son intersecciones de límites circulares.
• Los puntos rojos con el interior blanco son intersecciones de límites de círculos que no están contenidos en ningún otro círculo .

Identificar estos 3 tipos de puntos es fácil. Ahora construya una estructura de datos de gráfico donde los nodos sean los puntos azules y los puntos rojos con el interior blanco. Para cada círculo, coloque un borde entre el medio del círculo (punto azul) y cada una de sus intersecciones (puntos rojos con interior blanco) en su límite.

Esto descompone la unión circular en un conjunto de polígonos (sombreados en azul) y trozos circulares (sombreados en verde) que están separados por pares y cubren la unión original (es decir, una partición). Dado que cada pieza aquí es algo que es fácil de calcular el área de, puede calcular el área de la unión sumando las áreas de las piezas.

Para una solución diferente a la anterior, podría producir una estimación con una precisión arbitraria utilizando un quadtree.

Esto también funciona para cualquier unión de forma si puede saber si un cuadrado está dentro o fuera o se cruza con la forma.

Cada celda tiene uno de los estados: vacío, lleno, parcial

El algoritmo consiste en "dibujar" los círculos en el quadtree comenzando con una resolución baja (4 celdas, por ejemplo, marcadas como vacías). Cada celda es:

• dentro de al menos un círculo, luego marque la celda como llena,
• fuera de todos los círculos, marque la celda como vacía,
• de lo contrario, marque la celda como parcial.

Cuando haya terminado, puede calcular una estimación del área: las celdas completas dan el límite inferior, las celdas vacías dan el límite superior, las celdas parciales dan el error de área máxima.

Si el error es demasiado grande para usted, refine las celdas parciales hasta obtener la precisión correcta.

Creo que esto será más fácil de implementar que el método geométrico que puede requerir manejar muchos casos especiales.

Me encanta el enfoque del caso de 2 círculos que se cruzan; así es como usaría una ligera variación del mismo enfoque para el ejemplo más complejo.

Podría dar una mejor idea de la generalización del algoritmo para un mayor número de círculos semi superpuestos.

La diferencia aquí es que empiezo por vincular los centros (por lo que hay un vértice entre el centro de los círculos, en lugar de entre los lugares donde los círculos se cruzan). Creo que esto permite generalizar mejor.

(en la práctica, quizás valga la pena el método montecarlo)

_{(fuente: secretGeek.net )}

Si desea una respuesta discreta (en lugar de una continua), puede hacer algo similar a un algoritmo de pintura de píxeles.

Dibuja los círculos en una cuadrícula y luego colorea cada celda de la cuadrícula si está mayormente contenida dentro de un círculo (es decir, al menos el 50% de su área está dentro de uno de los círculos). Haga esto para toda la cuadrícula (donde la cuadrícula abarca toda el área cubierta por los círculos), luego cuente el número de celdas coloreadas en la cuadrícula.

Hmm, problema muy interesante. Mi enfoque probablemente sería algo similar a lo siguiente:

• Encuentre una forma de averiguar cuáles son las áreas de intersección entre un número arbitrario de círculos, es decir, si tengo 3 círculos, necesito poder determinar cuál es la intersección entre esos círculos. El método "Monte-Carlo" sería una buena forma de aproximar esto ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
• Elimine cualquier círculo que esté contenido por completo en otro círculo más grande (mire el radio y el módulo de la distancia entre el centro de los dos círculos). No creo que sea obligatorio.
• Elija 2 círculos (llámelos A y B) y calcule el área total usando esta fórmula:

(esto es cierto para cualquier forma, ya sea circular o no)

area(A∪B) = area(A) + area(B) - area(A∩B)

Donde A ∪ Bsignifica A unión B y A ∩ Bsignifica A intersección B (puede resolver esto desde el primer paso.

• Ahora continúe agregando círculos y continúe calculando el área agregada como una suma / resta de áreas de círculos y áreas de intersecciones entre círculos. Por ejemplo, para 3 círculos (llame al círculo adicional C) calculamos el área usando esta fórmula:

(Esto es lo mismo que arriba donde Ase ha reemplazado por A∪B)

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

Donde area(A∪B)acabamos de hacer ejercicio y area((A∪B)∩C)se puede encontrar:

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

Donde nuevamente puedes encontrar el área (A∩B∩C) desde arriba.

Lo complicado es el último paso: cuantos más círculos se agregan, más complejo se vuelve. Creo que hay una expansión para resolver el área de una intersección con una unión finita, o, alternativamente, es posible que pueda resolverlo de forma recursiva.

También con respecto al uso de Monte-Carlo para aproximar el área de la sección, creo que es posible reducir la intersección de un número arbitrario de círculos a la intersección de 4 de esos círculos, que se pueden calcular exactamente (no tengo idea de cómo hacer esto sin embargo).

Probablemente haya una mejor manera de hacer esto por cierto: la complejidad aumenta significativamente (posiblemente exponencialmente, pero no estoy seguro) por cada círculo adicional agregado.

He estado trabajando en un problema de simulación de campos de estrellas superpuestos, tratando de estimar los recuentos de estrellas reales a partir de las áreas reales del disco en campos densos, donde las estrellas brillantes más grandes pueden enmascarar las más débiles. Yo también esperaba poder hacer esto mediante un análisis formal riguroso, pero no pude encontrar un algoritmo para la tarea. Lo resolví generando los campos de estrellas sobre un fondo azul como discos verdes, cuyo diámetro fue determinado por un algoritmo de probabilidad. Una rutina simple puede emparejarlos para ver si hay una superposición (volviendo amarillo el par de estrellas); luego, un recuento de píxeles de los colores genera el área observada para compararla con el área teórica. Esto luego genera una curva de probabilidad para los conteos verdaderos. Tal vez la fuerza bruta, pero parece funcionar bien. _{(fuente: 2from.com )}

Aquí hay un algoritmo que debería ser fácil de implementar en la práctica y podría ajustarse para producir un error arbitrariamente pequeño:

1. Aproxime cada círculo por un polígono regular centrado en el mismo punto
2. Calcula el polígono que es la unión de los círculos aproximados
3. Calcular el área del polígono fusionado

Los pasos 2 y 3 se pueden llevar a cabo utilizando algoritmos estándar fáciles de encontrar de geometría computacional.

Obviamente, cuantos más lados use para cada polígono aproximado, más cercana será su respuesta exacta. Puede realizar una aproximación utilizando polígonos inscritos y circunscritos para obtener límites en la respuesta exacta.

Existen soluciones eficientes a este problema utilizando lo que se conoce como diagramas de potencia. Sin embargo, esta es una matemática realmente pesada y no es algo que me gustaría abordar de inmediato. Para una solución "fácil", busque algoritmos de barrido de línea. El principio básico aquí es que divide la figura en tiras, donde calcular el área en cada tira es relativamente fácil.

Entonces, en la figura que contiene todos los círculos sin nada borrado, dibuje una línea horizontal en cada posición que sea la parte superior de un círculo, la parte inferior de un círculo o la intersección de 2 círculos. Observe que dentro de estas tiras, todas las áreas que necesita calcular tienen el mismo aspecto: un "trapecio" con dos lados reemplazados por segmentos circulares. Entonces, si puede averiguar cómo calcular esa forma, simplemente hágalo para todas las formas individuales y súmelas. La complejidad de este enfoque ingenuo es O (N ^ 3), donde N es el número de círculos en la figura. Con un uso inteligente de la estructura de datos, podría mejorar este método de barrido de línea a O (N ^ 2 * log (N)), pero a menos que realmente lo necesite, probablemente no valga la pena.

Encontré este enlace que puede ser útil. Sin embargo, no parece haber una respuesta definitiva. Google responde . Otra referencia para tres círculos es el teorema de Haruki . Allí también hay un periódico.

Dependiendo del problema que esté tratando de resolver, podría ser suficiente obtener un límite superior e inferior. Un límite superior es fácil, solo la suma de todos los círculos. Para un límite inferior, puede elegir un solo radio de modo que ninguno de los círculos se superponga. Para mejorar eso, encuentre el radio más grande (hasta el radio real) para cada círculo para que no se superponga. También debería ser bastante trivial eliminar cualquier círculo completamente superpuesto (todos estos círculos satisfacen | P_a - P_b | <= r_a) donde P_a es el centro del círculo A, P_b es el centro del círculo B y r_a es el radio de A ) y esto mejora tanto el límite superior como el inferior. También podría obtener un límite superior mejor si usa su fórmula de pares en pares arbitrarios en lugar de solo la suma de todos los círculos. Puede haber una buena forma de elegir el "mejor"

Dado un límite superior e inferior, es posible que pueda ajustar mejor un enfoque de Montecarlo, pero no se le ocurre nada específico. Otra opción (nuevamente dependiendo de su aplicación) es rasterizar los círculos y contar píxeles. Básicamente es el enfoque de Montecarlo con una distribución fija.

Esto se puede resolver usando el teorema de Green , con una complejidad de n ^ 2log (n). Si no está familiarizado con el teorema de Green y desea saber más, aquí está el video y las notas de Khan Academy. Pero por el bien de nuestro problema, creo que mi descripción será suficiente.

Perdón por los enlaces a las fotos, ya que no puedo publicar imágenes (no hay suficientes puntos de reputación)

Ecuación general del teorema de Green

Si pongo L y M tal que

Condición

entonces el RHS es simplemente el área de la Región R y se puede obtener resolviendo la integral cerrada o LHS y esto es exactamente lo que vamos a hacer.

Todas las uniones pueden dividirse en conjuntos de círculos tan inconexos que se cruzan

Entonces, integrar a lo largo del camino en sentido antihorario nos da el Área de la región e integrar a lo largo de las agujas del reloj nos da el negativo del Área . Entonces

AreaOfUnion = (Integración a lo largo de arcos rojos en sentido antihorario + Integración a lo largo de arcos azules en sentido horario)

Pero el truco genial es si para cada círculo, si integramos los arcos que no están dentro de ningún otro círculo, obtenemos nuestra área requerida, es decir, obtenemos la integración en sentido antihorario a lo largo de todos los arcos rojos y la integración a lo largo de todos los arcos azules en el sentido de las agujas del reloj. ¡¡¡TRABAJO HECHO!!!

Incluso se solucionan los casos en los que un círculo no se cruza con ningún otro.

Aquí está el enlace de GitHub a mi código C ++

El enfoque de pintura de píxeles (como lo sugiere @Loadmaster) es superior a la solución matemática en una variedad de formas:

1. La implementación es mucho más sencilla. El problema anterior se puede resolver en menos de 100 líneas de código, como lo demuestra esta solución JSFiddle (principalmente porque es conceptualmente mucho más simple y no tiene casos extremos ni excepciones que tratar).
2. Se adapta fácilmente a problemas más generales. Funciona con cualquier forma, independientemente de la morfología, siempre que se pueda renderizar con bibliotecas de dibujo 2D (es decir, "¡todas!"): Círculos, elipses, splines, polígonos, lo que sea. Diablos, incluso imágenes de mapa de bits.
3. La complejidad de la solución de pintura de píxeles es ~ O [n], en comparación con ~ O [n * n] para la solución matemática. Esto significa que funcionará mejor a medida que aumente el número de formas.
4. Y hablando de rendimiento, a menudo obtendrá aceleración de hardware de forma gratuita, ya que la mayoría de las bibliotecas 2D modernas (como el lienzo de HTML5, creo) descargarán el trabajo de renderizado a los aceleradores de gráficos.

La única desventaja de la pintura de píxeles es la precisión finita de la solución. Pero eso se puede ajustar simplemente renderizando a lienzos más grandes o más pequeños según lo requiera la situación. Tenga en cuenta también que el suavizado en el código de renderizado 2D (a menudo activado de forma predeterminada) producirá una precisión mejor que el nivel de píxel. Entonces, por ejemplo, renderizar una figura de 100x100 en un lienzo de las mismas dimensiones debería, creo, producir una precisión del orden de 1 / (100 x 100 x 255) = .000039% ... lo cual probablemente sea "suficientemente bueno" para todos menos los problemas más exigentes.

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>

// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);