Masqué par Le Nain
La surface des polygones
Comment créer un algorithme permettant de déterminer la surface d'un polygone ?
Le problème exposé dans ce sujet a été résolu.
Salutations nobles Zestien-ne-s !
M'intéressant à la programmation en C, j'ai découvert la SDL et ses joies, et en voulant représenter des polygones à l'écran, je me suis légitimement posé cette question : comment ?
Il se trouve que j'ai réglé mon problème de code en utilisant une librairie graphique d'un niveau un peu plus élevé (Allegro), mais cette question finalement très mathématique m'a angoissé, et je me la pose toujours :
Comment peut-on déterminer si un point dont on connaît les coordonnées (x,y) est à l'intérieur d'un polygone ?
Je précise ce qu'on sait sur le polygone : on a son ordre (c'est à dire son nombre de points) les coordonnées de chacun de ces points, et l'ordre dans lequel il faut les relier (parce qu'en reliant différemment les points, le polygone est tout autre !). Tout ça stocké par exemple sous forme de liste chaînée, ou de tableau, et peu importe d'ailleurs.
J'ai beaucoup travaillé le problème, et je crois avoir une solution (qui soit un peu mieux que le "bah ça se voit sur la figure" 
). Toutefois elle me paraît un peu compliquée, et je pense qu'il y en a des plus simples. Si vous en voyez, n'hésitez pas à poster même des embryons de début de piste, ce sera toujours intéressant !
La solution :
On a donc un polygone quelconque. S'il est convexe, c'est très facile, il y a plusieurs façons de faire (notamment de manière assez élégante en définissant chaque point à l'intérieur du polygone comme un barycentre des sommets, je vous laisse regarder sur Wikipédia si vous êtes curieux). S'il n'est pas convexe… C'est plus délicat ! Voyez plutôt :
On va commencer par définir un sens de rotation. J'ai pris le sens trigonométrique.
Puis on va parcouri le polygone. À chaque sommet, on s'interroge : est-ce que je tourne à gauche ou à droite ? On signale tous les sommets anormaux. Avec le sens trigo, ce sont les sommets qui tournent à droite qu'il faut signaler.
On va ensuite surligner les côtés qui touchent ces sommets. On va les appeler "côtés concaves". Je sais, ce n'est pas très rigoureux de dire qu'un segment est concave, mais c'est pour une meilleure compréhension. On va aussi regrouper ces côtés concaves en "familles", comme marquée sur la figure. J'ai nommé les familles A et B, mais rien ne nous oblige à les nommer.
Enfin, et c'est peut-être l'étape la plus délicate à implémenter en programmation, on va marquer pour chaque côté si le polygone se trouve au-dessus ou en-dessous. J'avoue ne pas encore être sûr de savoir implémenter ça. On va appeler cette caractéristique la consigne du côté.
Voilà, notre travail sur le polygone est terminé ! Nous sommes maintenant prêts à résoudre le problème initial ! Un point est-il, oui ou non, à l'intérieur du polygone ?
Accrochez-vous, ça a l'air compliqué mais c'est très simple : on étudie tous les côtés à la verticale de ce point. S'ils ne sont pas surlignés (côtés "convexes"), alors leur consigne doit être respectée. S'ils sont "concaves", alors il suffit que la consigne d'un seul par famille soit respectée. Une image vaut mieux qu'un long dicours :
Ici, il n'y a à la verticale du point que des côtés convexes, leur consigne doit être respectée. C'est le cas. Le point est bien à la surface du polygone.
Ici, la consigne des côtés convexes est repectée, et une consigne seulement de la famille A est respectée. Ça suffit pour que le point soit à la surface du polygone.
La famille A n'aime pas beaucoup qu'on ne respecte aucune de ses consignes ! Ce point est à l'extérieur.
Aïe ! Deux familles ! Pas de panique, on reprend tranquillement. Côtés convexes : OK. Famille A : OK. Famille B : OK. Ce n'était pas si dur que ça !
J'espère que ça vous inspirera. J'ajoute qu'on n'a aucunement résolu le problème des polygones croisés, je laisse un meilleur cerveau s'en charger .
PS : Désolé pour le double-post, une mauvaise manip pendant que je rédigeais…
+1
-0
Solution un peu plus simple (mais tu y es presque), qui fonctionne également pour les polygones croisés.
+3
-0
Bon sang mais c'est bien sûr. C'est même extrêmement logique.
Pour les non-anglophones qui seraient intéressés par la solution : le principe est semblable, mais on s'embête pas à repérer les "côtés concaves", les familles, les consignes… On trace juste la droite verticale passant par le point (comme je le faisais), et on compte le nombre de côtés qu'elle coupe. Il doit y en avoir un nombre impair au-dessus du point, et un nombre impair en-dessous du point pour que le point appartienne au polygone (sur le lien de Höd, on tarce la droite horizontale et non verticale, mais cela revient bien évidemment au même).
Merci !
+2
-0
De rien ! Ton idée était la bonne, il suffisait simplement de la reformuler pour obtenir un procédé plus simple ! Souvent les idées les plus simples sont les meilleures, encore faut-il fait apparaître la simplicité. 
+1
-0
Connectez-vous pour pouvoir poster un message.
Connexion
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte