Découper un polygone (issu de Google Maps)

Version imprimable

27/02/2017, 12h47
didate

1 pièce(s) jointe(s)

Découper un polygone (issu de Google Maps)

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

Pièce jointe 248840

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

Merci à vous.
27/02/2017, 13h22
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:

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 ?
27/02/2017, 13h33
didate

Oui c'est exactement ça que je veux.
27/02/2017, 15h15
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:

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.

Merci beaucoup tbc92

J'ai aussi trouvé ça dans mes recherches
Code:

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 .

1 pièce(s) jointe(s)

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:

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:

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:

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 ) ; }
Citation:

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:

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:

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 :

Citation:

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)
Pièce jointe 249573

01/03/2017, 13h51
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.
01/03/2017, 14h18
didate

Merci pour ta réponse

Citation:

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.

Citation:

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
01/03/2017, 14h49
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.

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

voici la fonction corrigé :

Code:

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:

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:

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:

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.

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

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.

01/03/2017, 16h26
didate

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

ça devrait être ça :

Code:

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.
02/03/2017, 11h16
didate

1 pièce(s) jointe(s)

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

Pièce jointe 249959

Merci Beaucoup tbc92.