Bonjour,
 
Voilà mon problème : j'ai un tableau contenant une liste de points représentés par des coordonnées GPS (latitude et longitude) :

$ArrayCoords = array(
                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
                              ...);

Cette liste de points forme un polygone, le dernier point dans mon tableau a les mêmes coordonnées que le premier. Je voudrais arriver à déterminer si les points sont donnés dans l'ordre horaire ou anti-horaire dans mon tableau.
Ca me paraît tout bête comme problématique mais je trouve pas le bon algo de détection
Attention, c'est pour tout type de polygone, même les plus biscornus...
 
Merci par avance.

Il est censé se passer quoi si ton polygone est concave?

Ben l'algo que je recherche doit gérer ce type de polygone. Et le premier point dans mon tableau peut être n'importe quel sommet du polygone (donc, ça peut être le point le plus au sud comme le plus au nord en terme de latitude, comme ça peut être le plus à l'ouest comme le plus à l'est en terme de longitude)...

Tu cherches l'enveloppe convexe des points avec l'Algorithme de Jarvis (ou algorithme du paquet cadeau)
 
Si les sommets de l'enveloppe sont dans l'ordre du tableau => sens horaire, sinon anti-horaire.
 

Il faut te placer à un changement de variation de ta position x ou y (x abscisse et y ordonnée, oui je ne sais plus comment fonctionnent les latitudes et longitudes). Donc suffit de vérifier :
tant que x+1>x, à ce moment là tu sais qu'à partir des prochains points tu vas avoir x qui va décroitre, il te suffit alors de comparer les valeurs de y pour savoir si c'est dans le sens horaire ou anti-horaire qu'on tourne.
 
Le tout étant de se placer à un changement de variation de x ou de y et de regarder si on va plus à droite (ou à gauche) ou plus en bas (ou en haut).
 
Après faut comprendre les coordonnées latitudes/longitudes pour pouvoir traduire ça en 2D (une projection suffit).

 
   
 
Il a dit tout type de polygone, même les plus biscornus

On peut pas juste regarder si le second point et à l'est et nord du premier point pour voir que c'est le sens horaire ?

EDIT : ceci est une réponse à totoche et non à jovalise.
 
Oui pas faux, je viens de penser que certains peuvent avoir un changement de concavité localement. Et autrement si on part sur des points cardinaux on doit pouvoir obtenir des choses non?
 
Ex : on se place sur le pt le plus haut, est-ce que le précédent était plus à gauche que celui qui suit le pt le plus haut?

Tout à fait, la méthode proposée par MaybeEijOrNot est celle sur laquelle j'étais parti (pas la même mais dans le même style), mais ça marche pas à tout les coup quand on a un polygone qui a des parties convexes ET des parties concaves
 
L'algo de la marche de Jarvis m'a l'air pas mal du tout. C'est marrant, pendant que vous répondiez à mon topic, j'étudiais une autre piste à base de directions NO, SO, SE, NE et des règles de réduction de ces directions (ex : SO, SE, SO => SO ou encore SE* => SE). Ca a l'air pour l'instant de marcher pas trop mal... Je vous tiens au courant.
 
En tout cas merci, j'aurais appris un nouvel algo aujourd'hui

 
Non parce que déjà on est sur un point au hasard, du coup si on est tout au sud alors le point suivant dans le sens horaire est à l'ouest et plus au nord.
 
 
Ma solution semble marcher, sauf que tu es obligé de parcourir tout ton tableau pour trouver un point cardinal (et non juste max local) et du coup ça doit surement revenir au même que l'enrobage.

C'est ce que j'avais fait au début, mais c'est pas suffisant dans le cas de polygones biscornus

 
Pas sûr que ta solution fonctionne dans le cas d'un polygone qui aurait la forme d'un C, par ex...

 
Non, c'est facile de trouver un cas où ça va foirer

Je ne vois pas de contre-exemple, dans le cas du C, le plus haut point possède un point à gauche quasiment au même niveau et un point à droite toujours au quasi-même niveau.

Autre point aussi, attention si l'un des poles (Nord ou Sud) est situé à l'intérieur de ton polygone, tu risques d'avoir des surprises si le cas n'est pas bien géré.
 
   

Y a pas une solution en regardant si un point donné est à l'intérieur ou à l'extérieur du polygone ?
 
Si non pas le savoir à l'avance ?
Et c'est pour faire quoi ?

Tu parlais d'un cas où ma solution ne fonctionnait pas, mais à part les polygones avec croisements je ne vois pas. Et je ne sais pas si on peut parler de sens horaire et anti-horaire dans un polygone croisé. En effet dans ce cas là le sens ne dépend que du point de départ et du point qui le suit.

C'est bon, mon pb semble résolu. Je suis finalement resté sur mon algo des directions NE, NO, SE, SO avec des règles de réductions appliquées récursivement jusqu'à avoir une chaîne de directions sur laquelle plus aucune règle de réduction ne peut s'appliquer. En général, j'arrive soit à une chaîne SONONESE (sens horaire) ou l'une de ses combinaisons cycliques (genre NONESESO) soit à une chaîne NOSOSENE (sens anti-horaire) ou l'une de ses combinaisons cyclique.

Pourquoi Jovalise il répond toujours en même temps que moi?

Ma contrainte est que je dois déterminer le sens à partir du premier point dans mon tableau (et des suivants) et non d'un point de mon tableau choisi d'une manière particulière. En effet, certains de mes points sont parfois des instructions du genre "arc de cercle ayant tel centre et tel rayon"... Au moment où je dois effectuer cette détermination de sens, je n'ai donc pas tous les points de mon polygone.

Si tu n'as pas tous les points tu ne peux pas définir le sens, si tu commences dans une concavité locale et que tu finies toujours dedans tu auras le mauvais sens. :s
 
Imagine un polygone qui ressemble à un croissant de lune C. Si tu commences par le haut du croissant en allant vers le droite tu es concave, en descendant tu iras vers la gauche ce qui te donnera l'impression de travailler dans le sens anti-horaire alors que tu travailles dans le sens horaire. Donc si tu n'as que la moitié des points tu te plantes. :s

En fait non, car c'est justement pour savoir comment récupérer les points manquants que je dois déterminer le sens de parcours des points de mon tableau (oui, je sais, ça a l'air bien tordu mon pb ).
 
Mais comme je le disais hier, je pense avoir résolu mon pb. J'ai pratiqué des tests et ça semble concluant.
 
Merci en tout cas pour vos idées

Ah ok, dans ce cas là travaille plutôt sur la convexité/concavité locale : tu fit un arc de cercle sur tes x points précédents dans le tableau, une fois fité tu regardes à quelles coordonnées retombent ton premier point et ton dernier et tu obtiens le sens.
C'est lourd (faire varier la position du centre et la taille du rayon), mais l'avantage c'est que tu peux réutiliser ton modèle fité pour tracer ta partie manquante.
Tu pourrais même travailler avec un ovale mais là ça sera encore pire niveau perfs.

Après pour améliorer les perfs du traitement tu peux découper tes points précédents par 3 points, 3 points => un cercle => résolution équation (http://math.15873.pagesperso-orange.fr/Cercl3p.html), tu calcules un point au milieu de l'arc et ça te fait plus qu'un point au lieu de trois. Tu peux avancer comme ça, après j'ai du mal à me représenter le résultat final mais ça devrait être pas trop mal.

Je n'ai pas de pbs de perfs, mon nb de points dépasse pas la vingtaine.

Non je parlais dans le cas où tu fais un fit car là en fonction de la précision choisie tu peux bouffer énormément.