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 ?
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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 ?
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Bonjour,
Qu'entends-tu pas "leur très grand nombre"? Pourrais-tu nous donner un ordre de grandeur?
Pour une bonne utilisation des balises codec'est ici!
Petit guide du voyageur MATLABien :
La nature est un livre écrit en langage mathématique. Galilée.
si ce sont des simples réponses booléennes que vous désirez, il est assez facile d'obtenir la réponse en faisant faire le calcul par le GPU…
à condition que les polygones soient tous décrits de manière cohérente quant à la "winding rule" - càd tous de la même façon, par exemple clockwise…
il suffit de remarquer que si le polygone A est inclus dans le polygone B alors
si l'on dessine les 2 polygones dans un espace plus grand que l'union de leurs bounding boxes, d'abord A et ensuite B en inversant sa "winding rule" (donc ici anticlockwise) alors un point situé à l'extérieur choisi comme "témoin" ne changera pas de couleur…
par contre si B n'est pas entièrement dans A, toute la surface de dessin aura changé de couleur…
Evidemment, il faudra examiner si la perte de précision due à la conversion de l'espace mathématique en surface de pixels est tolérable dans votre contexte…
(voir aussi le chapitre "Polygon Tesselation" de "OpenGL Programming Guide", le "red book" …)
Bonsoir,
Le fait est que la précision est souvent attendue en absolue, et ce quelques soit la taille du polygone... Hélas, pour améliorer la précision d'un facteur 2, on multiplie par 4 la taille de l'image. Très vite, on perd l'intérêt du parallélisme.si ce sont des simples réponses booléennes que vous désirez, il est assez facile d'obtenir la réponse en faisant faire le calcul par le GPU…
C'est donc souvent une fausse bonne idée de ramener un calcul sur des géométries à un calcul sur des images.
Le principe de l'image est parfois utilisé comme premier filtre pour ce genre de calcul (grille). Mais là encore, on se heurte au choix du pas qui rend cette optimisation efficace si bien que l'on utilise plutôt des structures telles les QuadTree voir RTree.
Ensuite, les temps de calcul restent raisonnables en traitant en séquentiel des géométries complexes, à l'aide de quelques optimisations sur les recherches d'intersections en particulier...
Bye
Absolument...
La géométrie est de la géométrie. Le traitement d'images est, par définition, lié à une définition (taille du pixel) et un découpage et un moyennage...
Un point en géométrie n'a pas d'épaisseur...
Une interpolation géométrique peut donner un pixel. Une interpolation de pixel donne un point (fictif) dans un espace qui ressemble nettement plus à de la géométrie pure, puisqu'avoir un pixel de coordonnées (2.345 , 3.623) est impossible...
Les algorithmes de géométrie pure sont faits pour solutionner les problèmes de géométrie pure, ceux de traitements d'images pour solutionner les problèmes liés aux images..
Ne mélangeons pas les genres, si l'on ne veut pas risquer soit de prendre un bulldozer pour écraser une mouche, soit d'avoir à faucher un hectare avec une paire de ciseaux à ongles...
Comme je l'ai mentionné, les liens cités ci-dessus, ainsi que CGAL tout au moins, sont des algos de maths/géométrie pure(s), ce sont ceux-ci qu'il faut utiliser pour un problème, au moins tel que celui posté par le PO...
Note : effectivement, comme tu le mentionnes, j'ai un mal fou à faire comprendre que par exemple afficher un modèle numérique (calculé en maillage) sous forme d'une image est une approximation, mais pas la réalité.. C'est d'ailleurs une des erreurs fondamentales de beaucoup (puisque tu as l'air pas mal dans le domaine) de SIGs... Représenter des valeurs discrètes (ou discontinues, ou n'ayant aucune signification) par une image, qui par définition est continue...
Répondre avec citation
Partager