Área combinada de círculos sobrepostos

107

Recentemente me deparei com um problema onde tinha quatro círculos (pontos médios e raio) e tive que calcular a área de união desses círculos.

Imagem de exemplo:

Para dois círculos é muito fácil,

Posso apenas calcular a fração da área de cada círculo que não está dentro dos triângulos e depois calcular a área dos triângulos.

Mas existe um algoritmo inteligente que posso usar quando há mais de dois círculos?

Anton Hansson
fonte
15
Este é um problema muito interessante, lembro-me de ter visto isso na aula de geometria do colégio, mas nunca encontrei uma solução. Se você não conseguir encontrar uma resposta aqui, tente postá-la em mathoverflow.net e deixe os matemáticos darem uma olhada : P
Charles Ma
25
às vezes, os programadores reais precisam de matemática real
fa.
1
Que tal descobrir a resposta a esta pergunta - "Temos representantes de vendas morando nesses 4 locais, cada um dos quais atendendo em uma área com esses 4 raios. Quanto do país cobrimos?" Se você tiver um banco de dados de representantes de vendas em constante mudança, isso se torna uma questão de programação!
Chris Roberts
5
Na verdade, esse é o tipo de problema em que os programadores reais gostam de pensar.
MAK
2
@zvolkov: as placas de circuito são descritas com uma linguagem que estampa quadrados e círculos para baixo e, opcionalmente, os arrasta. "Calcule a área de cobre". (Isso pode ser necessário para calcular os tempos de gravação, saber se deve adicionar arte de limpeza, várias coisas.)
DigitalRoss

Respostas:

97

Encontre todas as interseções do círculo no perímetro externo (por exemplo, B, D, F, H no diagrama a seguir). Conecte-os com os centros dos círculos correspondentes para formar um polígono. A área da união dos círculos é a área do polígono + a área das fatias do círculo definidas por pontos de intersecção consecutivos e o centro do círculo entre eles. Você também precisará levar em consideração quaisquer buracos.

círculo sobreposto

Formigas Aasma
fonte
17
O que acontece quando há um buraco no centro?
John Gietzen
3
Você precisará subtrair o polígono conectado ao centro para o furo do total e adicionar as fatias do círculo desse polígono ao total.
Formigas Aasma
3
bom, mas acho que vai precisar de muitos detalhes de implementação para lidar com todos os casos especiais (círculo dentro de outro, sem interseção, buracos, um ponto de contato ...)
fa.
1
Os casos especiais são muito fáceis. Círculos dentro de outros são descartados por não terem interseções de perímetro. Um ponto de contato é, na verdade, duas interseções com distância zero. Formas desconectadas podem ser encontradas por meio do algoritmo de componentes conectados sobre o gráfico, onde dois círculos são conectados se a distância dos centros for menor que a soma dos raios. Os furos são todos polígonos, exceto aquele com a maior área. As interseções de perímetro são todas as interseções que não estão estritamente dentro de um círculo.
Formigas Aasma
4
sim, mas as bordas dos buracos também são arcos (pequenos). Ainda acho que isso precisa de muito código para funcionar bem.
fa.
32

Tenho certeza de que existe um algoritmo inteligente, mas aqui está um burro para evitar que você tenha que procurá-lo;

  • coloque uma caixa delimitadora ao redor dos círculos;
  • gerar pontos aleatórios dentro da caixa delimitadora;
  • descobrir se o ponto aleatório está dentro de um dos círculos;
  • calcule a área por alguma adição e divisão simples (proporção_of_points_inside * area_of_bounding_box).

Claro que é idiota, mas:

  • você pode obter uma resposta tão precisa quanto deseja, basta gerar mais pontos;
  • funcionará para quaisquer formas para as quais você possa calcular a distinção interna / externa;
  • ele vai paralelizar perfeitamente para que você possa usar todos os seus núcleos.
Marca de alto desempenho
fonte
2
Isso vai funcionar, mas métodos de Monte-Carlo como este, baseados simplesmente em amostragem uniforme, geralmente não têm as melhores taxas de convergência.
ShreevatsaR
2
Desculpe, mas embora eu aprecie seu esforço e pense que sua solução é "praticamente utilizável", considero sua abordagem muito errada. Este é um problema que pode e deve ser resolvido por meio da matemática, não da força bruta. Desperdiçar energia e núcleos em problemas como esse é um desperdício e extravagante.
mafu
5
Você está certo, tenho vergonha de mim mesmo, mas tenho um cluster com 12.000 núcleos, posso me dar ao luxo de ser pródigo. E eu não consigo descobrir como fazer a solução matemática elegante ser escalada para tantos processadores.
Alto desempenho Marcos
8
Não há nada inerentemente errado com uma abordagem de Monte-Carlo (ou qualquer abordagem aleatória), desde que forneça o grau necessário de precisão e o faça em um período de tempo razoável.
MAK
@mafutrct, você está certo. No entanto, é fácil cometer pequenos erros matemáticos. Esta solução fornece uma maneira simples de testar a correção.
Richard
18

A resposta das formigas Aasma deu a ideia básica, mas eu queria torná-la um pouco mais concreta. Dê uma olhada nos cinco círculos abaixo e como eles foram decompostos.

Exemplo

  • Os pontos azuis são centros de círculo.
  • Os pontos vermelhos são interseções do limite do círculo.
  • Os pontos vermelhos com interior branco são interseções de limite de círculo que não estão contidas em nenhum outro círculo .

Identificar esses 3 tipos de pontos é fácil. Agora construa uma estrutura de dados de gráfico onde os nós são os pontos azuis e os pontos vermelhos com interior branco. Para cada círculo, coloque uma aresta entre o meio do círculo (ponto azul) e cada uma de suas interseções (pontos vermelhos com interior branco) em seu limite.

Isso decompõe a união do círculo em um conjunto de polígonos (sombreado em azul) e pedaços de pizza circulares (sombreado em verde) que são separados por pares e cobrem a união original (ou seja, uma partição). Como cada peça aqui é algo fácil de calcular a área de, você pode calcular a área da união somando as áreas das peças.

Timothy Shields
fonte
Acho que posso calcular um conjunto de pontos vermelhos / brancos com bastante facilidade, mas minha teoria dos grafos não é muito boa: algoritmicamente, como você passa de uma lista de nós + arestas para uma área computada?
user999305
1
O algoritmo pode ser simplificado usando um conjunto de triângulos não sobrepostos em vez de polígonos. Os arcos (áreas verdes) são áreas contidas em apenas um círculo. Aumente o tamanho de um polígono à medida que adiciona mais círculos. (no final você pode esquecer que está falando sobre polígonos). Isso torna as propriedades booleanas e as áreas também mais fáceis de calcular. Conforme um ponto vermelho oco se torna um ponto vermelho sólido, você simplesmente adiciona mais triângulos ao seu conjunto e ajusta o arco que é "comido" por mais e mais círculos que se cruzam.
Steve
16

Para uma solução diferente da anterior, você poderia produzir uma estimativa com uma precisão arbitrária usando uma quadtree.

Isso também funciona para qualquer união de forma se você puder dizer se um quadrado está dentro ou fora ou cruza a forma.

Cada célula tem um dos estados: vazio, cheio, parcial

O algoritmo consiste em "desenhar" os círculos da quadtree a partir de uma resolução baixa (4 células por exemplo marcadas como vazias). Cada célula é:

  • dentro de pelo menos um círculo, marque a célula como cheia,
  • fora de todos os círculos, marque a célula como vazia,
  • caso contrário, marque a célula como parcial.

Quando terminar, você pode calcular uma estimativa da área: as células cheias fornecem o limite inferior, as células vazias fornecem o limite superior, as células parciais fornecem o erro de área máximo.

Se o erro for muito grande para você, refine as células parciais até obter a precisão correta.

Acho que isso será mais fácil de implementar do que o método geométrico que pode exigir o tratamento de muitos casos especiais.

