Discussion :

[sglug]

Bonjour,
je voudrais par calcul savoir si un point (longitude, latitude) se trouve en France. pour ça j'ai a ma disposition un polygone dont je connais chaque point et qui représente la France.
par ex voici les coordonnées composant le polygone autour de paris :
2.2432708740234375, 48.839141876306556;
2.256317138671875, 48.88250866640883;
2.303009033203125, 48.907788609578795;
2.3709869384765625, 48.913655339565594;
2.4176788330078125, 48.9068859745916;
2.4444580078125, 48.87754146105978;
2.44171142578125, 48.85676416656577;
2.434844970703125, 48.84140149087084;
2.426605224609375, 48.83010239864697;
2.40325927734375, 48.815635841683424;
2.366180419921875, 48.807496568302234;
2.3242950439453125, 48.803878689339356;
2.2830963134765625, 48.810209806241;
2.26318359375, 48.821513384068865;
2.2467041015625, 48.83462234135941;
il est composé de 15 points
maintenant par calcul je voudrais savoir si le point(2.341461181640625, 48.8734770170422) est dans mon polygone donc dans paris.

certains vont me dire qu'il existe des service web faisant ça, oui je sais, mais je voudrais le calculer moi même, enfin avec votre aide car je ne sais pas comment m'y prendre.

[Zavonen]

Je crois qu'il faut se ramener au cas du plan par un système de projection, par exemple Mercator (voir wiki).
Les points qui définissent le contour approximatif d'un pays sont alors les sommets d'un polygone plan. Pour savoir si un point de la sphère terrestre ramené à sa projection sur la planisphère est dans le polygone on dispose d'un outil analytique (l'indice d'un point par rapport à un lacet).
Le calcul peu aisé en toute généralité est particulièrement simple dans le cas où le lacet est un polygone.

[sglug]

je suis déjà dans un système plan en 2D.
j ai pas refais de math depuis très très longtemps. mais la en gros si on trace sur une feuille de papier une croix abscisse, ordonnées (x,y)

on peut ensuite reporter chaque point du polygone. lorsqu'on relie chaque point on dessine bien une forme.

si j ai ensuite des coordonnées, que je reporte ce point sur ma feuille, je suis capable de dire si oui ou non le point est dans le polygone ou s'il est en dehors.

et il se trouve que ce polygone, peut être superposer sur une carte "routière" et quelle représente un pays dans mon exemple, mais je pourrais aussi définir une forme représentant un trajet pour une course par exemple, en déterminer grossièrement les contours, et récupérer les coordonnées GPS de chaque coureur, puis grâce à la solution que je cherche déduire si des coureurs sont sortie de la zone (polygone) déterminé.

[pseudocode]

maintenant par calcul je voudrais savoir si le point(2.341461181640625, 48.8734770170422) est dans mon polygone donc dans paris.

Le retour de la vengeance du fils du winding number

http://softsurfer.com/Archive/algori...n_PinPolygon()

[sglug]

merci pseudocode

je vais tester ça et l'adapter pour le faire en php.
je reviendrais pour mettre la solution.

[Zavonen]

Le retour de la vengeance du fils du winding number

Le fils caché français du 'winding number' s'appelle l'indice d'un point par rapport à un lacet (circuit). Il se généralise bien sûr à des courbes qui ne sont pas des polygones, mais dans notre monde pixelisé toutes ses courbes perdent leurs 'rondeurs'. Enfin, comme dans la réalité, en n'y regardant pas de trop près...
Nous parlons donc bien de la même chose.
Sur cette page il y a une animation super:
http://en.wikipedia.org/wiki/Winding_number

[pseudocode]

Le fils caché français du 'winding number' s'appelle l'indice d'un point par rapport à un lacet (circuit).

"winding number" ca fait quand même plus classe !

[SpiceGuid]

Un cas particulier intéressant est celui du polygone convexe à n côtés:

• le polygone convexe est l'intersection de n demi-plans
• l'appartenance d'un point à un demi-plan est le signe de l'image des coordonnées de ce point par l'équation de la droite

(dvp n'a pas de ressources en géométrie algorithmique, c'est dommage parce que le domaine est très formateur)

[Camel LowFilter]

C'est une idée SpiceGuid mais reste à parser le polygone quelconque en graph de polygones convexes. Divers algos possibles pour ça: diagramme de voronoi, triangulation au plus proche, bsp tree (ce dernier est plus rapide à tester s'il est précalculé et enregistré sur le serveur)

