Algorithme pour vérifier si un Cercle est totalement contenu dans la zone d'autres cercles

Question

Quel serait l'algorithme pour vérifier si un cercle comme le cercle bleu ci-dessous est TOTALEMENT contenu dans la zone d'autres cercles (les cercles de temps). Je veux un TRUE pour le cercle bleu et un FALSE pour le cercle rouge

L'entrée pour tous les cercles est leurs coordonnées et leur rayon.

Answer 1

Cela semble simple (EDIT: mais n'est pas): si chaque point de chaque arc de cercle donné est contenu dans au moins l'un des autres cercles, le cercle entier est contenu. Vous devrez alors trouver toutes les intersections (algorithm to detect if a Circles intersect with any other circle in the same plane) et vérifier tous les arcs spécifiés par ces intersections. Si un point "intérieur" d'un arc A1-A2 du cercle A pour deux intersections avec le cercle B (arc B1-B2, où les points A1 = B1 et A2 = B2) est contenu dans le cercle B, alors l'arc entier est contenu dans le cercle B et vice-versa. S'il vous plait corrigez moi si je me trompe.

EDIT: Ok, je sais déjà, que j'avais tort, tout comme maxim1000 montré. C'est plus compliqué que je ne le pensais. Je pense à ajouter quelque chose à ma réponse, mais je ne suis pas sûr, si c'est une solution. J'espère que ça aide, cependant. A savoir: Je pense à déterminer la surface totale des intersections entre notre cercle et tous les autres. Nous trouvons toutes les intersections séparées dans notre cercle - toutes les parties qui comprennent les mêmes points, qui sont séparés par tous les arcs qui se croisent - et trouvent leurs zones. Wu les résume. Si elle est égale à la zone de notre cercle, alors notre cercle est contenu dans d'autres cercles. Déterminer cette zone peut être un problème en soi, mais comme je l'ai dit, cela peut conduire dans la bonne direction. Laissez-moi penser aussi ..

EDIT: Après un certain temps de penser. Déterminer toutes les zones dans (multiples) cercles d'intersection est juste une question d'ajouter ou de soustraire des triangles ou ... hmmm ... comment les appeler? ... pièces jaunes comme ici sur l'image :)

Answer 2

Je ne pense pas qu'il y ait une solution facile.

Je voudrais aborder cela en prenant chaque cercle à son tour, et en effectuant une soustraction booléenne de tous les autres cercles. (Les cercles qui sont assez loin - R0 + R1 < D12 - n'interféreront pas.)

Après avoir mangé des morceaux, un cercle devient un polygone curviligne fait d'arcs de cercle, ou un ensemble de tels polygones, comme la connexité peut être brisé. Un polygone peut être représenté par la liste des cercles qui contribuent à un arc de son contour, et les points d'extrémité d'arcs sont définis par l'intersection commune de deux voisins consécutifs, ou du cercle cible et d'un voisin. Notez que le même voisin peut apparaître plusieurs fois. Pour rendre les choses un peu plus sanglantes, les polygones peuvent avoir des trous, que vous devez également représenter.

Ensuite, une opération cruciale est la soustraction d'un cercle d'un polygone curviligne. Vous devez détecter les arcs qui sont entièrement à l'intérieur du nouveau cercle et ceux qui le traversent. Après avoir obtenu les parties restantes des arcs, vous devez réorganiser les arcs restants et le nouveau (s).

Je suppose que toutes ces opérations peuvent être construites à partir d'une seule primitive qui trouve la partie d'un arc (définie par trois cercles) qui est à l'intérieur d'un disque.

Answer 3

Voici une solution brute:

• Prenez tous les cercles et trouver tous points d'intersection qui sont soit sur ou à l'intérieur le cercle test de T. diviser les bords correspondants et construire un graphique de bord:

Pour chaque bord, gardez une trace du cercle qui l'a créé.

• Tous les régions ne se chevauchant pas l'intérieur du cercle, en utilisant la cycle minimum algorithme (Find all non-overlapping polygons in a list of edges/vertices).

• Pour chaque bord de délimitation E de chaque région R vous trouvez, prenez le cercle C que E appartient. Si C est pas T (rouge) - c.-à-E est bleu, vérifier si les points sur les autres bords de R sont à l'intérieur du C:

  • Si elles sont alors C couvre R. Continuer sur la région suivante .
  • Si elles ne sont pas, alors R ne sont pas couverts par C. Boucle sur les autres bords bleus délimitant R.
  • Si à la fin R est encore ne sont pas couverts, alors T est pas complètement couvert - retour faux.

dans le diagramme ci-dessus, C contient B, alors R est couvert; mais C ne contient pas, donc ne couvre pas S

• Si vous n'êtes pas encore revenu à ce stade, puis revenir vrai.

---

cas secondaires:

• Si un certain cercle contient T, puis l'ignorer.
• Si T contient , puis différer le test d'intersection en le stockant dans une liste. À la fin refaire le test et diviser ses bords.

Cet algorithme est très inefficace, et je ne suis pas sûr à 100% s'il y a des cas plus dégénérés; Si quelqu'un à des suggestions, veuillez s'il vous plait me le faire savoir.