fa.
fonte
3
Meu palpite é que isso irá convergir mais rapidamente do que o algoritmo de ponto interno / externo de monte carlo também.
Frank Krueger
Isso parece muito mais fácil de implementar. Definitivamente, o melhor método de força bruta sugerido. Obrigado!
Anton Hansson
a força bruta aqui é chamada de teorema de compressão
fa.
Esse é o tipo de algoritmo que você usa na aritmética de intervalo. en.wikipedia.org/wiki/Interval_arithmetic
rjmunro
13

Eu amo a abordagem do caso de 2 círculos que se cruzam - aqui está como eu usaria uma ligeira variação da mesma abordagem para o exemplo mais complexo.

Isso pode fornecer uma visão melhor sobre a generalização do algoritmo para um número maior de círculos semi-sobrepostos.

A diferença aqui é que eu começo ligando os centros (então há um vértice entre o centro dos círculos, em vez de entre os lugares onde os círculos se cruzam). Acho que isso permite generalizar melhor.

(na prática, talvez o método monte-carlo valha a pena)

texto alternativo
(fonte: secretGeek.net )

Leon Bambrick
fonte
1
Acho que fazer o tipo de divisão de polígono sugerido pela sua imagem provavelmente seria uma abordagem muito boa. Há muitos detalhes a serem trabalhados para codificá-lo. Como ele lidaria com uma cadeia de vinte círculos, cada um dos quais se sobrepõe apenas ao último e ao próximo na cadeia? Fácil de descobrir manualmente, mas qual é o seu algoritmo?
PeterAllenWebb
4

Se você quiser uma resposta discreta (em oposição a contínua), pode fazer algo semelhante a um algoritmo de pintura de pixel.

Desenhe os círculos em uma grade e, em seguida, pinte cada célula da grade se estiver contida principalmente em um círculo (ou seja, pelo menos 50% de sua área está dentro de um dos círculos). Faça isso para a grade inteira (onde a grade abrange toda a área coberta pelos círculos) e, em seguida, conte o número de células coloridas na grade.

David R Tribble
fonte
3

Hmm, problema muito interessante. Minha abordagem provavelmente seria algo como o seguinte:

  • Encontre uma maneira de descobrir quais são as áreas de interseção entre um número arbitrário de círculos, ou seja, se eu tiver 3 círculos, preciso ser capaz de descobrir qual é a interseção entre esses círculos. O método "Monte-Carlo" seria uma boa maneira de aproximar isso ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
  • Elimine quaisquer círculos que estejam contidos inteiramente em outro círculo maior (observe o raio e o módulo da distância entre o centro dos dois círculos) que não acho que seja obrigatório.
  • Escolha 2 círculos (chame-os de A e B) e calcule a área total usando esta fórmula:

(isso é verdadeiro para qualquer forma, seja círculo ou outro)

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

Onde A ∪ Bsignifica A união B e A ∩ Bsignifica A intersecção B (você pode resolver isso desde a primeira etapa.

  • Agora continue adicionando círculos e continue trabalhando a área adicionada como uma soma / subtração de áreas de círculos e áreas de interseção entre círculos. Por exemplo, para 3 círculos (chame o círculo extra C), calculamos a área usando esta fórmula:

(Este é o mesmo que acima, onde Afoi substituído por A∪B)

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

Onde area(A∪B)acabamos de trabalhar e area((A∪B)∩C)pode ser encontrado:

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)

Onde novamente você pode encontrar a área (A∩B∩C) de cima.

A parte complicada é a última etapa - quanto mais círculos são adicionados, mais complexo ele se torna. Acredito que haja uma expansão para calcular a área de uma interseção com uma união finita ou, alternativamente, você pode resolvê-la recursivamente.

Ainda com relação ao uso de Monte-Carlo para aproximar a área de itersecção, acredito que seja possível reduzir a intersecção de um número arbitrário de círculos para a intersecção de 4 desses círculos, que pode ser calculado exatamente (não tenho ideia de como fazer isso Contudo).

Provavelmente há uma maneira melhor de fazer isso aliás - a complexidade aumenta significativamente (possivelmente exponencialmente, mas não tenho certeza) para cada círculo extra adicionado.

Justin
fonte
O que há com a formatação? Também sinto muito sobre o uso de n e u para interseção e união, provavelmente há uma maneira melhor ...
Justin
1
adicionado alguns sinais de união (∪) e interseção (∩) Unicode. espero que funcionem.
Spoike
3

Tenho trabalhado em um problema de simulação de campos estelares sobrepostos, tentando estimar as verdadeiras contagens de estrelas a partir das áreas reais do disco em campos densos, onde as estrelas maiores brilhantes podem mascarar as mais fracas. Eu também esperava ser capaz de fazer isso por meio de uma análise formal rigorosa, mas não consegui encontrar um algoritmo para a tarefa. Resolvi isso gerando os campos estelares em um fundo azul como discos verdes, cujo diâmetro foi determinado por um algoritmo de probabilidade. Uma rotina simples pode emparelhá-los para ver se há uma sobreposição (tornando o par de estrelas amarelo); então, uma contagem de pixels das cores gera a área observada para comparar com a área teórica. Isso então gera uma curva de probabilidade para as contagens verdadeiras. Força bruta talvez, mas parece funcionar bem. (fonte: 2from.com )

user213660
fonte
2

Este é um algoritmo que deve ser fácil de implementar na prática e pode ser ajustado para produzir erros arbitrariamente pequenos:

  1. Aproxime cada círculo por um polígono regular centrado no mesmo ponto
  2. Calcule o polígono que é a união dos círculos aproximados
  3. Calcule a área do polígono mesclado

As etapas 2 e 3 podem ser realizadas usando algoritmos padrão e fáceis de encontrar da geometria computacional.

Obviamente, quanto mais lados você usar para cada polígono aproximado, mais perto da exata sua resposta estará. Você pode aproximar usando polígonos inscritos e circunscritos para obter os limites da resposta exata.

PeterAllenWebb
fonte
2

Existem soluções eficientes para esse problema usando o que são conhecidos como diagramas de energia. Esta é uma matemática realmente pesada e não algo que eu gostaria de resolver de imediato. Para uma solução "fácil", procure algoritmos de varredura de linha. O princípio básico aqui é que você divida a figura em tiras, onde calcular a área em cada tira é relativamente fácil.

Assim, na figura que contém todos os círculos sem nada apagado, desenhe uma linha horizontal em cada posição que é o topo de um círculo, a parte inferior de um círculo ou a intersecção de 2 círculos. Observe que, dentro dessas faixas, todas as áreas que você precisa calcular têm a mesma aparência: um "trapézio" com dois lados substituídos por segmentos circulares. Portanto, se você conseguir descobrir como calcular essa forma, basta fazer isso para todas as formas individuais e adicioná-las. A complexidade dessa abordagem ingênua é O (N ^ 3), onde N é o número de círculos na figura. Com algum uso inteligente da estrutura de dados, você poderia melhorar este método de varredura de linha para O (N ^ 2 * log (N)), mas a menos que seja realmente necessário, provavelmente não vale a pena se dar ao trabalho.

Steve Thomas
fonte
1

Achei este link que pode ser útil. Porém, não parece haver uma resposta definitiva. Respostas do Google . Outra referência para três círculos é o teorema de Haruki . Também há um jornal lá.

Greg Reynolds
fonte
1

Dependendo do problema que você está tentando resolver, pode ser suficiente obter um limite superior e inferior. Um limite superior é fácil, apenas a soma de todos os círculos. Para um limite inferior, você pode escolher um único raio de forma que nenhum dos círculos se sobreponha. Para melhor isso, encontre o maior raio (até o raio real) para cada círculo de forma que ele não se sobreponha. Também deve ser bastante trivial remover quaisquer círculos completamente sobrepostos (Todos esses círculos satisfazem | P_a - P_b | <= r_a) onde P_a é o centro do círculo A, P_b é o centro do círculo B e r_a é o raio de A ) e isso melhora o limite superior e inferior. Você também pode obter um Limite superior melhor se usar sua fórmula de par em pares arbitrários, em vez de apenas a soma de todos os círculos. Pode haver uma boa maneira de escolher o "melhor"