Je ne sais pas du tout si c'est l'approche la plus efficace...

[souviron34]

puisque nous en sommes aux vieiiles citations encore une fois, le forum Usenet News :

comp.graphics.algorithms

sujet 2.06

[souviron34]

je suis déjà dans un système plan en 2D.
j ai pas refais de math depuis très très longtemps. mais la en gros si on trace sur une feuille de papier une croix abscisse, ordonnées (x,y)

on peut ensuite reporter chaque point du polygone. lorsqu'on relie chaque point on dessine bien une forme.

si j ai ensuite des coordonnées, que je reporte ce point sur ma feuille, je suis capable de dire si oui ou non le point est dans le polygone ou s'il est en dehors.

et il se trouve que ce polygone, peut être superposer sur une carte "routière" et quelle représente un pays dans mon exemple, mais je pourrais aussi définir une forme représentant un trajet pour une course par exemple, en déterminer grossièrement les contours, et récupérer les coordonnées GPS de chaque coureur, puis grâce à la solution que je cherche déduire si des coureurs sont sortie de la zone (polygone) déterminé.

D'abord prendre conscience que raisonner en termes de latitude/longitude dépend des cartes et du fait qu'elles ont le même système de projections et les mêmes paramètres.

Ensuite prendre conscience du fait qu'une droite en latitude ou longitude n'est pas une droite sur Terre.

