Al fin luego de mucho trabajar hemos encontrado el resultado de esta incógnita que tantos lectores de este sitio han tenido. Si tienes algún detalle que aportar no dejes de compartir tu comentario.
Solución:
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;
- coloque 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. Eche 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írculos.
- Los puntos rojos son intersecciones de límites circulares.
- Los puntos rojos con interior blanco son intersecciones de límites circulares que son no figura en ningún otro círculo.
Identificar estos 3 tipos de puntos es fácil. Ahora construya una estructura de datos gráfica donde los nodos son 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.
Nos puedes añadir valor a nuestra información colaborando tu veteranía en las notas.