Dados os limites superior e inferior, você pode ajustar melhor uma abordagem de Monte-carlo, mas nada específico vem à mente. Outra opção (novamente dependendo de seu aplicativo) é rasterizar os círculos e contar pixels. É basicamente a abordagem de Monte-carlo com uma distribuição fixa.

fryguybob
fonte
0

Isso pode ser resolvido usando o Teorema de Green , com uma complexidade de n ^ 2log (n). Se você não está familiarizado com o Teorema de Green e deseja saber mais, aqui está o vídeo e as notas da Khan Academy. Mas, para o bem de nosso problema, acho que minha descrição será suficiente.

Desculpe pelos links para as fotos, pois não consigo postar imagens. (Pontos de reputação insuficientes)

Equação Geral do Teorema de Green

Se eu colocar L e M de forma que

Doença

então o RHS é simplesmente a área da Região R e pode ser obtido resolvendo a integral fechada ou LHS e isso é exatamente o que vamos fazer.

Todos os sindicatos podem ser divididos em conjuntos desconexos de círculos que se cruzam

Portanto, a integração ao longo do caminho no sentido anti-horário nos dá a Área da região e a integração ao longo do sentido horário nos dá o negativo da Área . assim

AreaOfUnion = (Integração ao longo de arcos vermelhos no sentido anti-horário + Integração ao longo de arcos azuis no sentido horário)

Mas o truque legal é se, para cada círculo, se integrarmos os arcos que não estão dentro de nenhum outro círculo, obtermos nossa área necessária, ou seja, obtermos integração no sentido anti-horário ao longo de todos os arcos vermelhos e integração ao longo de todos os arcos azuis ao longo do sentido horário. TAREFA CONCLUÍDA!!!

Até os casos em que um círculo não se cruza com nenhum outro são resolvidos.

Aqui está o link do GitHub para meu código C ++

Deepesh Thakur
fonte
-1

A abordagem de pintura de pixels (conforme sugerido por @Loadmaster) é superior à solução matemática de várias maneiras:

  1. A implementação é muito mais simples. O problema acima pode ser resolvido em menos de 100 linhas de código, como esta solução JSFiddle demonstra (principalmente porque é conceitualmente muito mais simples e não tem casos extremos ou exceções para lidar).
  2. Ele se adapta facilmente a problemas mais gerais. Funciona com qualquer forma, independentemente da morfologia, desde que seja renderizável com bibliotecas de desenhos 2D (ou seja, “todos eles!”) - círculos, elipses, splines, polígonos, etc. Caramba, até mesmo imagens de bitmap.
  3. A complexidade da solução de pintura de pixels é ~ O [n], em comparação com ~ O [n * n] para a solução matemática. Isso significa que ele terá um melhor desempenho à medida que o número de formas aumenta.
  4. E por falar em desempenho, você frequentemente obterá aceleração de hardware gratuitamente, já que a maioria das bibliotecas 2D modernas (como a tela do HTML5, eu acredito) irá descarregar o trabalho de renderização para aceleradores gráficos.

A única desvantagem da pintura em pixels é a precisão finita da solução. Mas isso é ajustável simplesmente renderizando para telas maiores ou menores conforme a situação exigir. Observe também que o anti-aliasing no código de renderização 2D (geralmente ativado por padrão) renderá uma precisão melhor do que o nível de pixel. Então, por exemplo, renderizar uma figura 100x100 em uma tela com as mesmas dimensões deve, eu acho, produzir uma precisão da ordem de 1 / (100 x 100 x 255) = 0,000039% ... o que provavelmente é "bom o suficiente" para todos, exceto os problemas mais 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
fonte
Esta solução falha em fazer cálculos matemáticos com as áreas dos círculos. Ele perde o foco da questão dos OPs. Muitas vezes, a geometria de renderização é apenas metade da batalha ao lidar com formas geométricas
Steve