Polygones
Description
Voici un petit ensemble de routines qui permet une familiarisation avec les polygones.
Les polygones sont souvent donnés sous la forme d'un array (vecteur) de points ou de deux arrays de coordonnées.
Ces deux types de "structures" sont utilisés pour calculer l'aire et le "centre de gravité" ainsi que pour déterminer si un point se trouve à l'intérieur.
Un exemple d'utilisation de Polygone.h Polygone.cpp, basé sur Windows GDI, se trouve dans WinMain.cpp.
J'ai aussi ajouté un code pour définir un polygone en forme de "spirale" qui permet de tester les routines de remplissage et du point intérieur d'un polygone quelconque.
Wikipédia donne la définition suivante: Polygone
Et les calculs de l'aire et du centre de gravité (ou de masse) correspondent à:
Aire et centre de masse d'un polygone.
La méthode utilisée compte le nombre de fois que le pourtour du polygone traverse une demi-droite (imaginaire) issue de ce point.
Le point (X,Y) se trouve à l'intérieure si et seulement si ce nombre est impair.
Faites un petit dessin pour vous en convaincre.
Pour simplifier les formules, on choisit une demi-droite horizontale ou verticale (ici verticale: (X,Y)->(X,+∞)).
Pour chaque segment (u,v)->(x,y) du polygone, on teste d'abord s'il traverse la droite (complète) (X,-∞)->(X,+∞):
(u>X) != (x>X)
Puis, si oui, on regarde s'il la traverse du "bon" coté:
Y < (v + (X-u)*(y-v)/(x-u))
Plutôt que d'incrémenter un compteur, on inverse à chaque intersection une valeur booléenne initialisée à false.
Remarques:
a) Il existe des algorithmes plus simples et plus efficaces pour certaines surfaces particulières telles que rectangles, cercles, etc.
b) Dans bien des codes proposés, le test (u>X) != (x>X) est écrit sous la forme:
((u>X)&&(x<=X)) || ((u<=X)&&(x>X))
Savez-vous ou devinez-vous pourquoi ?
Rectangle englobant, périmètre, polygones avec "arrondis" et trous, centres quadratiques, sections (résistance des matériaux), triangulation, etc.
Dites-moi si l'un ou l'autre de ces domaines vous intéresse.
Les polygones sont souvent donnés sous la forme d'un array (vecteur) de points ou de deux arrays de coordonnées.
Ces deux types de "structures" sont utilisés pour calculer l'aire et le "centre de gravité" ainsi que pour déterminer si un point se trouve à l'intérieur.
Un exemple d'utilisation de Polygone.h Polygone.cpp, basé sur Windows GDI, se trouve dans WinMain.cpp.
J'ai aussi ajouté un code pour définir un polygone en forme de "spirale" qui permet de tester les routines de remplissage et du point intérieur d'un polygone quelconque.
Définition et calculs
Wikipédia donne la définition suivante: Polygone
Et les calculs de l'aire et du centre de gravité (ou de masse) correspondent à:
Aire et centre de masse d'un polygone.
Point à l'intérieur d'un polygone
La méthode utilisée compte le nombre de fois que le pourtour du polygone traverse une demi-droite (imaginaire) issue de ce point.
Le point (X,Y) se trouve à l'intérieure si et seulement si ce nombre est impair.
Faites un petit dessin pour vous en convaincre.
Pour simplifier les formules, on choisit une demi-droite horizontale ou verticale (ici verticale: (X,Y)->(X,+∞)).
Pour chaque segment (u,v)->(x,y) du polygone, on teste d'abord s'il traverse la droite (complète) (X,-∞)->(X,+∞):
(u>X) != (x>X)
Puis, si oui, on regarde s'il la traverse du "bon" coté:
Y < (v + (X-u)*(y-v)/(x-u))
Plutôt que d'incrémenter un compteur, on inverse à chaque intersection une valeur booléenne initialisée à false.
Remarques:
a) Il existe des algorithmes plus simples et plus efficaces pour certaines surfaces particulières telles que rectangles, cercles, etc.
b) Dans bien des codes proposés, le test (u>X) != (x>X) est écrit sous la forme:
((u>X)&&(x<=X)) || ((u<=X)&&(x>X))
Savez-vous ou devinez-vous pourquoi ?
Sujets non traités
Rectangle englobant, périmètre, polygones avec "arrondis" et trous, centres quadratiques, sections (résistance des matériaux), triangulation, etc.
Dites-moi si l'un ou l'autre de ces domaines vous intéresse.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.