Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1654 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [Résolu] Détecter le sens de parcours d'une liste de coordonnées

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Résolu] Détecter le sens de parcours d'une liste de coordonnées

n°2209407
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 14:59:10  profilanswer
 

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) :

Code :
  1. $ArrayCoords = array(
  2.                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
  3.                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
  4.                              array("Lat" => xx.zzzz, "Lng" => yy.zzzz),
  5.                              ...);


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.


Message édité par rufo le 07-11-2013 à 10:30:17

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
mood
Publicité
Posté le 06-11-2013 à 14:59:10  profilanswer
 

n°2209408
masklinn
í dag viðrar vel til loftárása
Posté le 06-11-2013 à 15:04:43  profilanswer
 

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


---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°2209410
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 15:12:53  profilanswer
 

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)...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209411
Totoche17
Posté le 06-11-2013 à 15:18:02  profilanswer
 


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.
 

n°2209428
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 16:06:31  profilanswer
 

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).

n°2209431
Totoche17
Posté le 06-11-2013 à 16:14:28  profilanswer
 

MaybeEijOrNot a écrit :

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).


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

n°2209432
Profil sup​primé
Posté le 06-11-2013 à 16:24:27  answer
 

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 ?

n°2209433
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 16:27:45  profilanswer
 

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?

Message cité 2 fois
Message édité par MaybeEijOrNot le 06-11-2013 à 16:32:35
n°2209434
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 16:30:47  profilanswer
 

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 :jap:


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209435
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 16:31:19  profilanswer
 


 
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.

mood
Publicité
Posté le 06-11-2013 à 16:31:19  profilanswer
 

n°2209436
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 16:31:47  profilanswer
 


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


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209438
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 16:33:12  profilanswer
 

MaybeEijOrNot a écrit :


 
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.


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


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209439
Totoche17
Posté le 06-11-2013 à 16:34:57  profilanswer
 

MaybeEijOrNot a écrit :


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?


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

n°2209443
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 16:42:40  profilanswer
 

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.

n°2209444
Totoche17
Posté le 06-11-2013 à 16:49:02  profilanswer
 


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é.
 
 :D  

n°2209454
Profil sup​primé
Posté le 06-11-2013 à 17:35:28  answer
 

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 ?

n°2209455
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 17:36:22  profilanswer
 

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.

n°2209456
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 17:36:45  profilanswer
 

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.


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209457
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 17:36:56  profilanswer
 

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

n°2209459
rufo
Pas me confondre avec Lycos!
Posté le 06-11-2013 à 17:43:15  profilanswer
 

MaybeEijOrNot a écrit :

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?


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.


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209460
MaybeEijOr​Not
but someone at least
Posté le 06-11-2013 à 18:05:50  profilanswer
 

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

n°2209548
rufo
Pas me confondre avec Lycos!
Posté le 07-11-2013 à 10:29:59  profilanswer
 

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 :D ).
 
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 :jap:


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209562
MaybeEijOr​Not
but someone at least
Posté le 07-11-2013 à 11:18:25  profilanswer
 

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. :D

n°2209571
MaybeEijOr​Not
but someone at least
Posté le 07-11-2013 à 11:50:20  profilanswer
 

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.

n°2209573
rufo
Pas me confondre avec Lycos!
Posté le 07-11-2013 à 12:03:47  profilanswer
 

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


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2209588
MaybeEijOr​Not
but someone at least
Posté le 07-11-2013 à 13:31:06  profilanswer
 

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.

mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [Résolu] Détecter le sens de parcours d'une liste de coordonnées

 

Sujets relatifs
Afficher une Liste.Problème Scrit qui liste les fichiers
[Java] Liste chaînée - PilePatrons pour détecter les titres et les sous tires d'un fichier texte
[PHP/JQuery] Liste déroulante suivit Autocompleterequète dans une liste déroulante
liste déroulantes liées, innerHTML non compatible IEExcel: Aide pour imprimer à partir d'une liste
Liste déroulante et passage de variableLier la sélection d'une liste dans une classe à une autre classe.
Plus de sujets relatifs à : [Résolu] Détecter le sens de parcours d'une liste de coordonnées


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR