Discussion :

[Souleyre]

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

[nonifier]

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.

[Souleyre]

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.

[pseudocode]

Il suffit de tester les intersections segment/segment des contours des polygones. Non ?

[Souleyre]

Non car les polygones ne sont jamais sécants.

[pseudocode]

Non car les polygones ne sont jamais sécants.

?

Je peux avoir un exemple de 2 polygones non sécants qui ne sont pas à l'intérieur l'un de l'autre ?

[Souleyre]

Deux cartes à jouer posées l'une à côté de l'autre.

[Jean Dumoncel]

Bonjour,

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.

Qu'entends-tu pas "leur très grand nombre"? Pourrais-tu nous donner un ordre de grandeur?

[pseudocode]

Deux cartes à jouer posées l'une à côté de l'autre.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Pour chaque Segment Sa du Polygone A
    Pour chaque Segment Sb du Polygone B
       Si (Sa coupe Sb) retourner "A intersecte B"
   FinPour
FinPour
 
Pa = un sommet quelconque de A
Si (Pa est a l'intérieur du Polygone B) retourner "A est inclus dans B"
 
Pb = un sommet quelconque de B
Si (Pb est a l'intérieur du Polygone A) retourner "B est inclus dans A"
 
retourner "A et B sont disjoints"

[Souleyre]

Qu'entends-tu pas "leur très grand nombre"? Pourrais-tu nous donner un ordre de grandeur?

Les polygones contenants entre 5.000 et 10.000, les polygones inclus entre 4.000 et 8.000

Pour chaque Segment Sa du Polygone A
Pour chaque Segment Sb du Polygone B
Si (Sa coupe Sb) retourner "A intersecte B"
FinPour

Il n'y a jamais de polygones sécants, ils sont:

• 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)

[pseudocode]

Il n'y a jamais de polygones sécants, ils sont:

• 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.

[Souleyre]

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

Exact.

Ca revient a considere B comme convexe, car de toutes façons A ne coupe jamais B

Faux. Imagine un M majuscule fermé à sa base et contenant un autre M majuscule fermé, les 2 polygones sont bien concaves.

[pseudocode]

Faux. Imagine un M majuscule fermé à sa base et contenant un autre M majuscule fermé, les 2 polygones sont bien concaves.

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.

[Souleyre]

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.

[pseudocode]

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.

[Souleyre]

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.

[souviron34]

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...

[Graffito]

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.

[Souleyre]

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).

La méthode du barycentre ne convient hélas pas aux cas des polygones concaves!

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...

Cette méthode me paraît très intéressante. Pourrais-tu me mettre sur la voie?

[Graffito]

La méthode du barycentre ne convient hélas pas aux cas des polygones concaves!

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).

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 .