Discussion :

[didate]

Bonjour

Je ne sais pas si je suis dans la bonne section, si c'est pas le cas je demande au admin de m'aider à déplacer la discussion.

J'ai un polygone délimité par des coordonnées gps, le polygone fait environ 450km2, je veux placer dans ce polygone des points distancés de 20m.

voici un exemple de ce que je veux faire : la distance entre les points doit être de 20m



Je cherche un algorithme en Java, Android voir même JavaScript qui pourrai m'aider à le faire.


Merci à vous.

[tbc92]

Oublions google Map un instant ... on verra à la fin comment adapter le problème à la sphère terrestre.

Si on était sur un plan (x,y) classique , on ferait un traitement de ce genre :

Code :

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

1
2
3
4
5
6
7
8
 
pour x = xmin à x max pas 20
  pour y = ymin a ymax  pas 20
    si est_dans_polygone ( x, y ) alors 
       plot( x,y)
    fin si 
  fin
fin

On aurait donc des (x, y) disposés en quadrillages tous les 20 mètres.
Et sans les traits entre les plots.

C'est ça que tu veux ?

[didate]

Oui c'est exactement ça que je veux.

[tbc92]

Dans ce cas, j'essaierai ainsi :

1. tu cherches quel Delta-latitude correspond à une distance de 20 mètres , idem quel Delta-longitude correspond à 20 mètres. Pour Delta-longitude, ça va dépendre de l'emplacement sur le globe. 1°, quand on est sur l'équateur ou sur le cercle polaire, ça ne correspond pas du tout à la même distance. Tu es sur une surface de 450 km², ce n'est pas très grand, on peut considérer que sur une portion de cette surface, les parallèles et les méridiens forment des rectangles.
Attention, si tu travailles près des pôles, et si tu as besoin d'une distance de 20m précisément, ça ne marche pas.

2. tu fais la même boucle

Code :

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

1
2
3
4
5
6
7
8
 
pour la = la_min à la_max pas la_00
  Pour  lo = lo_min a lo_max pas lo_00
    si est_dans_polygone ( la, lo ) alors 
       plot( la, lo )
    fin si 
  fin
fin

Reste le plus difficile : Pour un point de latitude (la, lo), déterminer si ce point est dans un polygone P.

Pour ça, si je recherche "algorithme point intérieur polygone" sur Google, je trouve plein de solutions... A toi de regarder si ces solutions fonctionnent.

[didate]

Merci beaucoup tbc92

J'ai aussi trouvé ça dans mes recherches

Code :

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

1
2
3
4
To determine the destination point, knowing the starting point the direction θ and the distance d, we use the following formula: 
 
latB = asin( sin( latA) * cos( d / R ) + cos( latA ) * sin( d / R ) * cos( θ )) 
lonB = lonA + atan2(sin( θ ) * sin( d / R ) * cos( latA ), cos( d / R ) − sin( latA ) * sin( latB ))

ça permet de trouver le point suivant, connaissant le point de départ, la direction et la distance.

J'ai déjà la solution pour la fonction est_dans_polygone ( la, lo ) .

Merci encore une fois. je vais tester tout ça et voir ce que ça va donner .

[didate]

Alors j'ai essayé de tester tous ça, mais je pense que j'ai raté un truc :

Pour arriver à l'algorithme suivant j'ai voulu aller pas à pas

Code :

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

1
2
3
4
5
6
7
pour la = la_min à la_max pas la_00
  Pour  lo = lo_min a lo_max pas lo_00
    si est_dans_polygone ( la, lo ) alors 
       plot( la, lo )
    fin si 
  fin
fin

j'ai cherché à déterminer un point de destination connaissant le point de départ et la distance entre les deux, en appliquant les formules suivantes.
Avec R = 6372.795477598 et θ la direction est aussi à déterminer.

Code :

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

1
2
latB = asin( sin( latA) * cos( d / R ) + cos( latA ) * sin( d / R ) * cos( θ )) 
lonB = lonA + atan2(sin( θ ) * sin( d / R ) * cos( latA ), cos( d / R ) − sin( latA ) * sin( latB ))

Alors pour déterminer θ j'ai utilisé le code suivant :

Code :

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

1
2
3
4
5
6
 public static double direction(LatLng dep, LatLng point){
    	double pi = 3.1416 ;
    	double dt  = Math.log(Math.tan( point.latitude  / 2 + pi/ 4 ) / Math.tan( dep.latitude/2 + pi/4) ) ;
    	double deltaLon = Math.abs(dep.longitude  - point.longitude  ) ;
    	return Math.atan2( deltaLon ,  dt ) ;
    }

