J'ai une tâche où j'ai un nombre quelconque de cercles. Tout ce que je sais à propos de l'un est son centre et rayon. Maintenant, j'ai besoin de trouver le nombre de zones qui se chevauchent par exactement 3 cercles. J'ai essayé de le résoudre en sachant que les cercles se chevauchent lorsque la distance entre leurs centres est plus courte que la somme des rayons, mais cela ne m'a rien donné.Nombre de zones chevauchées par exactement 3 cercles
Un algorithme de ligne de balayage devrait faire le travail.
En savoir plus sur les algorithmes de ligne de balayage en général here, sur un algorithme particulier (très important) here. La structure globale d'un algorithme pour ce problème serait similaire à celle de l'algorithme de Bentley-Ottmann. Voici quelques détails (pas une description complète mais plutôt une esquisse, une description complète
Prenez tous les points les plus à gauche (min X) et les plus à droite (max X) de chaque cercle, et triez tous ces points par leur coordonnée X. les à une file d'attente de priorité.
Exécuter une ligne de balayage vertical le long de l'axe X. la ligne contient un ensemble de coordonnées Y des points où elle croise les cercles à la coordonnée actuelle X, triés par Y.
Une fois que la ligne de balayage atteint un point du cercle le plus à gauche, ajoutez-la deux fois à la collection - une fois pour le demi-cercle supérieur et une fois pour le demi-cercle inférieur. points correspondants de la collection. Gardez une trace du nombre de fois que chaque intervalle entre deux points successifs est couvert par des cercles. Gardez une trace de l'identité de ces zones. Chaque fois que deux points appartenant à des cercles différents apparaissent l'un à côté de l'autre, calculez leurs points d'intersection et insérez-les dans la file d'attente de points. Chaque fois que la ligne de balayage atteint un point d'intersection, permutez les points correspondants dans la collection et ajustez les identités de zone et les chevauchements.
Il est facile de visualiser l'algorithme en dessinant des cercles sur une feuille de papier, en coloriant chaque zone différemment et en déplaçant lentement une règle sur le dessin, en notant comment elle croise les cercles et les zones.
Également google "algorithme de balayage de ligne" "cercles".
Je vote pour clore cette question hors-sujet parce que c'est une question de géométrie de base, pas de programmation. –
Par région, voulez-vous dire les composants connectés? Seriez-vous satisfait d'une approximation discrète ou avez-vous besoin d'un résultat exact? –
Demandez-vous le nombre (nombre) de zones sans chevauchement, ou chaque région à triple liaison doit-elle être comptée comme une seule, malgré les chevauchements, ou autre chose? Et la * taille * de chacune de ces régions est-elle pertinente? –