Solutions retenues et utilisées

Saisie des polygones par l'utilisateur

Il a été choisi de permettre à l'utilisateur de saisir lui-même ses polygones via une interface graphique crée sous OpenGL. L'utilisateur se sert de la souris pour entrer les sommets du polygone qui sont ensuite stockée dans un tableau. Quelques limites ont toutefois été précisées. Il est donc impossible d'entrer des polygones possédant des côtés s'entrecroisant. Pour empêcher cette saisie, nous avons implémenté un algorithme de calcul d'intersection. A chaque définition de nouveau segment, nous calculons l'équation de chaque droite affine correspondant aux côtés du polygone déjà créés. Nous appliquons à ces équations les deux sommets du nouveau segment que l'on désire créer. Si les signes de ces calculs sont identiques, nous pouvons conclure que le segment est entièrement du même côté du bord du polygone. Il n'y a donc pas d'intersection, on peut pas passer au bord du polygone suivant. Si les signes sont opposés, il y a un sommet de chaque côté du bord du polygone. Il est alors nécessaire que nous vérifions si l'intersection ce fait entre les deux extrémités du bord du polygone, ou au-delà. Pour cela nous calculons le point d'intersection, et nous regardons si celui-ci appartient au bord du segment ou non. Si la réponse est oui, le segment que l'on désirait créer est rejeté, sinon, il est validé.


Calcul de l'aire d'un polygone

Nous avons cherché et trouver un algorithme qui permet de calculer l'aire d'un polygone quelconque. Il est décrit à l'adresse suivante :
http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf

Nous avons utilisé cet algorithme car il est simple à implémenter et très performant. De plus, il permet de calculer de manière intuitive l'aire de n'importe quel polygone convexe ou non.

Calcul du point d'accroche du polygone

Le point d'accroche du polygone est le point le plus distant du centre de gravité. Pour calculer le centre de gravité, nous prenons la moyenne des coordonnées du polygone. Puis nous cherchons le point le plus distant en utilisant le théorème de pythagore. Enfin, nous effectuons une rotation du polygone autour de l'axe Oz pour que le segment formé par le point le plus distant et le barycentre soit sur l'axe Oy, afin que le point le plus distant soit le point d'accroche. Enfin nous changeons de repère afin d'avoir pour origine le coin haut gauche du rectangle englobant (Bounding Box).

Calcul du rectangle englobant

Une fois le polygone exprimé dans son nouveau repère, il suffit de trouver le X et le Y les plus grand du polygone pour en déduire la taille du rectangle englobant.

Pour le placement des polygones sur le portique

Un élément est :




Le problème peut se ramener alors à un problème récursif. Il faut composer un portique avec des polygones qui sont accrochés à un bras qui lui-même est accroché à un autre bras, etc. Deux étapes : Plusieurs dispositions pour les éléments sont possibles :


Pour savoir quelle est la disposition la moins consommatrice en terme de place, nous calculons l'aire des trois cas. Nous prenons la solution qui a l'aire la plus faible. (computeTwoElement () dans portique.cpp)

Divison d'un polygone en triangle

Pour pouvoir afficher des polygones concaves, qui ne sont pas gérés par OpenGL, nous avons mis au point un algorithme permettant de diviser n'importe quel polygone en triangles. Pour commencer cette division nous recherchons un sommet du polygone à partir du quel nous pouvons partir. Pour que ce sommet soit déclarer valide, il doit remplir deux critères. Le premier est que le segment reliant le sommet précédent, et le sommet suivant ne coupe aucun autre côté du polygone.



Le deuxième critère à vérifier, et que ce segment est à l'intérieur du polygone. Pour vérifier ce critère, nous prenons un point du segment à créer, arbitrairement, nous avons choisi de calculer le milieu. Puis nous traçons la demi droite horizontale partant de ce point. Il nous suffit alors de compter le nombre d'intersection de cette demi droite avec les bords du polygone. Si ce nombre est impair, le point est à l'intérieur, et par extension tout le segment. Si il est pair, le poinr est à l'extérieur et par extension tout le segment. Si il est nul, nous traçons la demi-droite partant vers l'autre côté du point, et nous recomptons les intersections.


Une fois que ce premier sommet à été défini, nous repartons du suivant, qui est lui-même extrémité du segment que l'on vient de créer. Nous recherchons le sommet le plus proche de lui. Puis nous vérifions que si l'on crée un segment reliant ces deux points, celui-ci sera valide, c'est à dire qu'il ne coupe aucun bord du polygone, qui l'est à l'intérieur, et qu'il ne coupe aucun autre triangle créé précedemment. Si c'est le cas, nous effectuons les mêmes vérifications entre ce point est l'autre extrémité du segment duquel on est parti. Si tous ces critères sont vérifiés, nous créons un nouveau triangle, sinon, nous passons au deuxième sommet le plus proche, et ainsi de suite. Si aucun sommet n'est trouvé, nous avons fini la division en triangle de la portion du polygone. Récursivement chaque parti du polygone est traitée de la même manière.



Retour
Gregory GARCIA
Patrice MARQUES
Romain MAURER