Discussion :

[cla_gnx]

bonjour,
J'ai un tableau de coordonnées géographiques qui représente un polygone.
Mon problème est que les coordonnées ne sont pas triés correctement et j'obtiens donc des polygones croisés.
Je voudrais ordonner ses coordonnées dans le sens horaire (ou anti horaire peu importe) pour pouvoir obtenir des polygones simples.

Merci d'avance !

[kevin254kl]

Bonjour, peux tu nous donner un exemple? quel est ton problème tu n'arrive pas à les trier avec la méthode sort?

[cla_gnx]

En gros j'ai différentes coordonées géographiques qui représente un polygone qui peut etre convexe ou concave ou de n'importe quelles forme mais je veux obtenir seulement un polygone simple et pas que des segments se croisent. Il faudrait donc que mes points soient ordonnées pour que les segments crées ne se croisent pas.
Mais une simple méthode sort ne peux pas marcher car mon polygone peut etre concave et donc cela complique plutot la chose... Je pense qu'il faut faire quelque chose en fonction des angles mais je n'arrive pas vraiment à trouver..

[wolinn]

La solution n'est pas unique en général...
Pour un ensemble de 5 points ou plus, il y a plusieurs polygones solutions possible. Est-ce que tu as des critères pour choisir la bonne solution ou est-ce que c'est sans importance ?

On peut partir d'une triangulation de l'ensemble de points (en général une fonction de base des librairies de géométrie, cf Delaunay) et supprimer les arêtes extérieures (en faisant attention de ne pas générer de rebroussements) jusqu'à ce qu'il n'y aie plus de points intérieurs.
Mais ce n'est pas particulièrement élégant, je pense qu'il y a des méthodes plus élémentaires.

[cla_gnx]

La solution n'est pas unique en général...
Pour un ensemble de 5 points ou plus, il y a plusieurs polygones solutions possible. Est-ce que tu as des critères pour choisir la bonne solution ou est-ce que c'est sans importance ?

Peut importe la forme du polygone tant qu'il n'est pas croisé !

[tatayo]

Bonjour,
Une idée serai de transformer les coordonnées géographiques en coordonnées polaires, puis de les trier par angle/distance.

Tatayo.

[Flodelarab]

Bonjour

Voici 5 points positionnés de la même manière. Mais les polygones sont bien différents géographiquement.


Je reste dubitatif sur le fait que l'ordre n'a pas d'importance.

[cla_gnx]

Une idée serai de transformer les coordonnées géographiques en coordonnées polaires, puis de les trier par angle/distance.

Oui c'est ce que j'ai essayé de faire..
J'ai calculé le milieu du polygone ( moyenne des coordonnées) puis pour chaque point je cherchais le point qui permettait d'avoir le plus petit angle avec le milieu. Ca marche pas trop mal, mais pas dans tous les cas malheureusement...

Voici 5 points positionnés de la même manière. Mais les polygones sont bien différents géographiquement.


Je reste dubitatif sur le fait que l'ordre n'a pas d'importance.

Justement, je dis que l'ordre des points est important
Et je veux justement reussir à ordonner mes points pour avoir un polygone simple et non croisé



Ce que je fais actuellement :
J'ai mon tableau de coordonées :coordtotale2 qui est une liste de tuples.
Je calcule le milieu avec la fonction :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
def calcul_milieu(coord):
	taille=len(coord)
	x=0
	y=0
	for coo in coord:
		x=x+coo[0]
		y=y+coo[1]
 
	x=x/taille
	y=y/taille
 
	return x,y

Je calcule mes angles avec la fonction :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def calcul_angle(coord1, coord2, milieu):
	distance1m=sqrt(((coord1[0]-milieu[0])*(coord1[0]-milieu[0]))+((coord1[1]-milieu[1])*(coord1[1]-milieu[1])))
	distance2m=sqrt(((coord2[0]-milieu[0])*(coord2[0]-milieu[0]))+((coord2[1]-milieu[1])*(coord2[1]-milieu[1])))
	distance12=sqrt(((coord2[0]-coord1[0])*(coord2[0]-coord1[0]))+((coord2[1]-coord1[1])*(coord2[1]-coord1[1])))
 
	angle=acos(((distance1m*distance1m)+(distance2m*distance2m)-(distance12*distance12))/(2*distance1m*distance2m))
 
	return angle

Et je récupere la coordonée de mon tableau qui creer l'angle le plus petit avec le milieu avec cette fonction :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
def return_index_coord_plus_petit_angle(coord1, coordtotale, milieu):
	minimum=10000
	num=-1
	for tmp in range(len(coordtotale)):
		if coordtotale[tmp] != coord1:
			angle=calcul_angle(coord1, coordtotale[tmp], milieu)
			if angle < minimum:
				minimum=angle
				num=tmp
 
 
	return coordtotale[num]

et du coup j'utilise mes fonctions :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x,y=calcul_milieu(coordtotale2)
milieu=(x,y)
 
tablecoord=[]
tablecoord.append(coordtotale2[0])
angle_utilise=coordtotale2[0]
coordtotale2.remove(angle_utilise)
while(coordtotale2):	
	print(angle_utilise)
	coordmin=return_index_coord_plus_petit_angle(angle_utilise, coordtotale2,milieu)
	tablecoord.append(coordmin)
	coordtotale2.remove(coordmin)
	angle_utilise=coordmin
 
#Je rajoute la premiere coordonées à la fin pour que le polygone soit fermé.
tablecoord.append(tablecoord[0])

[souviron34]

il y a plus simple pour l'angle :

la fonction atan2 qui donne l'angle par rapport à l'horizontale entre 0 et 2 PI.


2 manières de trier : par rapport au barycentre ou par rapport à une extrémité (par exemple le point le plus en bas à droite).


Mais, à moins que tu ne connaisses par avance le polygone, il n'y a pas de manière simple de déterminer le polygone à partir de ça, sauf si c'est l'enveloppe convexe (et alors la manière usuelle est de trier à partir d'une extrémité).