Zone combinée de cercles qui se chevauchent

107

Je suis récemment tombé sur un problème où j'avais quatre cercles (milieu et rayon) et devais calculer l'aire de l'union de ces cercles.

Exemple d'image:

Pour deux cercles c'est assez facile,

Je peux simplement calculer la fraction de la zone de chaque cercle qui n'est pas dans les triangles, puis calculer la surface des triangles.

Mais y a-t-il un algorithme intelligent que je peux utiliser quand il y a plus de deux cercles?

Anton Hansson
la source
15
C'est un problème vraiment intéressant, je me souviens avoir vu cela en classe de géométrie au lycée, mais je n'ai jamais trouvé de solution. Si vous ne trouvez pas de réponse ici, essayez de la publier sur mathoverflow.net et laissez les mathématiciens s'y intéresser : P
Charles Ma
25
parfois les vrais programmeurs ont besoin de vrais maths
fa.
1
Que diriez-vous de trouver la réponse à cette question - "Nous avons des commerciaux qui vivent sur ces 4 sites, chacun desservant une zone avec ces 4 rayons. Quelle partie du pays couvrons-nous?" Si vous aviez une base de données changeante de commerciaux, cela devient une question de programmation!
Chris Roberts
5
En fait, c'est le genre de problème auquel les vrais programmeurs aiment penser.
MAK
2
@zvolkov: les circuits imprimés sont décrits avec un langage qui plonge les carrés et les cercles vers le bas et les fait éventuellement glisser. "Calculez la surface de cuivre". (Cela peut être nécessaire pour calculer les temps de gravure, savoir s'il faut ajouter des illustrations de nettoyage, diverses choses.)
DigitalRoss

Réponses:

97

Trouvez toutes les intersections de cercles sur le périmètre extérieur (par exemple B, D, F, H sur le diagramme suivant). Connectez-les avec les centres des cercles correspondants pour former un polygone. L'aire de l'union des cercles est l'aire du polygone + l'aire des tranches de cercle définies par des points d'intersection consécutifs et le centre du cercle entre eux. Vous devrez également tenir compte de tous les trous.

chevauchement de cercle

Fourmis Aasma
la source
17
Que se passe-t-il quand il y a un trou au centre?
John Gietzen
3
Vous devrez soustraire le polygone connecté au centre pour le trou du total et ajouter les tranches de cercle pour ce polygone au total.
Ants Aasma
3
sympa mais je suppose que cela nécessitera beaucoup de détails d'implémentation pour gérer tous les cas particuliers (cercle à l'intérieur de l'autre, pas d'intersection, trous, un point de contact ...)
fa.
1
Les cas particuliers sont assez simples. Les cercles à l'intérieur des autres sont supprimés en l'absence d'intersections de périmètre. Un contact ponctuel correspond en fait à deux intersections à distance nulle. Les formes déconnectées peuvent être trouvées via l'algorithme des composants connectés sur le graphique où deux cercles sont connectés si la distance des centres est inférieure à la somme des rayons. Les trous sont tous des polygones sauf celui avec la plus grande surface. Les intersections de périmètre sont toutes les intersections qui ne sont strictement à l'intérieur d'aucun cercle.
Ants Aasma
4
oui, mais les bordures des trous sont aussi de (petits) arcs. Je pense toujours que cela nécessite beaucoup de code pour fonctionner correctement.
fa.
32

Je suis sûr qu'il existe un algorithme intelligent, mais en voici un idiot pour éviter d'avoir à le chercher;

  • placez une boîte englobante autour des cercles;
  • générer des points aléatoires dans la boîte englobante;
  • déterminer si le point aléatoire est à l'intérieur de l'un des cercles;
  • calculer l'aire par une simple addition et division (proportion_of_points_inside * area_of_bounding_box).

Bien sûr, c'est stupide, mais:

  • vous pouvez obtenir une réponse aussi précise que vous le souhaitez, il suffit de générer plus de points;
  • cela fonctionnera pour toutes les formes pour lesquelles vous pouvez calculer la distinction intérieur / extérieur;
  • il se parallélisera magnifiquement pour que vous puissiez utiliser tous vos cœurs.
