ampholyte a écrit:Supposons que j'ai un polygone donné (qu'on notera A), je souhaiterais insérer un polygone extrait d'une base de donnée (noté B), pour l'insérer dans le polygone A tout en vérifiant qu'il est inclut dans le polygone B.
Le petit schéma explicatif
C'est pour cette raison que j'essaye de trouver un moyen de connaître l'inclusion ou non d'un point dans un polygone. J'aurais juste à parcourir l'ensemble des points de mon polygone B pour savoir s'il est inclus ou non dans A
J'ai eut, il y a longtemps à traiter un cas similaire.
Mais les conditions initiales étaient un peu différence. En particulier les polygones à considérer étaient tous des polygones convexes. Ceux-ci étaient définis à partir des coordonnées de leurs sommets. Toutes les coordonnées, y compris celle du point M à tester étaient des entiers.
Je pense qu'en organisant un peu les choses, on doit pouvoir adapter la méthode que j'avais utilisée à des polygones quelconques (il faudra certainement découper les polygones concaves en un ou plusieurs sous-parties convexes) et sans problème extrapoler les calculs à des coordonnées réelles (ou float).
Le système dans lequel de travaillais permettait des calculs matriciels rapides sur les entiers uniquement. Il fallait donc autant que possible ne 'jouer' qu'avec des opérations et des indicateurs produisant des résultats entiers. Ce qui ne posait pas de problème car de toute façon les données de base et les résultats ne pouvaient être que des coordonnées entières.
Pour faciliter les explications, prenons un exemple simple : voyons comment on pourrait déterminer simplement (avec des calcul sur les entiers seulement) si le point M(x,y) est ou n'est pas dans le polygone convexe ABCD suivant :
Lidée maitresse de cette détermination est basée sur le fait que le point M doit être à lintérieur de la région du plan (mais on peut étendre cette notion à lespace) délimité par les cotés du polygone.
En observant la figure, on se rend vite compte que M est à lintérieur sil est simultanément du bon coté de chacune des droites supportant les cotés successifs du polygone.
En effet, chaque droite supportant un des coté du polygone partage le plan en deux demi-plans dont léquation caractèristique peut sexprimer facilemetn en fonction des coordonnées x et y.
Ainsi, par exemple, la droite AB partage le plan en deux demi-plans :
- Le demi-plan supérieur (au-dessus de AB) pour lequel :
- Le demi-plan inférieur (au-dessous de AB) pour lequel :
Sachant que la droite elle-même correspond à lensemble des points vérifiant légalité
Le même raisonnement peut être tenu pour chacun des coté du polygone en considérant léquation caractéristique de chacune des droites soutenant les cotés du polygone.
Dans notre cas, M(x,y) est à lintérieur du polygone, sil est simultanément
- en-dessous de AB (
),
- à gauche de BC (
),
- en-dessus de CD (
),
- à droite de DA (
),
Donc, à partir des coordonnées des point ABCD du polygone, il convenait de construire une les équations caractéristiques des droites directrice de chaque coté du polygone, convenablement organisées et ordonnées dans une matrice M de façon à ce quun simple produit matriciel permette de déterminer de quel coté (positif ou négatif) le point M de coordonnées (x,y) se trouve.
Notons que cela revient quelque part à étudier le signe dun produit vectoriel. Si on se débrouille bien, seul le signe des éléments de ce produit matriciel est à considérer et à comparer avec le résultat attendu pour un point à lintérieur du polygone.
Dans mon cas, les cas où M se trouve exactement sur un coté du polygone étaient à rejeter, ce qui me faciliter les choses car si un des éléments du produit matriciel (produit vectoriel) était nul (égal à zéro) cest que le point M était aligné avec un des cotés, donc au pire sur un des coté est donc il nétait pas strictement à lintérieur du polygone.
Mais ce système fonctionne aussi bien si l'on considère les coté comme faisant partie de l'intérieur du polygone. Dans ce cas, un résultat nul n'exclu pas le point M.
L'avantage était un calcul rapide (manipulation que d'entiers) et surtout un court-circuit qui évite d'avoir à tester M avec tous les points du polygone. C'était important car les polygone que je traitais été des contours géographique avec plusieurs milliers de points.
Il suffisait d'un signe non conforme pour ^sortir de la boucle de test et indiquer que M ne faisait pas partie du polygone.
Notons aussi qu'il était facile d'inverser le sens du test pour déterminer si le point M est à l'extérieurou l'intérieur du polygone.
Maintenant, cela ne fonctionne que pour les polygones convexes.
En cas de polygone quelconques, il faut mettre en ordre les choses.
Soit en découpant un polygone concave en une ou plusieurs sous partie convexe; on testera donc l'intériorité du point M(x,y) en plusieurs étapes, un test pour chaque sous-polygone:
Le polygone ABCDEFG est découpé en deux polygone convexes. Le point M appartient au polygone ABCDEFG initial s'il appartient à ABCG ou à CDEFG.
Soit en considérant l'enveloppe convexe du polygone quelconque dans lequel on repère tous les sous-polygones convexes. On teste alors l'intériorité du point M(x,y) en deux étapes. La première consistant à vérifier aue M est à l'intérieur de l'enveloppe convexe. Puis, en cas de résultat positif, on vérifie que M n'appartient à aucune des sous-concavités:
On considère dans un premier temps l'enveloppe ABDEFG convexe du polygone inital ABCDEFG.
Dans un premier temps on vérifie donc que M(x,y) appartient à cette enveloppe ABDEFG.
Si c'est le cas, on vérifie alors qu'il n'appartient pas à la concavité BCD (ainsi qu'aux suivantes si plusieurs concavités existent).
Comme on le voit, la facilité et rapidité (algorithmique) à déterminer si M(x,y) appartient à un polygone quelconque du plan dépend beaucoup du prétraitement des données et donc surtout de la "forme" des polygones à considérer.
Dans le problème qui m'avait été soumis, les polynômes était nombreux et contenaient beaucoup de points (par rapport à ce que pouvait traiter le système informatique utilisé à ce moment là). Mais par chance, ces polygones étaient les mêmes (ou pratiquement) à détermination. Le temps passer à optimiser leur codage (et mémorisation) était rapidementamorti par le gain de temps à déterminer l'intériorité des nombreux et aléatoires points M.
Par contre, si les polygone à considérer à chaque détermination sont diffèrents, il faudra automatiser leur 'codage' et éventuellemetn faire appel à des notion plus générale de topologie, des triangularisation de Boris Delaunoy ou des réseaux de Voronoï.
Ensuite, ce n'est pas parce que tous les sommet M(n) d'un polygone sont à l'intérieur d'un polygone concave ABCD...XYZ que ce polygone M(n) est entièrement inclus dans le premier.
L'approche point par point n'est peut-être pas de ce type de cas la meilleure approche.
