ANNEXE A
CRITERES GEOMETRIQUES |
|
ANNEXE A
CRITERES GEOMETRIQUES |
Le but de cette partie est de décrire la résolution de problèmes simples de géométrie plane, qui sont souvent utilisés par les algorithmes de triangulation.
1 - POSITION D’UN POINT PAR RAPPORT A UNE DROITE
Problème : Déterminer si un point A se situe d’un coté, de l’autre, ou sur une droite donnée, repérée par deux de ses points B1 et B2.
Figure A. 1: position d'un point parapport à une droite.
Méthode : Etudier le signe du déterminant B1A^B1B2 comme critère de l’orientation de l’angle entre ces deux vecteurs.
Solution : renvoyer le signe de 
.
Le côté (A ,(B1 , B2)) = signe (Dét (A-B1 , B2-B1))
Remarque : Ce signe est fonction du fait que le système de coordonnées (x,y) est direct ou indirect.
2 - INTERSECTION DE DEUX SEGMENTS
Problème :Déterminer si deux segments [A1,A2] et [B1,B2] ont une intersection vide ou non.
Figure A. 2: intersection entre deux segments.
Méthode : On vérifie que les points A1 et A2 sont de part et d’autre de la droite (B1B2) et que les points B1 et B2 sont de part et d’autre de la droite (A1A2).
Solution :
Intersect ((A1,A2), (B1,B2)) = Max ((Côté (A1, (B1,B2)* Côté (A2, (B1,B2), Côté (B1, (A1,A2))* Côté (B2, (A1,A2)).
Remarque : On peut, en considérant de plus prés les cas d’égalité à 0, spécifier les cas d’intersection sur les extrémités des segments.
3 – POSITIONS RELATIVES DE TROIS DEMI-DROITES AUTOUR D’UN POINT
Problème : Déterminer l’ordre cyclique, depuis une origine, des trois demi-droites infinies [OA), [OB) et [OC) autour de leur origine commune O.
Figure A. 3: positions relatives de trois demi-droites
Méthode :Etudier le signe des angles entre ces trois demi-droites par l’intermédiaire des déterminants OA^OB, OB^OC et OA^OC.
Solution : Si les deux premiers déterminants sont de même signe, il n’y a pas d’ambiguïté, sinon on choisit le signe en fonction du dernier.
DtA = Signe (Dét (AO, BO)) ;
DtB = Signe (Dét (BO, CO)) ;
DtC = Signe (Dét (AO, CO)) ;
Si (DtB = 0) Alors Sect (O, (A, B, C))=Signe (DtA+DtC)
sinon Sect (O, (A, B, C)) =Signe(DtB*Min(DtB*DtA, DtB*DtC))
Remarque : comme précédemment, les cas d’égalité à 0 traduisent des demi-droites confondues.
Problème :Déterminer le barycentre d’un triangle quelconque dans le but de le partitionner en trois autres triangles.
Figure A. 4 : Barycentre d'un
Méthode : Calculer les coordonnées du barycentre (nouveau point D).
Solution : 
Remarque :Le barycentre n’est calculé que si la variance et la surface du triangle sont supérieures à des seuils donnés.
La variance d’un triangle (bloc de l’image) est donnée par :
où : m : taille du bloc (nombre de pixels), xi :valeur du niveau de gris du pixel i, et moy :est la moyenne des niveaux de gris dans le bloc.
© 1999, KADDOUR Chakib
| Réactions ? Commentaires ? Suggestions ?
Cliquez Ici
|