Zone combinée de cercles qui se chevauchent

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

• mettez une boîte englobante des cercles;
• générer des points aléatoires dans la zone de délimitation;
• Déterminez si le point aléatoire est à l'intérieur d'un des cercles;
• calculez la zone par une simple addition et division (proportion_of_points_inside * area_of_bounding_box).

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

• vous pouvez obtenir une réponse aussi précise que vous voulez, juste générer plus de points;
• cela fonctionnera pour toutes les formes pour lesquelles vous pouvez calculer la distinction intérieur/extérieur;
• Il parallélisera magnifiquement afin que vous puissiez utiliser tous vos cœurs.

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

Cela fonctionne également pour toute 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 du quadtree en commençant par une basse résolution ( 4 cellules par exemple marquées comme vides). Chaque cellule est soit :

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

Quand c'est fait, vous pouvez calculer une estimation de la zone : les cellules complètes donnent la limite inférieure, les cellules vides donnent la limite supérieure, les cellules partielles donnent l'erreur de zone maximale.

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

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

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

• les points bleus sont des centres de cercle.
• les points rouges sont des intersections de limites de cercle.
• les points rouges avec 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. Maintenant, construisez 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 un bord 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 de cercle en un ensemble de polygones (ombrés en bleu) et de morceaux de tarte circulaires (ombrés en vert) qui sont disjoints par paires et couvrent l'union d'origine (c'est-à-dire une partition). Puisque chaque pièce ici est quelque chose c'est facile de calculer la zone de, vous pouvez calculer la zone de l'union en additionnant les zones des pièces.

J'aime 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-chevauchants.

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

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

Le texte d'Alt http://secretGeek.net/image/triangles_1667310.png

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

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 la grille entière (où la grille couvre toute la zone couverte par les cercles), puis comptez le nombre de cellules colorées dans la grille.

Hmm, problème très intéressant. Mon approche serait probablement quelque chose dans le sens de ce qui suit:

• trouvez un moyen de déterminer quelles sont les zones d'intersection entre un nombre arbitraire de cercles, c'est-à-dire 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/géométrie/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 qu'il soit obligatoire.
• Choisissez 2 cercles (appelez-les A et B) et calculez la surface totale en utilisant cette formule:

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

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

Où A ∪ B désigne une union B et A ∩ B signifie un intersect B (vous pouvez le résoudre dès la première étape.

• maintenant, continuez à ajouter des cercles et continuez à travailler sur la zone ajoutée comme une 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 travaillons sur la zone en utilisant cette formule:

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

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

Où 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 une fois vous pouvez trouver la zone (A B B C C) d'en haut.

Le bit délicat est la dernière étape - plus les cercles sont ajoutés, plus il devient complexe. Je crois qu'il y a une expansion pour travailler sur la zone d'une intersection avec une union finie, ou bien vous pouvez être en mesure de le travailler récursivement.

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

Il y a probablement une meilleure façon de le faire btw - la complexité augmente de manière significative (peut-être exponentielle, mais je ne suis pas sûr) pour chaque cercle supplémentaire ajouté.

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

Il existe des solutions efficaces à ce problème en utilisant ce que l'on appelle les diagrammes de puissance. C'est vraiment des mathématiques lourdes et pas quelque chose que je voudrais aborder désinvolte. Pour une solution "facile", 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 zone dans chaque bande est relativement facile.

Ainsi, sur la figure contenant tous les cercles sans rien frotté, tracez une ligne horizontale à chaque position qui est le haut d'un cercle, le fond d'un cercle ou de 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 travailler sur la façon de calculer une telle forme, vous le faites juste pour toutes les formes individuelles et les ajouter ensemble. La complexité de cette approche naïve est O(N^3), où N est le nombre de cercles dans la figure. Avec une structure de données intelligente, utilisez, 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.

J'ai trouvé ce lien qui peut être utile. Il ne semble pas y avoir de réponse définitive cependant. Google réponses. Une autre référence pour trois cercles est théorème de Haruki . Il y a aussi un papier là-bas.

Selon le problème que vous essayez de résoudre, il pourrait suffire d'obtenir une limite supérieure et inférieure. Une limite supérieure est facile, juste la somme de tous les cercles. Pour une limite inférieure, vous pouvez choisir un seul rayon tel qu'aucun des cercles ne se chevauchent. 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 chevauchés (tous ces cercles satisfont |P_a - P_b|

Étant donné une limite supérieure et inférieure, vous pourriez être en mesure de mieux accorder une approche de Monte-carlo, mais rien de spécifique vient à l'esprit. Une autre option (encore une fois en fonction de votre application) consiste à rastériser les cercles et à compter les pixels. C'est essentiellement L'approche Monte-carlo avec une distribution fixe.

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

1. approximer chaque cercle par un polygone régulier centré au même point
2. calculez le polygone qui est l'union des cercles approximé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 issus de la géométrie computationnelle.

Évidemment, le plus les côtés que vous utilisez pour chaque polygone approximatif, le plus proche de votre réponse exacte serait. Vous pouvez approximer en utilisant des polygones inscrits et circonscrits pour obtenir des limites sur la réponse exacte.

L'approche de la peinture au pixel (suggérée par @Loadmaster) est supérieure à la solution mathématique de diverses manières:

1. L'implémentation est beaucoup plus simple. Le problème ci-dessus peut être résolu en moins de 100 lignes de code, comme cette solution jsfiddle le démontre (principalement parce qu'elle est conceptuellement beaucoup plus simple et n'a pas de cas ou d'exceptions à traiter).
2. il s'adapte facilement aux problèmes plus généraux. Il fonctionne avec n'importe quelle forme, indépendamment de morphologie, tant qu'elle est rendue avec des bibliothèques de dessin 2D (c'est-à-dire "toutes!")- cercles, ellipses, splines, polygones, vous l'appelez. Heck, même des images bitmap.
3. la complexité de la solution de pixel-peinture est ~O [n], par rapport à ~O [n * N] pour la solution mathématique. Cela signifie qu'il fonctionnera mieux que le nombre de formes augmente.
4. et en parlant de performance, vous obtiendrez souvent une accélération matérielle gratuite, comme la plupart des bibliothèques 2D modernes (comme le canevas de HTML5, Je crois) va décharger le travail de rendu aux accélérateurs graphiques.

Le seul inconvénient de la peinture au pixel est la précision finie de la solution. Mais cela est réglable en rendant simplement à des toiles plus grandes ou plus petites que la situation l'exige. Notez également que l'anti-aliasing dans le code de rendu 2D (souvent activé par défaut) donnera une précision supérieure à celle du pixel. Ainsi, par exemple, le rendu d'une figure 100x100 dans une toile de même taille devrait, je pense, précision du rendement 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);