Área combinada de círculos superpuestos

107

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?

Anton Hansson
fuente
15
Este es un problema realmente interesante, recuerdo haberlo visto en la clase de geometría de la escuela secundaria, pero nunca encontré una solución. Si no puede encontrar una respuesta aquí, intente publicarla en mathoverflow.net y deje que los matemáticos lo intenten : P
Charles Ma
25
a veces los programadores reales necesitan matemáticas reales
fa.
1
¿Qué tal si buscamos la respuesta a esta pregunta: "Tenemos representantes de ventas que viven en estas 4 ubicaciones, cada uno de los cuales da servicio a un área con estos 4 radios. ¿Qué parte del país cubrimos?" Si tenía una base de datos cambiante de representantes de ventas, ¡esto se convierte en una pregunta de programación!
Chris Roberts
5
En realidad, este es el tipo de problema en el que a los programadores reales les gusta pensar.
MAK
2
@zvolkov: las placas de circuito se describen con un lenguaje que despliega cuadrados y círculos hacia abajo y, opcionalmente, los arrastra. "Calcula el área de cobre". (Esto puede ser necesario para calcular los tiempos de grabado, saber si agregar obras de arte de barrido, varias cosas).
DigitalRoss

Respuestas:

97

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.

superposición de círculos

Hormigas Aasma
fuente
17
¿Qué pasa cuando hay un agujero en el centro?
John Gietzen
3
Deberá restar el polígono conectado al centro para el agujero del total y sumar los sectores del círculo para ese polígono al total.
Hormigas Aasma
3
bueno, pero supongo que esto necesitará muchos detalles de implementación para manejar todos los casos especiales (círculo dentro de otro, sin intersección, agujeros, contacto de un punto ...)
fa.
1
Los casos especiales son bastante fáciles. Los círculos dentro de otros se descartan al no tener intersecciones perimetrales. Un punto de contacto es en efecto dos intersecciones con distancia cero. Las formas desconectadas se pueden encontrar a través del algoritmo de componentes conectados sobre el gráfico donde se conectan dos círculos si la distancia de los centros es menor que la suma de los radios. Los agujeros son todos polígonos excepto el que tiene el área más grande. Las intersecciones perimetrales son todas las intersecciones que no están estrictamente dentro de ningún círculo.
Hormigas Aasma
4
sí, pero los bordes de los agujeros también son arcos (pequeños). Sigo pensando que esto necesita mucho código para funcionar bien.
fa.
32

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.
Marca de alto rendimiento
fuente
2
Esto funcionará, pero los métodos Monte-Carlo como este, basados ​​simplemente en un muestreo uniforme, generalmente no tienen las mejores tasas de convergencia.
ShreevatsaR
2
Lo siento, pero aunque aprecio su esfuerzo y creo que su solución es "prácticamente utilizable", considero que su enfoque es muy incorrecto. Este es un problema que puede y debe resolverse mediante las matemáticas, no con la fuerza bruta. Desperdiciar energía y núcleos en problemas como este es un derroche y una generosidad.
mafu
5
Tienes razón, me avergüenzo de mí mismo, pero tengo un grupo con 12.000 núcleos, puedo permitirme ser lujoso. Y no sé cómo hacer que la elegante solución matemática se adapte a tantos procesadores.
Marca de alto rendimiento
8
No hay nada intrínsecamente malo en un enfoque de Monte-Carlo (o cualquier método aleatorio), siempre que brinde el grado de precisión requerido y lo haga en un período de tiempo razonable.
MAK
@mafutrct, ciertamente tienes razón. Sin embargo, es fácil cometer pequeños errores matemáticos. Esta solución proporciona una forma sencilla de probar la corrección.
Richard
18

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.

Ejemplo

  • 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.

Timothy Shields
fuente
Creo que puedo calcular un conjunto de puntos rojos / blancos con bastante facilidad, sin embargo, mi teoría de grafos no es demasiado buena: algorítmicamente, ¿cómo se pasa de una lista de nodos + bordes a un área calculada?
user999305
1
El algoritmo se puede simplificar utilizando un conjunto de triángulos que no se superponen en lugar de polígonos. Los arcos (áreas verdes) son áreas contenidas en un solo círculo. Extiende el tamaño de un polígono a medida que agregas más círculos. (al final puedes olvidar que incluso estás hablando de polígonos). Hace propiedades booleanas y las áreas también son más fáciles de calcular. A medida que un punto rojo hueco se convierte en un punto rojo sólido, simplemente agrega más triángulos a su conjunto y ajusta el arco que se "devora" por más y más círculos que se cruzan.
Steve
16

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.

fa.
fuente
3
Mi conjetura es que esto va a converger más rápidamente que el algoritmo de Monte Carlo punto dentro / fuera también.
Frank Krueger
Esto parece mucho más fácil de implementar. Definitivamente el mejor método de fuerza bruta sugerido. ¡Gracias!
Anton Hansson
la fuerza bruta aquí se llama teorema de compresión
fa.
Ese es el tipo de algoritmo que usa en aritmética de intervalos. en.wikipedia.org/wiki/Interval_arithmetic
rjmunro
13

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)

texto alternativo
(fuente: secretGeek.net )

Leon Bambrick
fuente
1
Creo que hacer el tipo de división de polígonos sugerida por su imagen probablemente sería un muy buen enfoque. Hay muchos detalles que trabajar para codificarlo. ¿Cómo manejaría una cadena de veinte círculos, cada uno de los cuales se superpone solo al último y al siguiente en la cadena? Fácil de averiguar a mano, pero ¿cuál es tu algoritmo?
PeterAllenWebb
4

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.

David R Tribble
fuente
3

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.

Justin
fuente
¿Qué pasa con el formateo? También lamento el uso de n y u para intersección y unión, probablemente haya una mejor manera ...
Justin
1
se agregaron algunos signos de unión Unicode (∪) e intersección (∩). ojalá funcionen.
Spoike
3

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 )

user213660
fuente
2

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.

PeterAllenWebb
fuente
2

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.

Steve Thomas
fuente
1

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.

Greg Reynolds
fuente
1

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.

fryguybob
fuente
0

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 ++

Deepesh Thakur
fuente
-1

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);
broofa
fuente
Esta solución no tiene en cuenta la realización de cálculos matemáticos con las áreas de los círculos. Se pierde el punto de la pregunta de los OP. Muy a menudo, la geometría de renderizado es solo la mitad de la batalla cuando se trata de formas geométricas
Steve