Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Polygones quelconques imbriqués
Bonjour à tous,
On connaît bien l'algorithme permettant de savoir si un point se situe à l'intérieur d'un polygone.
Existerait-il un algorithme déterminant si un polygone est à l'intérieur d'un autre polygone?
Je précise que les polygones en question peuvent être concaves et jointifs par un certain nombre de faces.
Souleyre
En sachant si un point se situe à l'intérieur d'un polygone, tu peux tester si tous les sommets de ton polygone sont bien intérieurs à ton polygone externe.
Ceci n'est valable que si ton polygone externe est convexe.
Si tes 2 polygones sont concaves, tu peux tester s'il n'y a pas d'intersection pour de l'ensemble des segments des 2 polygones.
Bien sûr, on ne sait rien a priori de la nature des polygones, concaves ou convexes, jointifs ou non. La solution brutale qui consisterait d'examiner point par point s'il existe au moins un point à l'intérieur d'un autre polygone est à exclure en raison de leur très grand nombre.
Au cas présent, il s'agit de trouver un algorithme généraliste.
Il suffit de tester les intersections segment/segment des contours des polygones. Non ?
Non car les polygones ne sont jamais sécants.
Envoyé par Souleyre
?
Je peux avoir un exemple de 2 polygones non sécants qui ne sont pas à l'intérieur l'un de l'autre ?
Deux cartes à jouer posées l'une à côté de l'autre.
Bonjour,
Qu'entends-tu pas "leur très grand nombre"? Pourrais-tu nous donner un ordre de grandeur?
Ah, c'est pas faux.
Auquel cas il suffit de faire 2 tests pour savoir si on est dans ce cas. Non ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
Les polygones contenants entre 5.000 et 10.000, les polygones inclus entre 4.000 et 8.000Qu'entends-tu pas "leur très grand nombre"? Pourrais-tu nous donner un ordre de grandeur?
Il n'y a jamais de polygones sécants, ils sont:Pour chaque Segment Sa du Polygone A
Pour chaque Segment Sb du Polygone B
Si (Sa coupe Sb) retourner "A intersecte B"
FinPour
- disjoints extérieurs
- jointifs extérieurs
- jointifs intérieurs (l'un à l'intérieur de l'autre)
- disjoints intérieurs (l'un à l'intérieur de l'autre)
et donc ta question "déterminer si un polygone est à l'intérieur d'un autre polygone" se résume a savoir si on est dans l'un des 2 derniers cas. C'est à dire que tous les sommets du polygone A sont a l'intéreur du polygone B. Ca revient a considere B comme convexe, car de toutes façons A ne coupe jamais B.
Exact.ta question "déterminer si un polygone est à l'intérieur d'un autre polygone" se résume a savoir si on est dans l'un des 2 derniers cas
Faux. Imagine un M majuscule fermé à sa base et contenant un autre M majuscule fermé, les 2 polygones sont bien concaves.Ca revient a considere B comme convexe, car de toutes façons A ne coupe jamais B
Oui, ils sont bien concaves tous les 2.
Je disais juste qu'il suffisait de verifier tous les sommets du polygone A sont a l'intérieur du polygone B, ce qui est le meme test que pour 2 polygones convexes.
Tu as raison, mais il s'agit là d'une méthode un peu brutale.
Intuitivement, il me semble qu'il doit exister une méthode analytique à partir des coordonnées de l'ensemble des points des polygones A & B.
Un peu brutale ?
Ca ne mes semble pas excessif.
Il faut voir la configuration de tes 10.000 polygones. S'ils ne sont pas tous superposés les uns aux autres, une comparaison de leurs bounding box devrait réduire les tests necessaires. Au pire des cas (inclusion du polygone), il faut faire un test d'inclusion point/polygone pour chaque sommet du polygone.
Et bien, s'il n'existe pas de méthode analytique élégante, il me faudra me résoudre à tester l'inclusion de chaque sommet du groupe B dans chaque polygone du groupe A! (quelques heures de traitement en perspective!)
Merci quand même pour ton aide.
la méthode "élégante" consiste à faire des opérations booléenes sur les polygones...
Si union = intersection, alors l'un des deux est compris dans l'autre...
Pour optimiser, on peut utiliser determiner pour chaque polygone un "centre" (barycentre opar exemple, mais pas besoin de grande précision), et à partir de ce centre les 2 circles internes et externes qui contiennent tous les points du polygone (rayon interne/externe = min/max des distances des sommets au centre).
Ensuite, on déduira rapidement :
- si les cercles externes de PolX et PolY sont disjoints, les 2 poly sont disjoints extérieurs.
- si le cercle externe de PolX est inclus dans le cercle interne de PolY, alors POLX est dans POLY.
Sinon, on fait le calcul normal.
La méthode du barycentre ne convient hélas pas aux cas des polygones concaves!Pour optimiser, on peut utiliser determiner pour chaque polygone un "centre" (barycentre opar exemple, mais pas besoin de grande précision), et à partir de ce centre les 2 circles internes et externes qui contiennent tous les points du polygone (rayon interne/externe = min/max des distances des sommets au centre).
Cette méthode me paraît très intéressante. Pourrais-tu me mettre sur la voie?la méthode "élégante" consiste à faire des opérations booléenes sur les polygones...
Si union = intersection, alors l'un des deux est compris dans l'autre...
La meilleure position théorique pour le "centre" est celle qui minimise la différence entre rayon interne et rayon externe. Toutefois, la méthode d'optimisation fonctionne avec tout point situé à l'intérieur du polygone (ou sur le bord, auquel cas le rayon interne sera égal à 0).La méthode du barycentre ne convient hélas pas aux cas des polygones concaves!
Ainsi, si le "barycentre" est n'est pas à l'intérieur, on peut utiliser comme "centre" le point du polygone le plus proche du barycentre.
Répondre avec citation
Partager