Superficie combinée des cercles qui se chevauchent

Question

Je suis récemment tombé sur un problème où j'ai eu quatre milieux (milieux et de rayon) et avait pour calculer la zone de l'union de ces cercles.

Exemple en image:

Pour les deux cercles, c'est assez facile,

Je peux juste calculer la fraction de chacun des cercles de la zone qui n'est pas dans les triangles et ensuite calculer l'aire des triangles.

Mais est-il un algorithme intelligent je peux l'utiliser quand il n'y a plus de deux cercles?

Answer 1

Trouver tous cercle intersections sur le périmètre extérieur (par exemple, B,D,F,H, sur le schéma suivant). Connectez-les ensemble avec les centres des correspondants des cercles pour former un polygone. La zone de l'union des cercles est l'aire du polygone + l'aire du cercle des tranches définies par consécutives points d'intersection du cercle de centre entre eux. Vous devez également tenir compte de tout les trous.

Answer 2

Je suis sûr qu'il y est un algorithme intelligent, mais voici un muet pour enregistrer avoir à chercher;

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

Sûr que c'est bête, mais:

• vous pouvez obtenir la meilleure réponse que vous voulez, il suffit de générer le plus de points;
• il va travailler pour toutes les formes pour lesquelles vous pouvez calculer l'intérieur/à l'extérieur de distinction;
• il paralléliser magnifiquement de sorte que vous pouvez utiliser tous les cœurs.

Answer 3

Pour une solution différente de la précédente, vous pourriez produire une estimation avec une précision arbitraire à l'aide d'un quadtree.

Cela fonctionne aussi pour toute forme d'union si vous pouvez dire si un carré est à l'intérieur ou à l'extérieur ou coupe la forme.

Chaque cellule dispose de l'un des états : le vide , le plein , partiel

L'algorithme consiste en "tirant" les cercles dans le quadtree de commencer avec une faible résolution ( 4 cellules par exemple marqué comme vide). Chaque cellule est soit :

• à l'intérieur d'au moins un cercle, puis marquer la cellule,
• en dehors de tous les cercles, marque de la cellule à vide,
• d'autre marque de la cellule en tant que partielle.

Quand c'est fait, vous pouvez calculer une estimation de la zone : l'intégralité des cellules à la limite inférieure, les cellules vides donner la limite supérieure, l'partielle des cellules de donner le max de la zone d'erreur.

Si l'erreur est trop grande pour vous, vous pouvez affiner la partielle des cellules jusqu'à ce que vous obtenez le droit de précision.

Je pense que ce sera plus facile à mettre en œuvre que la méthode géométrique qui peut nécessiter de gérer un grand nombre de cas.

Answer 4

J'aime l'approche pour le cas de 2 cercles sécants, voilà comment je voudrais utiliser une légère variation de la même approche que pour l'exemple plus complexe.

Il pourrait donner un meilleur aperçu de la généralisation de l'algorithme pour un plus grand nombre de demi-cercles qui se chevauchent.

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

(dans la pratique, peut-être que le monte-carlo méthode est utile)

Answer 5

Hmm, très intéressant problème. Mon approche serait probablement quelque chose le long des lignes suivantes:

• Un moyen de savoir ce que les zones d'intersection entre un nombre arbitraire de cercles est, c'est à dire si j'ai 3 cercles, j'ai besoin d'être en mesure de travailler sur ce que l'intersection entre ces cercles est. Le "Monte-Carlo" méthode serait une bonne façon de rapprocher ce (http://local.wasp.uwa.edu.au/~pbourke/géométrie/circlearea/).
• Éliminer tous les cercles qui sont contenues entièrement 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 c'est obligatoire.
• Choisissez 2 cercles (appelons les A et B) et la superficie totale de la zone à l'aide de cette formule:

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

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

Où A ∪ B signifie Une union B et A ∩ B signifie Une intersection B (vous pouvez faire ce travail à partir de la première étape.

• Maintenant, gardez à l'ajout de cercles et de continuer à travailler sur la zone ajoutée comme une somme / soustraction des zones de cercles et de zones d'intersections entre les cercles. Par exemple, pour les 3 cercles (appelez-le supplément du cercle C) nous travaillons sur la zone à l'aide de cette formule:

(C'est le même que ci-dessus où l' 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 avons juste travaillé, 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)

Là encore, vous pouvez trouver de la zone(A∩B∩C) ci-dessus.

Le problème est la dernière étape - le plus de cercles ajoutés plus il devient complexe. Je crois qu'il s'agit d'une extension pour travailler sur la zone d'intersection finie de l'union, ou alternativement, vous pouvez être en mesure de manière récursive.

Également en ce qui concerne l'aide de Monte-Carlo, rapprochant le domaine de la itersection, je crois que c'est possible de réduire l'intersection d'un nombre arbitraire de cercles à l'intersection de 4 de ces cercles, qui peut être calculée exactement (aucune idée de comment faire cela, cependant).

Il est probable que la meilleure manière de faire ceci btw - la complexité augmente de façon significative (éventuellement de façon exponentielle, mais je ne suis pas sûr) pour chaque supplémentaire cercle ajouté.