LatLng point, est un point qui se situe sur la même droite que le point de départ et le point de destination

Enfin le code qui calcul le point de destination :

Code :

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

1
2
3
4
5
6
7
8
9
10
 public static LatLng dest(LatLng depart, double direction,double distance){
    	LatLng ln = new LatLng();
    	double R = 6372.795477598*1000;   	
 
    	direction = Math.toRadians(direction);
    	depart.latitude = Math.toRadians(depart.latitude);
    	ln.latitude  = Math.asin( Math.sin( depart.latitude) * Math.cos( distance / R ) + Math.cos( depart.latitude ) * Math.sin( distance / R ) * Math.cos( direction ));    	
    	ln.longitude  = depart.longitude  + Math.atan2(Math.sin( direction ) * Math.sin( distance / R ) * Math.cos( depart.latitude ), Math.cos(distance/R )-Math.sin( depart.latitude ) * Math.sin( ln.latitude ));  	
    	return ln;
    }

Le code de test :

Code :

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

1
2
3
4
 
   LatLng depart = new LatLng(9.575107,-13.652315);
		System.out.println(Utils.direction(depart,new LatLng(9.584755,-13.652658)));		
		System.out.println(Utils.dest(depart, 3.106482888052143, 20));

Résultat :

3.106482888052143
Lat = 0.16712027710926805, Lon = -13.652314827524767

Ce qui ne semble pas correcte surtout pour la latitude.

Ai-je raté quelque chose dans mon code ? peut-être les conversion degré <-> radian ? m <-> km ?

L'objectif de mon projet c'est d'arriver à faire ça : ( capture de plus.codes)

[tbc92]

Dans le code que je proposais, j'avais 2 direction : Ouest et Nord ( éventuellement Est et sud ) ; c'est à dire qu'à partir d'un point donné, je partais 20m vers l'ouest, et je traçais le point correspondant , etc.

Ici, tu as un principe différent. Ok, tu fais comme tu veux, c'est toi le demandeur. Mais cette variable direction que tu introduis, elle est sensée prendre quelles valeurs ?
0 = Nord , 90 = Est, 180 = sur , et 270 = Ouest par exemple, au pif. Ou quelles autres valeurs ?
Et avec cette variable direction, tu comptes faire quoi ? A partir d'un point de départ, tu vas placer différents points dans cette direction, tous les 20m, c'est ça ? mais ça va faire une ligne, pas un quadrillage.

Et enfin, si on revient au dessin de départ, tu avais un polygone ; selon quel critère tu vas choisir de placer des points sur une direction Nord-Est // Sud-Ouest , plutôt que Nord-Sud, ou bien Est-Ouest ?

Ici, je vois des lignes de codes, mais je n'arrive plus à comprendre le plan de travail. Et sans plan de travail, il est prématuré de regarder le code.

[didate]

Merci pour ta réponse

Ici, tu as un principe différent. Ok, tu fais comme tu veux, c'est toi le demandeur. Mais cette variable direction que tu introduis, elle est sensée prendre quelles valeurs ?
0 = Nord , 90 = Est, 180 = sur , et 270 = Ouest par exemple, au pif. Ou quelles autres valeurs ?
Et avec cette variable direction, tu comptes faire quoi ? A partir d'un point de départ, tu vas placer différents points dans cette direction, tous les 20m, c'est ça ? mais ça va faire une ligne, pas un quadrillage.

Peut-être j'ai mal expliqué dans ma dernière réponse, l'objectif reste le quadrillage. Mais pour arriver à ca, dans mon exemple j'ai essayé de commencer par faire une ligne. si j'arrive à faire ça, je me dis que le quadrillage deviendra plus simple.

Et enfin, si on revient au dessin de départ, tu avais un polygone ; selon quel critère tu vas choisir de placer des points sur une direction Nord-Est // Sud-Ouest , plutôt que Nord-Sud, ou bien Est-Ouest ?

Alors mon point de départ est sur la gauche (ouest) du dessin de départ et la direction c'est vers la droite(Est) . donc ce qui donne Ouest-Est

[tbc92]

D'accord.
A partir d'un point de départ, tu traces plusieurs points , un tous les 20m, systématiquement vers l'Est.
Donc tu n'as pas besoin de calculer une direction ; tu sais que la direction que tu veux, c'est vers l'est.

Puis dans un 2nd temps, on prendra une direction vers le Nord , ou le Sud, pour faire un quadrillage au lieu d'une simple ligne.

