algorithm - Área combinada de círculos superpuestos

geometry area

Question

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

Imagen de ejemplo:

Para dos círculos es bastante fácil,

Solo 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 un algoritmo inteligente que pueda usar cuando hay más de dos círculos?

Answer 1

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. Aproximar 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. Calcule el área del polígono fusionado

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

Obviamente, cuantos más lados uses para cada polígono que se aproxime, más cerca estarás de la respuesta exacta. Podría aproximarse usando polígonos inscritos y circunscritos para obtener límites en la respuesta exacta.

Answer 2

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 simple. El problema anterior se puede resolver en menos de 100 líneas de código, como lo demuestra esta solución JSFiddle (sobre todo porque es conceptualmente mucho más simple y no tiene casos límite ni excepciones para tratar).
2. Se adapta fácilmente a problemas más generales. Funciona con cualquier forma, independientemente de su morfología, siempre que se pueda procesar 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 tendrá un mejor rendimiento a medida que aumente el número de formas.
4. Y hablando de rendimiento, a menudo obtendrá la 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.

El único inconveniente de la pintura de píxeles es la precisión finita de la solución. Pero eso se puede ajustar simplemente renderizando en lienzos más grandes o más pequeños según lo requiera la situación. Tenga en cuenta, también, que el anti-aliasing en el código de renderizado 2D (a menudo activado por defecto) producirá una precisión de nivel mejor que el píxel. Entonces, por ejemplo, renderizar una figura de 100x100 en un lienzo de las mismas dimensiones debería, creo, rendir precisión del orden de 1 / (100 x 100 x 255) = .000039% ... que probablemente sea "lo suficientemente bueno" para todos menos para 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);

Answer 3

Encontré este enlace que puede ser útil. Sin embargo, no parece haber una respuesta definitiva. Respuestas de Google Otra referencia para tres círculos es el teorema de Haruki . Hay un papel allí también.

Answer 4

Encuentra todas las intersecciones de círculo en el perímetro exterior (por ejemplo, B, D, F, H en el siguiente diagrama). Conéctelos junto 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 las secciones del círculo definidas por los puntos de intersección consecutivos y el centro del círculo entre ellos. También necesitarás dar cuenta de cualquier agujero.

Answer 5

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

• pon un cuadro delimitador alrededor de los círculos;
• generar puntos aleatorios dentro del cuadro delimitador;
• averiguar si el punto aleatorio está dentro de uno de los círculos;
• calcule el área mediante una simple adición y división (proportion_of_points_inside * area_of_bounding_box).

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

Answer 6

Hay soluciones eficientes para este problema usando lo que se conoce como diagramas de poder. Sin embargo, esta es una matemática muy pesada y no es algo que quisiera abordar de forma directa. Para una solución "fácil", busque algoritmos de barrido de línea. El principio básico aquí es que divides la figura en tiras, donde calcular el área en cada tira es relativamente fácil.

Por lo tanto, 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. Tenga en cuenta 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 calcular cómo calcular tal forma, simplemente hágalo para todas las formas individuales y agréguelas. 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, puede 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.

Answer 7

He estado trabajando en un problema de simulación de campos de estrellas superpuestos, intentando estimar los recuentos de estrellas verdaderas 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 había esperado 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 vincularlos para ver si hay una superposición (convirtiendo el par de estrellas en amarillo); luego, un conteo de píxeles de los colores genera el área observada para comparar con el área teórica. Esto genera una curva de probabilidad para los conteos verdaderos. Fuerza bruta tal vez, pero parece funcionar bien.
http://www.2from.com/images/simulated_star_field.gif

Answer 8

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

• Determine 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, debo ser capaz de 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/ ).
• Elimina cualquier círculo que esté contenido por completo en otro círculo más grande (mira 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 círculo o de otra manera)

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

Donde A ∪ B significa A unión B y A ∩ B significa A se cruzan B (puede resolver esto desde el primer paso.

• Ahora continúe agregando círculos y siga trabajando en 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 extra C) calculamos el área usando esta fórmula:

(Este es el mismo que el anterior donde A ha sido reemplazado por A∪B )

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

Donde area(A∪B) acabamos de calcular, y el 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.

El truco es el último paso: cuanto más círculos se agregan, más complejo se vuelve. Creo que hay una expansión para calcular el área de una intersección con una unión finita o, alternativamente, puedes calcularlo recursivamente.

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

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

Answer 9

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

• Los puntos azules son centros de círculo.
• Los puntos rojos son intersecciones de límites circulares.
• Los puntos rojos con interior blanco son intersecciones de límites circulares que no están contenidas 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 son los puntos azules y los puntos rojos con el interior blanco. Para cada círculo, coloque un borde entre el círculo medio (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 circulares (sombreados en verde) que están disjuntos por parejas 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 al sumar las áreas de las piezas.

Answer 10

Me encanta el enfoque para el 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 proporcionar una mejor comprensión de la generalización del algoritmo para un mayor número de círculos superpuestos.

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

(en la práctica, tal vez vale la pena el método monte-carlo)

texto alternativo http://secretGeek.net/image/triangles_1667310.png

Answer 11

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

Esto también funciona para cualquier unión de formas si puede decir si un cuadrado está dentro o fuera o interseca la forma.

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

El algoritmo consiste en "dibujar" los círculos en el árbol quad 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 completa,
• fuera de todos los círculos, marque la celda como vacía,
• De lo contrario, marque la celda como parcial.

Cuando está hecho, puede calcular una estimación del área: las celdas llenas 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 que obtenga 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.

Answer 12

Según el problema que intente resolver, podría ser suficiente para 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 para que ninguno de los círculos se superponga. Para mejor, 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 esos 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 puede obtener un límite superior mejor si usa la fórmula de par en pares arbitrarios en lugar de solo la suma de todos los círculos. Puede haber una buena manera de elegir los "mejores" pares (los pares que dan como resultado el área total mínima).

Dado un límite superior e inferior, es posible que puedas sintonizar mejor un enfoque de Montecarlo, pero no te viene a la mente nada específico. Otra opción (de nuevo 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.

Answer 13

Si desea una respuesta discreta (en oposición a una respuesta continua), podría 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 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 la cantidad de celdas de color en la cuadrícula.