Enfin, pour un vrai calcul, utiliser les équations des projections pour calculer en coordonnées rectangulaires (sinon on se retrouve comme le camion l'autre jour, dans le lac parce que le GPS donnait pas la bonne coordonnée sur la carte).

Mais il semble que nos constructeurs et fournisseurs ne s'attardent plus la véracité de leurs calculs

[sglug]

Bonjour souviron34,

J'ai bien pris conscience de ce que tu dit, ca a été long , mais bon ok il faut utiliser les projections.

Et du coup j'ai pris conscience que je suis nul en math en plus de l'orthographe .

J'ai finalement opter pour un découpage en rectangle, c'est plus simple à calculer, donc j'ai plein de rectangles qui reproduise la France.
Chaque rectangle est défini par 2 points, le supérieur gauche(A) et l'inférieur droit(C), dont je connais la latitude et la longitude.

j'utilise Google Maps qui se base sur les projections de Mercator.
Donc si j'ai bien compris, pour savoir si un point se trouve dans un rectangle, il faut que je calcul les coordonnée (x,y) de mes 3 coordonnées (2 pour le rectangle et 1 pour le point recherché) et seulement a ce moment je peux utilisé la formule :
est dans le rectangle si ( Ax<Px & A>Py & Cx>Px & Cy< Py )
avec Ax = la valeur x du point A (le supérieur gauche)
Ay = la valeur y du point A (le supérieur gauche)
C = l'inférieur droit
P = le point recherché

ils est écrit que la latitude=φ et de sa longitude=λ (avec λ0 au centre de la carte)
Q1 : pour λ0 je peu prendre 0 de longitude? puisque je fait des calcul sans représentation visuelle.

sauf que dans la formule ci dessous, je ne connais pas tous les termes

bon ln = logarithme népérien
tan = la tangente.
Q2 : sec qu'est ce donc?

[Graffito]

Voir : http://www.developpez.net/forums/d14...oint-polygone/

[souviron34]

..
j'utilise Google Maps qui se base sur les projections de Mercator.
Donc si j'ai bien compris, pour savoir si un point se trouve dans un rectangle, il faut que je calcul les coordonnée (x,y) de mes 3 coordonnées (2 pour le rectangle et 1 pour le point recherché) et seulement a ce moment je peux utilisé la formule :
est dans le rectangle si ( Ax<Px & A>Py & Cx>Px & Cy< Py )
avec Ax = la valeur x du point A (le supérieur gauche)
Ay = la valeur y du point A (le supérieur gauche)
C = l'inférieur droit
P = le point recherché

ils est écrit que la latitude=φ et de sa longitude=λ (avec λ0 au centre de la carte)
Q1 : pour λ0 je peu prendre 0 de longitude? puisque je fait des calcul sans représentation visuelle.

sauf que dans la formule ci dessous, je ne connais pas tous les termes

bon ln = logarithme népérien
tan = la tangente.
Q2 : sec qu'est ce donc?

je ne le sais pas par coeur. Sans doute secante ? (comme cosec est cosecante)

La bible de référence pour les conversions lat-lon / rectangulaires suivant les différentes projections est :

Reference Map Projections - A Working Manual
U.S. Geological Survey Professional Paper 1935.

TOUTES les projections dans un sens et dans l'autre, avec les algos, et des exercices de vérifications dans les 2 sens.

Toute personne sensée s'occupant de calculs de coordonnées terrestres se doit de l'avoir.

• A commander aux US (environ 100 dollars)
• Peut-être disponible en France directement, ou dans un labo près de chez toi, ou à l'université (département géomatique ou géographique) la plus proche, ou à l'IGN peut-être ?
• Possiblement à emprunter à une bibliothèque scientifique

[souviron34]

j'ajouterais pour ta question 1 :

je ne sais pas où est centrée ta carte...

lambda 0 est la longitude centrale de la carte qu'on veut transformer en X,Y.

Si tu as la carte de France, ce sera sans doute quelque chose aux alentours de 3.0..

Si tu as la carte de l'Amrique du Nord, sans doute aux environs de -110.

Si tu as la carte du monde, il faut savoir où elle est centrée...

[sglug]

elle sont parfois condescendante tes réponse dit moi souviron34. enfin

j'ai trouvé cette formule sur le géniale Wikipedia, c'est bien de cela que nous parlons.

donc y = ln( tan A + 1/ cos A )

[souviron34]

elle sont parfois condescendante tes réponse dit moi souviron34. enfin

désolé, j'ai dû mal m'exprimer, ce n'était pas dans mon intention ...

Je donne juste la référence de la bible et répond à ta question...

Si c'est pour la dernière phrase du post référence, ça n'était pas dirigé vers toi, mais tu n'es pas le premier sur ce forum à poser ce genre de questions...
Parce qu'il y a beaucoup de gens qui croient que puisqu'ils voient une carte affichée comme un rectangle, c'est simple... Et ça finit par m'énerver... Comme tu t'en rends compte, il y a pas mal de maths, et c'est pas hyper-simple...

Et quand tu passes des mois à te taper de programmer et vérifier les formules de conversions pour que ça marche dans tous les cas, ça finit par énerver de voir que la plupart des projets googleiens s'en f;utent pas mal, de la véracité de ce qu'ils sortent...

Voilà. En rien contre toi, désolé, juste un ras-le-bol...

[jack-ft]

Bonjour,
je voudrais par calcul savoir si un point (longitude, latitude) se trouve en France. pour ça j'ai a ma disposition un polygone dont je connais chaque point et qui représente la France.

il est composé de 15 points
maintenant par calcul je voudrais savoir si le point(2.341461181640625, 48.8734770170422) est dans mon polygone donc dans paris.

certains vont me dire qu'il existe des service web faisant ça, oui je sais, mais je voudrais le calculer moi même, enfin avec votre aide car je ne sais pas comment m'y prendre.

Petit déterrage de sujet et petite réflexion:

La question de savoir si un point est "à l'intérieur" d'un polygone dessiné sur une sphère n'a de sens que pour des "petits" polygones, sinon il peut être difficile de distinguer "l'intérieur" de "l'extérieur" du polygone.

Par exemple, si on prend un polygone qui fait en gros l'équateur de la Terre. Le pôle Nord est-il à l'intérieur de ce polygone???

Plus subtil: si on prend la couture d'une balle de tennis standard, un point donné est-il à "l'intérieur" de la zone délimitée par la couture???

En fait, il me semble que la question perd son sens lorsque le centre de gravité de la courbe est le centre de la sphère...

[Flodelarab]

Bonjour

Trois concurrents: un ingénieur, un physicien et un mathématicien. Ils ont une épreuve à réaliser. Cette épreuve consiste à construire une clôture tout autour d'un troupeau de moutons en utilisant aussi peu de matériel que possible.

• L'ingénieur fait regrouper le troupeau dans un cercle, puis construit une barrière bien solide tout autour.
• Le physicien imagine une clôture potentiellement infinie qu'il fixe en un point et après avoir fait le tour du troupeau, relie les deux bouts.
• Le mathématicien construit une clôture autour de lui-même et se définit comme étant à l'extérieur.

Powaaaaaa les mathématiciens.