Marque haute performance
la source
2
Cela fonctionnera, mais les méthodes de Monte-Carlo comme celle-ci, basées simplement sur un échantillonnage uniforme, n'ont généralement pas les meilleurs taux de convergence.
ShreevatsaR
2
Désolé, mais même si j'apprécie vos efforts et pense que votre solution est «pratiquement utilisable», je considère que votre approche est très erronée. C'est un problème qui peut et doit être résolu au moyen des mathématiques et non de la force brute. Gaspiller de l'énergie et des noyaux sur des problèmes comme celui-ci est un gaspillage et une richesse.
mafu
5
Vous avez raison, j'ai honte de moi, mais j'ai un cluster avec 12 000 cœurs, je peux me permettre d'être somptueux. Et je ne peux pas comprendre comment adapter l'élégante solution mathématique à autant de processeurs.
High Performance Mark
8
Il n'y a rien de mal en soi avec une approche de Monte-Carlo (ou toute approche aléatoire), à ​​condition qu'elle donne le degré de précision requis et le fasse dans un laps de temps raisonnable.
MAK
@mafutrct, vous avez certainement raison. Cependant, il est facile de faire de petites erreurs en mathématiques. Cette solution fournit un moyen simple de tester l'exactitude.
Richard
18

La réponse d'Ants Aasma a donné l'idée de base, mais je voulais la rendre un peu plus concrète. Jetez un œil aux cinq cercles ci-dessous et à la façon dont ils ont été décomposés.

Exemple

  • Les points bleus sont les centres du cercle.
  • Les points rouges sont les intersections des limites du cercle.
  • Les points rouges avec un intérieur blanc sont des intersections de limites de cercle qui ne sont contenues dans aucun autre cercle .

Identifier ces 3 types de points est facile. Construisez maintenant une structure de données graphique où les nœuds sont les points bleus et les points rouges avec un intérieur blanc. Pour chaque cercle, placez une arête entre le milieu du cercle (point bleu) et chacune de ses intersections (points rouges avec intérieur blanc) sur sa limite.

Cela décompose l'union du cercle en un ensemble de polygones (ombrés en bleu) et de morceaux de secteurs circulaires (ombrés en vert) qui sont disjoints par paires et recouvrent l'union d'origine (c'est-à-dire une partition). Étant donné que chaque pièce ici est quelque chose dont il est facile de calculer l'aire, vous pouvez calculer l'aire de l'union en additionnant les aires des pièces.

Timothy Shields
la source
Je pense que je peux calculer un ensemble de points rouges / blancs assez facilement, mais ma théorie des graphes n'est pas trop grande: algorithmiquement, comment passer d'une liste de nœuds + arêtes à une zone calculée?
user999305
1
L'algorithme peut être simplifié en utilisant un ensemble de triangles non superposés au lieu de polygones. Les arcs (zones vertes) sont des zones contenues dans un seul cercle. Augmentez la taille d'un polygone à mesure que vous ajoutez plus de cercles. (à la fin, vous pouvez oublier que vous parlez même de polygones). Cela rend les propriétés booléennes et les zones sont également plus faciles à calculer. Lorsqu'un point rouge creux devient un point rouge uni, vous ajoutez simplement plus de triangles à votre ensemble, et vous ajustez l'arc, il est «rongé» par de plus en plus de cercles qui se croisent.
Steve
16

Pour une solution différente de la précédente, vous pouvez produire une estimation avec une précision arbitraire en utilisant un arbre quaternaire.

Cela fonctionne également pour n'importe quelle union de forme si vous pouvez dire si un carré est à l'intérieur ou à l'extérieur ou croise la forme.

Chaque cellule a l'un des états: vide, plein, partiel

L'algorithme consiste à "dessiner" les cercles dans l'arbre quaternaire en commençant par une faible résolution (4 cellules par exemple marquées comme vides). Chaque cellule est soit:

  • à l'intérieur d'au moins un cercle, puis marquez la cellule comme pleine,
  • en dehors de tous les cercles, marquez la cellule comme vide,
  • sinon, marquez la cellule comme partielle.

Lorsque c'est fait, vous pouvez calculer une estimation de la surface: les cellules pleines donnent la borne inférieure, les cellules vides donnent la borne supérieure, les cellules partielles donnent l'erreur de surface maximale.

Si l'erreur est trop importante pour vous, vous affinez les cellules partielles jusqu'à ce que vous obteniez la bonne précision.

Je pense que ce sera plus facile à mettre en œuvre que la méthode géométrique qui peut nécessiter de traiter de nombreux cas particuliers.

