Eléments de calcul sur les polygones

Voici quelques algorithmes qui peuvent s'avérer pratiques lors de travaux en géomatique. tab représente de manière générale un tableau à 2 x (n+1) dimensions, contenant les coordonnées des n sommets d'un polygone. tab.x[i] désigne l'abscisse du i-ème sommet. Le premier élément (indice 1) du tableau et le dernier (indice n+1) sont identiques.

• Calcul de l'aire d'un polygone (Le résultat est positif si le polygone est décrit dans le sens trigonométrique, négatif sinon)

Aire = 0;
for i = 1..n do  {
	Aire = Aire + (tab.y[i+1]-tab.y[i]) * (tab.x[i+1]+tab.x[i]);
}
Aire = Aire/2;

• Coordonnées du centre de gravité (attention, l'algo fait appel à l'aire du polygone)

xg = 0;
yg = 0;
for i = 1..n do {
	xg = xg + (tab.y[i+1]-tab.y[i]) * ( tab.x[i+1]²+tab.x[i+1]*tab.x[i]+tab.x[i]²)
	yg = yg + (tab.x[i]-tab.x[i+1]) * ( tab.y[i+1]²+tab.y[i+1]*tab.y[i]+tab.y[i]²)
}
xg = xg/(6*Aire);       
yg = yg/(6*Aire);

• Savoir si un point est dans un polygone

Pour savoir si un point est dans un polygone, il suffit de tracer à partir de ce point un demi-droite et de compter le nombre d'intersections avec la frontière du polygone. Si le nombre d'intersections est pair alors le point est à l'extérieur du polygone, sinon il est à l'intérieur.

Le point isolé d'un polygone

L'idée est venue d'un problème de représentation cartographique des données. En effet, un des moyens existant, est de représenter une donnée statistique par un symbole qui lui est proportionnel, par exemple un cercle, et de le placer sur un polygone.

Pour placer le cercle il faut choisir un "bon" point à l'intérieur du polygone. On peut utiliser le centre de gravité , l'isobarycentre... Mais ces points ont des désavantages, par exemple un centre du cercle situé à l'extérieur du polygone n'est pas idéal pour la cartographie.

Pour définir un "bon" point il faudrait qu'il ait au moins ces propriétés :

• Etre dans le polygone;
• éviter tant que possible le recouvrement avec ses cercles voisins.

Formalisons le point ainsi :

Soit P un polygone et I le centre du plus grand cercle inscrit dans P (cercle pseudo-inscrit).

Voici un exemple qui illustre les avantages du point isolé et du gain de qualité en représentation :

Pour l'instant, j'ai fait un progamme qui permet de déterminer numériquement une solution, mais il s'agit d'une recherche exhaustive (c'est pas très joli). Si ça vous intéresse, contactez-moi. Si vous avez une solution élégente (une formulation analytique ?), ça m'intéresse, contactez-moi. La solution est liée au problème du tas de sable : le point est la projection orthogonale du sommet du tas de sable qui a pour base le polygone exactement.

Le code est sur le site ici : code source