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)