FA.
la source
3
Je suppose que cela convergera plus rapidement que l'algorithme de point intérieur / extérieur de Monte Carlo.
Frank Krueger
Cela semble beaucoup plus facile à mettre en œuvre. Certainement la meilleure méthode de force brute suggérée. Merci!
Anton Hansson
la force brute est ici appelée théorème de compression
fa.
C'est le type d'algorithme que vous utilisez dans l'arithmétique des intervalles. en.wikipedia.org/wiki/Interval_arithmetic
rjmunro
13

J'adore l'approche du cas de 2 cercles qui se croisent - voici comment j'utiliserais une légère variation de la même approche pour l'exemple plus complexe.

Cela pourrait donner un meilleur aperçu de la généralisation de l'algorithme pour un plus grand nombre de cercles semi-superposés.

La différence ici est que je commence par relier les centres (il y a donc un sommet entre le centre des cercles, plutôt qu'entre les endroits où les cercles se croisent) Je pense que cela permet de mieux se généraliser.

(en pratique, peut-être que la méthode monte-carlo vaut la peine)

texte alternatif
(source: secretGeek.net )

Léon Bambrick
la source
1
Je pense que faire le genre de division polygonale suggérée par votre image serait probablement une très bonne approche. Il y a beaucoup de détails à élaborer pour le coder. Comment gérerait-il une chaîne de vingt cercles, dont chacun ne chevauche que le dernier et le suivant de la chaîne? Facile à comprendre à la main, mais quel est votre algorithme?
PeterAllenWebb
4

Si vous voulez une réponse discrète (par opposition à une réponse continue), vous pouvez faire quelque chose de similaire à un algorithme de pixel painting.

Dessinez les cercles sur une grille, puis colorez chaque cellule de la grille si elle est principalement contenue dans un cercle (c'est-à-dire qu'au moins 50% de sa surface est à l'intérieur de l'un des cercles). Faites ceci pour toute la grille (où la grille couvre toute la zone couverte par les cercles), puis comptez le nombre de cellules colorées dans la grille.

David R Tribble
la source
3

Hmm, problème très intéressant. Mon approche serait probablement quelque chose du genre:

  • Trouvez un moyen de déterminer ce que sont les zones d'intersection entre un nombre arbitraire de cercles, c'est-à-dire que si j'ai 3 cercles, je dois être capable de déterminer quelle est l'intersection entre ces cercles. La méthode "Monte-Carlo" serait un bon moyen de se rapprocher de cela ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
  • Éliminez tous les cercles qui sont entièrement contenus dans un autre cercle plus grand (regardez le rayon et le module de la distance entre le centre des deux cercles) Je ne pense pas que ce soit obligatoire.
  • Choisissez 2 cercles (appelez-les A et B) et calculez la surface totale en utilisant cette formule:

(cela est vrai pour n'importe quelle forme, que ce soit un cercle ou autre)

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

A ∪ Bsignifie A union B et A ∩ Bsignifie A intersecter B (vous pouvez le calculer à partir de la première étape.

  • Continuez maintenant à ajouter des cercles et continuez à travailler sur la zone ajoutée en tant que somme / soustraction des zones de cercles et des zones d'intersections entre les cercles. Par exemple, pour 3 cercles (appelez le cercle supplémentaire C), nous calculons l'aire en utilisant cette formule:

(C'est le même que ci-dessus où Aa été remplacé par A∪B)

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

area(A∪B)nous venons de travailler, et area((A∪B)∩C)peut être trouvé:

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)

Où encore vous pouvez trouver la zone (A∩B∩C) d'en haut.

Le plus délicat est la dernière étape - plus les cercles sont ajoutés, plus cela devient complexe. Je crois qu'il y a une extension pour travailler sur l'aire d'une intersection avec une union finie, ou alternativement, vous pourrez peut-être la résoudre de manière récursive.

Aussi en ce qui concerne l'utilisation de Monte-Carlo pour approximer la zone d'itersection, je pense qu'il est possible de réduire l'intersection d'un nombre arbitraire de cercles à l'intersection de 4 de ces cercles, qui peuvent être calculés exactement (aucune idée de comment faire cela toutefois).

Il existe probablement une meilleure façon de faire cela - la complexité augmente considérablement (peut-être de façon exponentielle, mais je ne suis pas sûr) pour chaque cercle supplémentaire ajouté.

Justin
la source
Quoi de neuf avec le formatage? Aussi désolé pour l'utilisation de n et u pour l'intersection et l'union, il existe probablement une meilleure façon ...
Justin
1
ajouté quelques signes d'union unicode (∪) et d'intersection (∩) j'espère qu'ils fonctionnent.
Spoike
3

J'ai travaillé sur un problème de simulation de champs d'étoiles qui se chevauchent, en essayant d'estimer le nombre réel d'étoiles à partir des zones de disque réelles dans des champs denses, où les plus grandes étoiles brillantes peuvent masquer les plus faibles. J'avais moi aussi espéré pouvoir le faire par une analyse formelle rigoureuse, mais je n'ai pas pu trouver un algorithme pour la tâche. Je l'ai résolu en générant les champs d'étoiles sur fond bleu sous forme de disques verts, dont le diamètre était déterminé par un algorithme de probabilité. Une simple routine peut les coupler pour voir s'il y a un chevauchement (en tournant la paire d'étoiles en jaune); puis un comptage de pixels des couleurs génère la zone observée à comparer à la zone théorique. Cela génère alors une courbe de probabilité pour les vrais comptes. Force brute peut-être, mais cela semble fonctionner correctement. (source: 2from.com )

user213660
la source
2

Voici un algorithme qui devrait être facile à mettre en œuvre dans la pratique et qui pourrait être ajusté pour produire une erreur arbitrairement petite:

  1. Approximer chaque cercle par un polygone régulier centré au même point
  2. Calculez le polygone qui est l'union des cercles approchés
  3. Calculer l'aire du polygone fusionné

Les étapes 2 et 3 peuvent être effectuées à l'aide d'algorithmes standard et faciles à trouver à partir de la géométrie de calcul.

De toute évidence, plus vous utilisez de côtés pour chaque polygone approximatif, plus votre réponse sera proche de l'exactitude. Vous pouvez effectuer une approximation en utilisant des polygones inscrits et circonscrits pour obtenir des limites sur la réponse exacte.

PeterAllenWebb
la source
2

Il existe des solutions efficaces à ce problème en utilisant ce que l'on appelle des diagrammes de puissance. Ce sont des calculs vraiment lourds et pas quelque chose que je voudrais aborder de manière désinvolte. Pour une solution «simple», recherchez des algorithmes de balayage de ligne. Le principe de base ici est que vous divisez la figure en bandes, où le calcul de la surface dans chaque bande est relativement facile.

Ainsi, sur la figure contenant tous les cercles sans aucun frottement, tracez une ligne horizontale à chaque position qui est soit le haut d'un cercle, le bas d'un cercle ou l'intersection de 2 cercles. Notez qu'à l'intérieur de ces bandes, toutes les zones que vous devez calculer se ressemblent: un «trapèze» avec deux côtés remplacés par des segments circulaires. Donc, si vous pouvez déterminer comment calculer une telle forme, faites-le simplement pour toutes les formes individuelles et ajoutez-les ensemble. La complexité de cette approche naïve est O (N ^ 3), où N est le nombre de cercles de la figure. Avec une utilisation intelligente de la structure de données, vous pouvez améliorer cette méthode de balayage de ligne à O (N ^ 2 * log (N)), mais à moins que vous n'en ayez vraiment besoin, cela ne vaut probablement pas la peine.

Steve Thomas
la source
1

J'ai trouvé ce lien qui peut être utile. Cependant, il ne semble pas y avoir de réponse définitive. Google répond . Une autre référence pour trois cercles est le théorème de Haruki . Il y a aussi un article.

Greg Reynolds
la source
1

En fonction du problème que vous essayez de résoudre, il peut suffire d'obtenir une limite supérieure et inférieure. Une borne supérieure est facile, juste la somme de tous les cercles. Pour une limite inférieure, vous pouvez choisir un rayon unique de sorte qu'aucun des cercles ne se chevauche. Pour mieux trouver le plus grand rayon (jusqu'au rayon réel) pour chaque cercle afin qu'il ne se chevauche pas. Il devrait également être assez trivial de supprimer tous les cercles complètement superposés (tous ces cercles satisfont | P_a - P_b | <= r_a) où P_a est le centre du cercle A, P_b est le centre du cercle B et r_a est le rayon de A ) et cela améliore à la fois la limite supérieure et inférieure. Vous pouvez également obtenir une meilleure borne supérieure si vous utilisez votre formule de paire sur des paires arbitraires au lieu de simplement la somme de tous les cercles. Il existe peut-être un bon moyen de choisir le "meilleur"

Étant donné une limite supérieure et inférieure, vous pourrez peut-être mieux régler une approche Monte-carlo, mais rien de spécifique ne vient à l'esprit. Une autre option (toujours en fonction de votre application) consiste à pixelliser les cercles et à compter les pixels. Il s'agit essentiellement de l'approche Monte-carlo avec une distribution fixe.

fryguybob
la source
0

Cela peut être résolu en utilisant le théorème de Green , avec une complexité de n ^ 2log (n). Si vous n'êtes pas familier avec le théorème de Green et que vous voulez en savoir plus, voici la vidéo et les notes de Khan Academy. Mais pour le bien de notre problème, je pense que ma description sera suffisante.

Désolé pour les liens vers les photos, car je ne peux pas publier d'images (pas assez de points de réputation)

Équation générale du théorème de Green

Si je mets L et M tels que

État

alors le RHS est simplement l'aire de la région R et peut être obtenu en résolvant l'intégrale fermée ou LHS et c'est exactement ce que nous allons faire.

Toutes les unions peuvent être divisées en des ensembles disjoints de cercles qui se croisent

Donc, intégrer le long du chemin dans le sens inverse des aiguilles d'une montre nous donne la zone de la région et intégrer le long du sens des aiguilles d'une montre nous donne le négatif de la zone . Alors

AreaOfUnion = (Intégration le long des arcs rouges dans le sens anti-horaire + Intégration le long des arcs bleus dans le sens horaire)

Mais le truc sympa est si pour chaque cercle, si nous intégrons les arcs qui ne sont à l'intérieur d'aucun autre cercle, nous obtenons notre zone requise, c'est-à-dire que nous obtenons une intégration dans le sens inverse des aiguilles d'une montre le long de tous les arcs rouges et une intégration le long de tous les arcs bleus dans le sens horaire. TRAVAIL ACCOMPLI!!!

Même les cas où un cercle ne croise aucun autre sont pris en charge.

Voici le lien GitHub vers mon code C ++

Deepesh Thakur
la source
-1

L'approche de pixel-painting (comme suggéré par @Loadmaster) est supérieure à la solution mathématique de plusieurs manières:

  1. La mise en œuvre est beaucoup plus simple. Le problème ci-dessus peut être résolu en moins de 100 lignes de code, comme le montre cette solution JSFiddle (principalement parce qu'elle est conceptuellement beaucoup plus simple et n'a pas de cas ou d'exceptions à traiter).
  2. Il s'adapte facilement à des problèmes plus généraux. Il fonctionne avec n'importe quelle forme, quelle que soit la morphologie, tant qu'il peut être rendu avec des bibliothèques de dessins 2D (c'est-à-dire «tous!») - cercles, ellipses, splines, polygones, vous le nommez. Heck, même des images bitmap.
  3. La complexité de la solution de pixel-painting est ~ O [n], comparée à ~ O [n * n] pour la solution mathématique. Cela signifie qu'il fonctionnera mieux à mesure que le nombre de formes augmente.
  4. Et en parlant de performances, vous obtiendrez souvent une accélération matérielle gratuite, car la plupart des bibliothèques 2D modernes (comme le canevas de HTML5, je crois) délesteront le travail de rendu vers des accélérateurs graphiques.

Le seul inconvénient de la peinture au pixel est la précision finie de la solution. Mais cela peut être ajusté en effectuant simplement un rendu sur des toiles plus grandes ou plus petites selon la situation. Notez également que l' anti-aliasing dans le code de rendu 2D (souvent activé par défaut) donnera une précision supérieure au pixel. Ainsi, par exemple, rendre une figure 100x100 dans un canevas de mêmes dimensions devrait, je pense, donner une précision de l'ordre de 1 / (100 x 100 x 255) = .000039% ... ce qui est probablement "assez bon" pour tous sauf les problèmes les plus exigeants.

<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
la source
Cette solution ne tient pas compte des calculs mathématiques avec les aires des cercles. Il manque le point de la question des OP. Très souvent, la géométrie de rendu n'est que la moitié de la bataille lorsqu'il s'agit de formes géométriques
Steve