zone combinée de cercles qui se chevauchent
https://stackoverflow.com/questions/1667310
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis récemment tombé sur un problème où j'ai eu quatre cercles (rayon) et mi-points et a dû calculer la zone de l'union de ces cercles.
Exemple d'image:
Pour deux cercles, il est assez facile,
je peux calculer la fraction de la zone de chacune des cercles qui ne sont pas à l'intérieur des triangles puis calculer l'aire des triangles.
Mais est-il un algorithme intelligent que je peux utiliser quand il y a plus de deux cercles?
La solution
Tous les intersections du cercle sur le périmètre extérieur (par exemple B, D, F, H sur le schéma ci-dessous). Se connecter ensemble avec les centres des cercles correspondants pour former un polygone. La zone de l'union des cercles est la superficie du polygone + la surface des tranches de cercle défini par les points d'intersection consécutifs et le centre du cercle entre eux. Vous devrez aussi tenir compte des trous.
Autres conseils
Je suis sûr qu'il ya un algorithme intelligent, mais voici un sourd-muet pour éviter de devoir chercher;
- mettre une boîte de délimitation autour des cercles;
- générer des points aléatoires dans la zone de délimitation;
- Figure savoir si le point est à l'intérieur aléatoire l'un des cercles;
- calculer la surface par une simple addition et de la division (proportion_of_points_inside * area_of_bounding_box).
Bien sûr, il est muet, mais:
- vous pouvez obtenir une réponse que vous voulez précis, juste générer plus de points;
- il fonctionnera pour toutes les formes que vous pouvez calculer l'intérieur / extérieur distinction;
- il paralléliser magnifiquement afin que vous puissiez utiliser tous vos cœurs.
Pour une solution différente de celle précédente vous pourriez produire une estimation avec une précision arbitraire en utilisant un quadtree.
Ceci fonctionne également pour une union de forme si vous pouvez dire si un carré est à l'intérieur ou à l'extérieur ou coupe la forme.
Chaque cellule a un des états: vide, pleine, partielle
L'algorithme consiste à « dessin » cercles dans le quadtree en commençant par une faible résolution (4 cellules par exemple marquées comme étant vide). Chaque cellule est:
- l'intérieur d'au moins un cercle, puis marquer la cellule complète,
- à l'extérieur tous les milieux, marquer la cellule vide,
- marque bien la cellule partielle.
Une fois terminé, vous pouvez calculer une estimation de la zone: les cellules pleines donnent la limite, plus les cellules vides donnent la limite, plus les cellules partielles donnent l'erreur de la zone max
.Si l'erreur est trop grand pour vous, vous affinez les cellules partielles jusqu'à ce que vous obtenez la précision droite.
Je pense que ce sera plus facile à mettre en oeuvre que la méthode géométrique qui peut nécessiter de traiter un grand nombre de cas particuliers.
La réponse de fourmis Aasma a donné l'idée de base, mais je voulais le rendre un peu plus concret. Jetez un oeil sur les cinq cercles ci-dessous et la façon dont ils ont été décomposées.
- Les points bleus sont des centres de cercle.
- Les points rouges sont des intersections aux limites du cercle.
- Les points rouges avec un intérieur blanc sont des intersections de limite de cercle qui sont ne figure pas dans les autres cercles .
L'identification de ces 3 types de points est facile. Maintenant construire une structure de données de graphe où les noeuds sont des points bleus et les points rouges avec un intérieur blanc. Pour chaque cercle, mettre un bord entre le milieu du cercle (rond bleu) et chacune de ses intersections (points rouges à l'intérieur blanc) sur sa limite.
décompose l'union de cercle en un ensemble de polygones (bleutée) et des morceaux de tarte circulaire (vert ombragé) qui sont disjoints et par paires couvrent l'union d'origine (à savoir une partition). Étant donné que chaque pièce ici est quelque chose qui est facile à calculer la zone, vous pouvez calculer la zone de l'Union en additionnant les zones des pièces.
J'adore l'approche du cas de 2 cercles entrecroisées - voici comment j'utiliser une légère variation de la même approche pour l'exemple plus complexe.
Il pourrait donner une meilleure idée de généraliser l'algorithme pour un plus grand nombre de demi-cercles se chevauchent.
La différence ici est que je commence en reliant 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 laisse généralisent mieux.
(dans la pratique, peut-être la méthode de Monte-Carlo est utile)
(source: secretGeek.net )
Si vous voulez un discret (par opposition à un flux continu) réponse, vous pourriez faire quelque chose de semblable à un algorithme de peinture de pixels.
Dessiner les cercles sur une grille, puis la couleur de chaque cellule de la grille, si elle est principalement contenue dans un cirle (à savoir, au moins 50% de sa surface est à l'intérieur de l'un des cercles). Pour ce faire, pour l'ensemble du réseau (où le réseau couvre l'ensemble de la zone couverte par les cercles), puis compter le nombre de cellules colorées dans la grille.
Hmm, problème très intéressant. Mon approche serait probablement quelque chose le long des lignes de ce qui suit:
- Les travaux sur une façon de travailler ce que les zones d'intersection entre un nombre arbitraire de cercles est, à savoir si j'ai 3 cercles, je dois être en mesure de comprendre ce que l'intersection entre ces cercles est. La méthode « Monte-Carlo » serait un bon moyen de rapprocher ce ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
- éliminer tous les milieux qui sont contenus entièrement dans un autre plus grand cercle (regarde le rayon et le module de la distance entre le centre des deux cercles) Je ne pense pas obligatoire.
- Choisissez 2 cercles (les appeler A et B) et de travailler sur la superficie totale en utilisant la formule suivante:
(cela est vrai pour toutes les formes, que ce soit cercle ou autre)
area(A∪B) = area(A) + area(B) - area(A∩B)
Où A ∪ B signifie A B et A ∩ B union signifie A Intersection B (vous pouvez nous en sortir de la première étape.
- Maintenant continuer à ajouter des cercles et continuer à travailler la zone ajoutée comme une somme / soustraction des zones de cercles et des zones d'intersection entre les cercles. Par exemple, pour 3 cercles (appeler le cercle supplémentaire C), nous travaillons sur la région en utilisant la formule suivante:
(Ceci est la même chose 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 préciser, 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 zone (A∩B∩C) d'en haut.
Le peu délicat est la dernière étape - les autres cercles sont ajoutés plus il devient complexe. Je crois qu'il ya une extension pour l'élaboration de la zone d'une intersection avec une union finie, ou bien vous pouvez être en mesure de travailler de manière récursive dehors.
Aussi en ce qui concerne l'utilisation de Monte-Carlo pour se rapprocher de la zone de itersection, je crois que son possible de réduire l'intersection d'un nombre arbitraire de cercles à l'intersection de quatre de ces cercles, qui peut être calculé exactement (aucune idée de le faire cependant).
Il y a probablement une meilleure façon de le faire BTW -. La complexité augmente de manière significative (peut-être de façon exponentielle, mais je ne suis pas sûr) pour chaque cercle supplémentaire ajouté
Je travaille sur un problème de simulation des champs d'étoiles qui se chevauchent, en essayant d'estimer la véritable star compte des zones de disque dans les champs denses réels, où l'on peut masquer les étoiles les plus grandes pâles brillantes. Moi aussi, je l'avais espéré pouvoir le faire par une analyse rigoureuse et formelle, mais n'a pas pu trouver un algorithme pour la tâche. Je l'ai résolu en générant les champs d'étoiles sur un fond bleu en tant que disques verts, dont le diamètre a été déterminé par un algorithme de probabilité. Une routine simple peut les jumeler pour voir s'il y a un chevauchement (tourner la paire d'étoile jaune); alors un nombre de pixels des couleurs génère la zone observée pour le comparer à la zone théorique. Cela génère alors une courbe de probabilité pour les vrais chefs d'accusation. La force brutale peut-être, mais il semble fonctionner OK.
(source: 2from.com )
Il existe des solutions efficaces à ce problème en utilisant ce qu'on appelle les schémas électriques. C'est vraiment lourd maths si et pas quelque chose que je voudrais aborder désinvolture. Pour une solution « facile », rechercher des algorithmes de balayage de ligne. Le principe de base est que vous diviser la figure en bandes, où le calcul de la zone dans chaque bande est relativement facile.
Ainsi, sur la figure contenant tous les cercles avec rien effacé, tracer une ligne horizontale à chaque position qui est soit la partie supérieure d'un cercle, le fond d'un cercle ou l'intersection de 2 cercles. Notez que l'intérieur de ces bandes, tous les domaines dont vous avez besoin pour calculer la même apparence: un « trapèzes » 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 venez de le faire 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 sur la figure. Avec une certaine utilisation de la structure intelligente des données, vous pouvez améliorer cette méthode ligne de balayage à O (N ^ 2 * log (N)), mais à moins que vous avez vraiment besoin, il est sans doute pas la peine.
J'ai trouvé ce lien qui peut être utile. Il ne semble pas être une réponse définitive bien. Google répond . Une autre référence pour trois cercles est théorème de Haruki . Il y a un papier là aussi.
En fonction de ce problème que vous essayez de le résoudre pourrait être suffisant pour obtenir une limite inférieure et supérieure. Un est facile, la somme de tous les cercles majorant. Pour une limite, vous pouvez choisir un seul rayon inférieur tel qu'aucun des cercles se chevauchent. Afin de mieux que trouver le plus grand rayon (jusqu'au rayon réel) pour chaque cercle de sorte qu'il ne se chevauchent pas. Il devrait également être assez trivial pour enlever les cercles complètement chevauchée (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 ), ce qui améliore à la fois la partie supérieure et la limite inférieure. Vous pouvez également obtenir un meilleur supérieur lié si vous utilisez votre formule paire sur des paires arbitraires au lieu de la somme de tous les cercles. Il pourrait y avoir une bonne façon de choisir les paires « meilleures » (les paires qui se traduisent par la superficie totale minimale.
Étant donné une limite supérieure et inférieure, vous pourriez être en mesure de mieux régler une approche Monte-carlo, mais rien ne vient à l'esprit spécifique. Une autre option (encore une fois en fonction de l'application) est de pixelliser les cercles et compter les pixels. Il est fondamentalement 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ée pour produire arbitrairement petite erreur:
- approximatif chaque cercle par un polygone régulier centré sur le même point
- Calculer le polygone qui est l'union des cercles approchées
- Calculer la zone du polygone fusionné
Les étapes 2 et 3 peuvent être effectués à l'aide standard, des algorithmes faciles à trouver de la géométrie algorithmique.
De toute évidence, les plus côtés que vous utilisez pour chaque polygone approchante, le plus proche de votre réponse exacte serait. Vous pouvez approcher en utilisant des polygones inscrits et circonscrits pour obtenir des limites sur la réponse exacte.
Ceci peut être résolu en utilisant théorème de Green , avec une complexité de n ^ 2log (n). Si vous n'êtes pas familier avec théorème de Green et que vous voulez en savoir plus, voici le vidéo et notes de Khan Academy. Mais pour le bien de notre problème, je pense que ma description sera suffisant.
Désolé pour les liens vers les photos, que je ne peux pas poster des 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
alors l'ERS est tout simplement la zone de la région R et peut être obtenu en résolvant l'intégrale fermée ou LHS ce qui est exactement ce que nous allons faire.
L'intégration sur le chemin dans le sens inverse nous donne la Espace de la région et l'intégration dans le sens horaire nous donne négatif du Espace . Donc,
AreaOfUnion = (intégration le long d'arcs rouges dans le sens anti-horaire + intégration le long d'arcs bleus dans le sens horaire)
Mais le truc cool est si pour chaque cercle si nous intégrons les arcs qui ne sont pas à l'intérieur de tout autre cercle que nous obtenons notre espace nécessaire à dire que nous obtenons l'intégration dans un sens anti-horaire le long de tous les arcs rouges et l'intégration ainsi que tous les arcs bleus le long dans le sens horaire direction. JOB !!! DONE
Même les cas où un cercle ne coupe pas avec tout autre est prise en charge.
Voici le lien GitHub à mon C ++ code
L'approche peinture pixel (comme suggéré par @Loadmaster) est supérieure à la solution mathématique dans une variété de façons:
- La mise en œuvre est beaucoup plus simple. Le problème ci-dessus peut être résolu en moins de 100 lignes de code, que cette solution jsFiddle démontre ( surtout parce qu'il est beaucoup plus simple sur le plan conceptuel, et n'a pas de bord ou des cas d'exceptions à traiter).
- Il adapte facilement à des problèmes plus généraux. Il fonctionne avec toutes les formes, quelle que soit la morphologie, tant qu'il est renderable avec les bibliothèques de dessin 2D (à savoir, « tous! ») - cercles, ellipses, splines, polygones, vous le nom. Heck, même les images bitmap.
- La complexité de la solution de peinture de pixel 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.
- Et en parlant de la performance, vous obtiendrez souvent l'accélération matérielle gratuitement, comme la plupart des bibliothèques 2D modernes (comme la toile de HTML5, je crois) déchargeront le rendu du travail à des accélérateurs graphiques.
Le seul inconvénient à la peinture de pixel est la précision finie de la solution. Mais c'est réglable en rendant simplement plus ou moins toiles que la situation exige. Notez aussi que anti-aliasing dans le code de rendu 2D (souvent activée par défaut ) donnera mieux que au niveau des pixels de précision. Ainsi, par exemple, ce qui rend une figure 100x100 dans une toile de même dimension devrait, je pense, donner une précision de l'ordre de 1 / (100 x 100 x 255) = 0,000039% ... ce qui est probablement « assez bon » pour tous, mais 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);