Ici, tu commençais par calculer une direction (D=3.10648) ; ça ne sert à rien. Essaie en remplaçant ce 3.10648 par 0.

A priori, ça ne va pas résoudre ton problème.

Il y a une erreur sure, c'est que tu dis R = 6372 (donc tu Décides d'utiliser le kilomètre comme unité, c'est TON choix) , et plus bas, tu dis dist = 20 ; donc tu fais un déplacement de 20 kilomètres, et pas un déplacement de 20 mètres.

Ensuite, il y a probablement des problèmes entre degré,radians ...
Essaie System.out.println(Utils.dest(depart, 0 , 0));
C'est à dire se déplacer de 0 kilomètre à partir du point de départ. Ton programme devrait t'afficher le point de départ. Si ce n'est pas le cas, c'est qu'il y a un problème. Vérifie l'aide de ton langage pour savoir si il attend des degrés ou des radians.
La majorité des langages travaillent en radians, et toi, pour l'instant, tu utilises les degrés.

[didate]

J'ai corrigé tout ça, je pense maintenant qu'on est proche du bon résultat

voici la fonction corrigé :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
public static LatLng dest(LatLng depart, double direction,double distance){
    	LatLng ln = new LatLng();
    	double R = 6372.795477598*1000;   	
 
    	direction = Math.toRadians(direction);
 
    	double latRadian = Math.toRadians(depart.latitude);
    	double lngRadian = Math.toRadians(depart.longitude);
 
    	ln.latitude  = Math.toDegrees(Math.asin( Math.sin( latRadian) * Math.cos( distance / R ) + Math.cos( latRadian ) * Math.sin( distance / R ) * Math.cos( direction )));    	
    	ln.longitude  = Math.toDegrees(lngRadian  + Math.atan2(Math.sin( direction ) * Math.sin( distance / R ) * Math.cos( lngRadian ), Math.cos(distance/R )-Math.sin( lngRadian ) * Math.sin( lngRadian )));  	
    	return ln;
    }

Code :

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

1
2
3
4
 
LatLng depart = new LatLng(9.575107,-13.652315);
System.out.println(Utils.dest(depart, 0, 0));
//Le résultat est : Lat = 9.575107, Lon = -13.652315000000002

Code :

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

1
2
3
LatLng depart = new LatLng(9.575107,-13.652315);
System.out.println(Utils.dest(depart, 0, 20));
//Le résultat est : Lat = 9.575286813646034, Lon = -13.652315000000002

La latitude qui change, ce qui me semble bizarre, je pense que c'est la longitude qui devrait changer dans ce cas.

Code :

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

1
2
3
LatLng depart = new LatLng(9.575107,-13.652315);
System.out.println(Utils.dest(depart, 0, 20));
//Le résultat est : Lat = 9.575106999952402, Lon = -13.652129958162357

Même remarque dans ce cas aussi.

[tbc92]

Tu fais 2 fois le même test, et tu obtiens 2 résultats différents, c'est bizarre :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 
//Test 1 ----------------------------------
LatLng depart = new LatLng(9.575107,-13.652315);
System.out.println(Utils.dest(depart, 0, 20));
//Le résultat est : Lat = 9.575286813646034, Lon = -13.652315000000002
 
// Test 2 ---------------------------------
LatLng depart = new LatLng(9.575107,-13.652315);
System.out.println(Utils.dest(depart, 0, 20));
//Le résultat est : Lat = 9.575106999952402, Lon = -13.652129958162357

Dans le test 1, le point résultat est plein nord par rapport au point de départ. Mais pourquoi pas, ça n'a rien de surprenant. On a pris la direction 0, en se disant : 'avec un peu de chance, la direction 0, ça va être Vers l'Est'. mais non, on constate que la direction 0, c'est Vers le Nord.

Et j'imagine qu'entre le test 1 et le test 2, tu as modifié la méthodes dest(), et maintenant, la direction 0 correspond bien à un déplacement vers l'EST.

PS : affiche les longitudes / Latitudes avec 6 décimales, c'est plus facile à lire, et c'est largement suffisant comme précision.

[didate]

ah désolé c'est une erreur de copie pour le deuxième test.

ça devrait être ça :

Code :

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

System.out.println(Utils.dest(depart, 90, 20));

Vraiment merci beaucoup.

Je laisse la discussion non résolu, je vais m'attaquer maintenant au quadrillage. Je te fait un retour de ce que ça donne

Merci encore une fois.

[didate]

Hop, la grille a pris forme. Elle s'affiche comme je souhaite. Maintenant il faut j'applique ça sur une superficie de 245857km2.



Merci Beaucoup tbc92.