Caractérisation de l'intérieur d'un polygone
Y. Morel
Introduction
Déterminer la présence d'une région commune à deux objets est un problème de base et maintenant classique. Un cas particuier de ce problème, et une manière d'aborder le problème plus général, est le problème de l'appartenance d'un point à un objet ou à un lieu géométrique.
Ce problème est assez courant en informatique, en infographie, pour colorer une zone géométrique, tester si un trajet passe par une région géographique donnée, effacer (ou ne pas charger en mémoire) des zones non visibles, ou encore en robotique: par exemple la détection d'une collision.
On s'intéresse assez naturellement dans un contexte informatique à des polygones. Un polygone est une figure géométrique plane définie par une ligne brisée fermée: un polygone se défini comme un ensemble de points, ses sommets.
Le cas de régions, ou ensembles, définis paramétriquement est aussi possible; on peut par exemple découper en sous-régions celles-ci et les approximer par des polygones avec un nombre de sommets d'autant plus grand qu'une grande précision est souhaitée.
On commence par différencier les cas de figure polygonale et la terminologie mathématique.
Ensemble convexe
Un ensemble géométrique E est dit convexe lorsque pour tout couple de points A et B de cet ensemble, le segment [AB] est entièrement inclus dans l'ensemble E:
∀(A, B)∈E2, [AB]⊂E
Exemple d'un ensemble convexe:
![\[\begin{pspicture}(-.3,-2.2)(5.3,3.4)
\pscustom{
\pscurve(0,0)(2,3)(4,3)(5,0)(3,-2)(0,0)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
\psline[linewidth=.2em,linecolor=blue](1,.7)(4,2)
\rput(1,1){\blue$A$}
\rput(4,2.3){\blue$B$}
\end{pspicture}\]](IMG/7.png)
Exemple d'un ensemble non convexe:
![\[\begin{pspicture}(-3.2,-2.2)(5.8,2.8)
\pscustom{
\pscurve(-3,-1)(2,2.5)(4,2.5)(5,-2)(2,1)(-1,-2)(-2.9,-1.2)(-3,-1)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
\psline[linewidth=.2em,linecolor=blue](-.3,.7)(4,0)
\rput(-.3,1){\blue$A$}
\rput(4,.3){\blue$B$}
\end{pspicture}\]](IMG/8.png)
Polygone convexe
Pour savoir si un polygone est convexe, il suffit de tester ses diagonales, c'est-à-dire les segments formés par des couples de sommets non voisins:Cas d'un polygone convexe:
(2,3)(6,3)(5.5,.5)(3,-2)
\rput(-.2,0){\blue$A$}
\rput(2,3.2){\red$B$}
\rput(6,3.2){\blue$C$}
\rput(5.7,.5){\green$D$}
\rput(3,-2.3){\yellow$E$}
\psline[linewidth=.2em,linecolor=blue](0,0)(6,3)
\psline[linewidth=.2em,linecolor=blue](0,0)(5.5,.5)
\psline[linewidth=.2em,linecolor=red](2,3)(3,-2)
\psline[linewidth=.2em,linecolor=red](2,3)(5.5,.5)
\psline[linewidth=.2em,linecolor=green](5.5,.6)(0,0.1)
\psline[linewidth=.2em,linecolor=green](5.5,.6)(2,3.1)
\psline[linewidth=.2em,linecolor=yellow](2.9,-2)(1.9,3)
\psline[linewidth=.2em,linecolor=yellow](3.1,-2)(6.1,3)
\end{pspicture}\]](IMG/9.png)
ou non convexe:
(2,3)(4,3)(5,-2)(2,1)
\rput(-3.2,-1,.7){\blue$A$}
\rput(2,3.2,-.2){\red$B$}
\rput(4.1,3.2){\blue$C$}
\rput(5,-2.3){\green$D$}
\rput(1.95,.6){\yellow$E$}
\psline[linewidth=.2em,linecolor=blue](-3,-1)(4,3)
\psline[linewidth=.2em,linecolor=blue](-3,-1)(5,-2)
\end{pspicture}\]](IMG/10.png)
Ici la diagonale [AD] n'est pas incluse dans E, [AD]⊄E, et donc E n'est pas convexe.
Il y a dans un polygone à n côtés, n(n−3)2 diagonales.
Par contre, pour savoir si une diagonale est entièrement incluse dans le polygone, c'est-à-dire si tous les points du segment appartiennent aussi au polygone, il faut être capable de distinguer un point intérieur au polygone, et un point extérieur à celui-ci. Ceci est présenté plus bas.
Triangle
Un triangle est un polygone toujours convexe. Il est facile dans ce cas de tester l'appartenance ou non d'un point.(2,3)(4,1)
\rput(-.2,-.2){$A$}
\rput(2,3.2){$C$}
\rput(4.2,1){$B$}
\rput(2.6,1.5){\large$\tm$}\rput(2.7,1.2){$M$}
\end{pspicture}\]](IMG/17.png)
En effet, en considérant M comme le barycentre des sommets A, B et C, on a
M = αA + βB + γCα + β + γ
et M appartient au triangle si et seulement si
0≤ α, β, γ ≤1.
Pour trouver ces coefficients, il suffit de trouver t et t' tels que AM = t AB + t' AC qui existent et sont uniques dès que A, B et C ne sont pas alignés, ce qui se réécrit en géométrie affine:
AM = t AB + t' AC
⇔
M−A = t(B−A) + t'(C−A)
⇔
M = (1 − t −t')A + tB + t'C
qui est la relation barycentrique précédente avec
α = 1 − t −t' et
β = t et
γ = t'.
Un point M intérieur du triangle vérifie alors 0 ≤ 1 − t −t' ≤1 ⇔ 0 ≤ t + t' ≤1 et 0 ≤ t ≤ 1 et 0 ≤ t' ≤ 1.
L'algorithme peut alors simplement s'écrire:
Calculer t et t' solutions du système:Si (0 ≤ t ≤ 1) & (0 ≤ t' ≤ 1) & (t+t' ≤ 1) alors M est à l'intérieur de ABC
![\[\la\begin{array}{lcl}
t(x_B-x_A)+t'(x_C-x_A)&=&x_M-x_A \\[.8em]
t(y_B-y_A)+t'(y_C-y_A)&=&y_M-y_A
\enar\right.\]](IMG/39.png)
Les cas d'un polygone convexe peut alors se ramener à celui de triangles, en considérant les sommets par triplets.
Par exemple, pour le polygone ABCDE, on découpe en ABC, ACD, ADE:
(2,3)(6,3)(5.5,.5)(3,-2)
\rput(-.2,0){$A$}
\rput(2,3.2){$B$}
\rput(6,3.2){$C$}
\rput(5.7,.5){$D$}
\rput(3,-2.3){$E$}
\pspolygon[fillstyle=solid,fillcolor=blue](0,0)(2,3)(6,3)
\pspolygon[fillstyle=solid,fillcolor=yellow](0,0)(6,3)(5.5,.5)(3,-2)
\pspolygon[fillstyle=solid,fillcolor=green](0,0)(5.5,.5)(3,-2)
\end{pspicture}\]](IMG/46.png)
Ensemble connexe
Un ensemble est connexe lorsqu'il ne peut s'écrire comme la réunion de deux sous-ensemble disjoints, ouverts ou fermés tous les deux.
En d'autres termes, un ensemble connexe est un ensemble en un seul morceau.
![\[\begin{pspicture}(-.3,-2.2)(5.3,3.4)
\pscustom{
\pscurve(0,0)(2,3)(4,3)(5,0)(3,-2)(0,0)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
\end{pspicture}\]](IMG/47.png)
Un ensemble non connexe est donc un ensemble en plusieurs morceaux, mathématiquement, qui peut s'écrire comme la réunion de sous-ensembles fermés, ou tous ouverts, et disjoints, comme cet exemple d'ensemble à deux composantes dijointes:
![\[\begin{pspicture}(-.3,-2.5)(5.3,3.4)
% 1ère composante
\pscustom{
\pscurve(0,0)(2,3)(4.5,3)(3,1.2)(0,0)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
% 2ème composante
\pscustom{
\pscurve(2,0)(3,-.2)(4,-1)(3,-1.5)(2,-2.2)(2,0)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
\end{pspicture}\]](IMG/48.png)
Pour traîter le cas d'ensembles non connexes, il suffit de traîter le problème sur chaque composante connexe de l'ensemble.
Lorsqu'on utilise des polygones, la question ne se pose pas vraiment; on définit en effet un polygone comme une suite de points. Par définition ainsi on se trouve naturellement sur des parties polygonales connexes.
Il est aussi important de prendre en compte la présence d'éventuels "trous". On parle de simple connexité, ou non.
Simple connexité
Schématiquement, un ensemble simplement connexe est un ensemble en un seul morceau et sans trou.
Par exemple, l'ensemble suivant est connexe, mais pas simplement connexe.
![\[\begin{pspicture}(1.7,.8)(4,3)
\pscustom{
\pscurve(2,3)(3,2.8)(4,2)(3,1.5)(2,.8)(2,3)\gsave
\fill[fillstyle=solid,fillcolor=lightgray]
\grestore
}
\pscircle[fillstyle=solid,fillcolor=white](2.8,2){.3}
\end{pspicture}\]](IMG/49.png)
La définition mathématique de la simple connexité est bien sûr plus précise, et plus complexe.
On définit pour cela la notion de chemin entre deux points A et B qui correspond à l'idée largement imagée d'un ensemble de points reliant continûment les extrémités A et B.
On définit alors directement la notion de lacet: c'est "une boucle", c'est-à-dire un chemin pour lequel A = B.
On étudie alors les déformations possible de ces chemins ou lacets. On appelle dan ce cadre homotopie, une transformation continue d'un chemin ou lacet en un autre.
On peut alors arriver à la définition précise: un ensemble est simplement connexe si tous ses lacets sont homotopes à un point.
En d'autres termes, un ensemble est simplement connexe si toute boucle (ou lacet) peut se rétracter continûment, et en restant dans l'ensemble, en un point.
Ce n'est pas le cas lorsqu'il y a un trou comme l'exemple précédent.
Point intérieur à un polygone
Il existe de multiples méthodes et algorithmes pout tester l'appartenance d'un point d'un point à un polygone, c'est-à-dire pour déterminer si le point est à l'intérieur du polygone.
La méthode choisie dépend principalement du type de polygone choisi: par exemple si on sait qu'il est convexe, on peut le subiviser en triangle et utiliser les coordonnées barycentriques. Par contre si on ne sait pas a priori...
Dans le cas le plus général, c'est-à-dire pour donner un algorithme permettant de traîter indifférement tous les cas de figure, on peut utiliser une méthode basée sur des rayons et des calculs d'intersection entre rayon et côtés du polygone.
Cette méthode de "raycasting", ou "ray tracing" est une des plus simple et plus générale; elle est à la base, entre autre, d'algorithmes de rendu graphique dans les jeux DOOM et Wolfenstein.
Elle est aussi implémentée dans la bibliothèque Libxy...
Description de la méthode
On se donne un point R extérieur au polygone. En pratique, il suffit de déterminer une "bounding box", c'est-à-dire un rectangle minimal contenant le polygone, et un point R extérieur à ce rectangle.
Ensuite, pour un point M donné, on considère le rayon [RM] et on compte son nombre d'intersection avec les côtés du polygone; si ce nombre est impair, le point M est à l'intérieur, sinon il est à l'extérieur.
Par exemple, dans la figure suivante, pour les points M1, M3 et M5, les nombres d'intersection sont respectivement 1, 3 et 5 et ces points sont bien à l'intérieur, tandis que les nombre d'intersection pour les points M0, M2, M4 et M6 sont respectivement de 0, 2, 4 et 6 et ces points sont extérieurs.
(3,3)(5,4)(9.5,1.5)(8.5,-2)(7,-2)(6,1)(5,-1)(4,2)(2,0)
\pspolygon[fillstyle=solid,fillcolor=white](8.2,.2)(8.5,-1.3)(7.3,-1.3)
\rput(.8,.8){$A$}
\rput(2.6,2.9){$B$}
\rput(4.8,4.2){$C$}
\rput(9.7,1.7){$D$}
\rput(8.7,-2.1){$E$}
\rput(6.7,-2.1){$F$}
\rput(6,1.3){$G$}
\rput(4.8,-1.2){$H$}
\rput(4,2.3){$I$}
\rput(2.1,-.2){$J$}
%
\rput(8.2,.5){$K$}
\rput(8.4,-1.55){$L$}
\rput(7.35,-1.55){$M$}
%
\rput(-1,1.8){\large$\tm$}\rput(-1,2.1){$R$}
\psline[linewidth=1.5pt,arrowsize=8.5pt,linecolor=blue]{->}(-1,1.8)(9.6,-1.1)
\rput(0,1.5){\large$\tm$}\rput(0,1.8){$M_0$}
\rput(1.8,1.03){\large$\tm$}\rput(1.9,1.3){$M_1$}
\rput(3.8,.48){\large$\tm$}\rput(3.9,.8){$M_2$}
\rput(5,.18){\large$\tm$}\rput(5,.5){$M_3$}
\rput(6,-.12){\large$\tm$}\rput(5.9,-.45){$M_4$}
\rput(7,-.4){\large$\tm$}\rput(7,-.1){$M_5$}
\rput(8,-.65){\large$\tm$}\rput(8,-1){$M_6$}
\end{pspicture}\]](IMG/67.png)
En pratique, il reste à déterminer l'intersection, si elle existe, entre deux segments.
Calculs et algorithme
Le point source R( xR ; yR) est supposé connu; le point M( xM ; yM) désigne le point dont on veut tester l'appartenance au polygone.On considère ensuite chaque couple de sommets consécutifs, par exemple A( xA ; yA) et B( xB ; yB) pour commencer.
Il est facile de déterminer le point I, s'il existe, à l'intersection des droites (RM) et (AB).
Il faut ensuite déterminer si ce point I d'intersection appartient bien au deux segments: I∈[RM] et I∈[AB].
Une manière simple et efficace de vérifier cela est de calculer les produits scalaires et de vérifier simultanément:
AI . BI < 0
RI . MI < 0
On peut faciliter, et donc accélerer les calculs on ne considérant, par exemple, que des rayons verticaux: l'intersection est plus simple et plus rapide (nécessite moins de calculs) à déterminer; on peut de plus éviter très simplement le cas où le rayon est parallèle à un côté (cas yA = yB).
Algorithme
On suppose que les sommets du polygone à n côtés sont {Ai(xi, yi) ; 1≤i≤n}, avec la fermeture An+1 = A1
On teste le point M(x ; y):
ymax=max{ yi; 1≤i≤n }
R=(x;ymax+1)
cpt=0
Pour i de 1 à n
Si xi≠xi+1
m=(yi+1-yi)/(xi+1-xi)
p=yi-m*xi
xI=x
yI=m*x+p
Fin
Si ((xI-xi)*(xI-xi+1})<0 & (yI-yR)*(y-yI)<0)
cpt=cpt+1
Fin
Si (cpt est pair): M est à l'intérieur
Sinon: M est à l'extérieur
Masquage par les sommets / rayons tangents
Cette méthode a à la fois l'avantage d'être simple à mettre en œuvre, et relativement rapide et efficace. D'autres algorithmes plus évolués, et complexes donc, existent pour optimiser cette fonction.
L'alignement avec les sommets du polygone n'est pas traîté dans l'algorithme précédent, c'est-à-dire le cas où le point d'intersection I est un sommet du polygone.
Dans ce cas cette intersection est décomptée deux fois, une pour chaque côté du polygone contenant ce sommet. C'est une de trop, et tous les points alignés avec un sommet, ou plus, sont erronés.
![\[\begin{pspicture}(0,-1.4)(6,4.5)
\pspolygon(1,1)(3,3)(5.5,2)(4,-.5)(2,-.5)
\rput(.75,1.25){$A_1$}
\rput(.8,.9){$=$}
\rput(.75,.6){$A_6$}
\rput(2.7,3.1){$A_2$}
\rput(5.7,2){$A_3$}
\rput(4.2,-.7){$A_4$}
\rput(2,-.8){$A_5$}
\psline[linewidth=1.6pt,linecolor=blue,arrowsize=8pt]{->}(3,4)(3,.5)
\rput(3,4){$\tm$}\rput(3.2,4.2){$R_1$}
\rput(3,.5){$\tm$}\rput(3.2,.4){$M_1$}
\psline[linewidth=1.6pt,linecolor=blue,arrowsize=8pt]{->}(5.5,4)(5.5,0)
\rput(5.5,4){$\tm$}\rput(5.7,4.2){$R_2$}
\rput(5.5,0){$\tm$}\rput(5.7,-.1){$M_2$}
\end{pspicture}\]](IMG/86.png)
L'algorithme précédent détectera le point M1 comme étant à l'extérieur.
Par ailleurs, si on corrige l'algorithme en traîtant différemment l'intersection avec un sommet, ne comptant que pour une fois l'intersection précédente, alors dans l'exemple précédent, le point M2 sera compté comme M1, et sera alors à son tour mal situé.
Il faut donc tester l'alignement avec un sommet et, si c'est le cas, choisir une autre source R' pour le rayon, par exemple un point R' cette fois tel que (R'M) est horizontal qui ne peuvent donc pas être alignés avec le sommet précédent.
En d'autres termes plus imagés, si des zones sont masquées derrière un sommet, il n'y a qu'à se déplacer un peu, tourner autour de l'objet, pour avoir un autre point de vue...
![\[\begin{pspicture}(0,-1.4)(6,4.5)
\pspolygon(1,1)(3,3)(5.5,2)(4,-.5)(2,-.5)
\rput(.75,1.25){$A_1$}
\rput(.8,.9){$=$}
\rput(.75,.6){$A_6$}
\rput(2.7,3.1){$A_2$}
\rput(5.7,2){$A_3$}
\rput(4.2,-.7){$A_4$}
\rput(2,-.8){$A_5$}
\psline[linewidth=1.6pt,linecolor=blue,arrowsize=8pt]{->}(3,4)(3,.5)
\rput(3,4){$\tm$}\rput(3.2,4.2){$R_1$}
\rput(3,.5){$\tm$}\rput(3.2,.4){$M_1$}
\psline[linewidth=1.6pt,linecolor=blue,arrowsize=8pt]{->}(5.5,4)(5.5,0)
\rput(5.5,4){$\tm$}\rput(5.7,4.2){$R_2$}
\rput(5.5,0){$\tm$}\rput(5.7,-.1){$M_2$}
% Correction
\psline[linewidth=1.6pt,linecolor=red,arrowsize=8pt]{->}(-1,.5)(3,.5)
\rput(-1,.5){$\tm$}\rput(-1.3,.8){$R_1'$}
\psline[linewidth=1.6pt,linecolor=red,arrowsize=8pt]{->}(-1,0)(5.5,0)
\rput(-1,0){$\tm$}\rput(-1.3,-.2){$R_2'$}
\end{pspicture}\]](IMG/93.png)
Alternative pour le coloriage de l'intérieur
Si l'objectif est le simple coloriage de la surface intérieur, et non pas une détection, évitement de colision, ... c'est-à-dire si la finalité est uniquement esthétique, on peut s'arranger simplement.
On conserve l'algorithme précédent dans lequel on teste l'alignement de la source R, du point testé M et des sommets du polygone. Les calculs sont déjà faits en fait, car si il y a un tel alignement, le point I est justement un des sommets. Enfin, si on est un tel cas d'alignement, on considère directement et simplement le point comme extérieur.
On colorie correctement l'intérieur néanmoins en marquant chaque point, ou pixel, considéré comme intérieur par un carré de 2 pixels sur 2.
Les points intérieurs masqués par les sommets sont donc marqués par leur voisins.