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
Mais alors ça multiplie énormément les calculs: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
- Calcul du barycentre
- Calcul pour savoir si le barycentre est inclus ou non
- Si oui, calculer le point le plus proche...
Inenvisageable avec une telle masse d'individus.
Mais, ces calculs ne se font qu'une fois pour chacun des polygones.Mais alors ça multiplie énormément les calculs:
L'interet de l'optimisation depend évidemment du nombre de calculs (pour déterminer si un polygone se trouve dans un autre) qui vont être exécutés par la suite.
" Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson
faire un dessin est la meilleure solution pour visualiser :Envoyé par Souleyre
A droite est l'union des 2 (en jaune)
Au milieu est l'intersection (en rouge)
A gauche, si l'un est dans l'autre, union = intersection.
(enfin, pas tout à fait : disons que l'intersection est l'un et l'union est l'autre)..
- On calcule l'union
- Ou on calcule l'intersection
Des algos très performants existent (voir le code (en C) de X11 (par exemple XFree86 ) la sous-partie sur les Region (XUnionRegion))
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Tu as raison. En réalité mes 4 cas de figures sont les suivants:faire un dessin est la meilleure solution pour visualiser
[IMG]d:\Sans titre.jpg[/IMG]
Et c'est bien ce que je recherche, un algorithme pour évaluer l'inclusion ou l'exclusion à partir des coordonnées des points de l'enveloppe.
Ta piste sur XFree86 pourrait être intéressante mais je recherche plutôt un code en VB6.
Zut, je m'aperçois que je ne sais pas inclure une image!
J'essaye les pièces jointes:
L'idée de Souviron parait séduisante.
J'ai soudain repensé à une ancienne discussion où le problème était intégralement traité pour des triangles.
Voici la référence:
http://www.developpez.net/forums/d26...s-quelconques/
Maintenant pour appliquer cela à des polygones quelconques il suffit d'appliquer les propriétés de l'intersection et de la réunion, en découpant les polygones en triangles.
Découper un polygone convexe en triangles c'est un jeu d'enfant. S'il est concave c'est un peu plus délicat, et je n'entrevois pour le moment que des solutions récursives.
Bref supposons qu'on trouve un tel algo de décomposition, il reste à voir si c'est jouable pour de très gros polygones du point de vue efficacité.
C'est juste une piste.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
Le problème majeur c'est qu'il peut y avoir une grande quantité de polygones concaves ce qui rend cette solution impraticable.S'il est concave c'est un peu plus délicat
De la même manière qu'il existe un algorithme ultra-simple pour déterminer si le point M(x,y) est inclus dans le polygone Poly(x,y), il me semble qu'il doit bien (!) exister un algorithme analogue pour vérifier l'inclusion stricte de PolyB(x,y) dans PolyA(x,y), non?
C'est un problème finalement assez banal qui a bien dû être résolu depuis la naissance de la géométrie analytique.
L'idée est naturelle, cela a du bon sens, mais ....De la même manière qu'il existe un algorithme ultra-simple pour déterminer si le point M(x,y) est inclus dans le polygone Poly(x,y), il me semble qu'il doit bien (!) exister un algorithme analogue pour vérifier l'inclusion stricte de PolyB(x,y) dans PolyA(x,y), non?
L'inclusion d'un polygone dans un autre est logiquement équivalente a une infinité de postulats du premier type. Dans le cas où le contenant (ou présupposé tel) est convexe l'inclusion du contenu (ou présupposé tel) se résume à l'inclusion de ses sommets, que le contenu soit convexe ou non. Mais dans le cas ou le contenant n'est pas convexe on n'a rien...
Une idée serait peut être de découper le contenant en polygones convexes et de tester l'inclusion des traces du contenu dans chaque sous-polygone convexe.
Mais là encore quel procédé de découpage utiliser?
Comment obtenir rapidement les sommets des traces (sachant quand même que le problème de l'intersection de deux segments dans le plan est un problème classique et résolu)?
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
Le code est en C.
Passer du C au Pascal est assez facile, non ?
L'union de 2 polygones quelconques s'intersectant est (relativement) facile.. (il faut suivre un polygone, puis suivre le second quand on intersecte, etc). Cependant, cela peut générer en sortie des trous , et donc une liste de trous (c'est à dire un polygone décrivant l'enveloppe et une liste de polygones décrivants les trous).
J'ai un algo qui fait ça (en C).
L'intersection est potentiellement un ensemble de polygones.
Comme le code de X11 couvre les domaines de l'union et de l'intersection, ainsi que la soustraction d'une région et d'une autre, de même que l'opération booléenne Xor (qui est la différence entre l'union et l'intersection), et que ce code est franchement pas mal optimisé, c'est la raison pour laquelle je le recommande....
Et ce n'est pas très long (environ 5000 lignes)..
La géométrie (et en particulier les algorithmes) est (sont) parfois simples d'apparence et compliqué(e)(s) de mise en oeuvre...
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Bonsoir,
J'arrive un peu après la bataille, mais si ça peut vous donner des idées...
Une première bibliothèque C++ réalise les opérations booléennes sur les polygones (à trou en bonus) : GEOS (descendante de JTS en java). Elle est plutôt robuste et fournit une interface C. Elle est intégré à postgis, cartouche spatiale du SGBD postgres (du coup, elle est fortement testée). Elle permet aussi de répondre à la question initiale.
http://trac.osgeo.org/geos/
Le principe dans cette bibliothèque repose sur l'utilisation d'un graphe pour le calcul des frontières résultant d'une opération booléenne (Union, Intersection, Différence, Différence symétrique).
L'utilisation du graphe permet du coup de traiter l'ensemble des opérations en un seul algorithme.
Une autre bibliothèque, CGAL (Computational Geometry Algorithms Library) fournit des outils du même ordre.
http://www.cgal.org/Manual/last/doc_.../contents.html
+1. Il est en particulier difficile de détecter les potentiels cas foireux à traiter; avant de se trouver face à eux sur des géométries inhabituelles... Les principaux problèmes sont en particulier liés aux approximations numériques; d'où les précautions prises dans les bibliothèques telles CGAL...La géométrie (et en particulier les algorithmes) est (sont) parfois simples d'apparence et compliqué(e)(s) de mise en oeuvre...
Ce document associé à JTS donne une bonne introduction pour ce type d'algorithmes :
http://www.vividsolutions.com/jts/bi...al%20Specs.pdf
bye
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...
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager