J'ai une piste GPS produite par Après avoir écrit plusieurs heures de piste de plusieurs heures, GPXLogger enregistre plusieurs fichiers GPX de mégaoctet long qui comprend plusieurs milliers de points. Ensuite, j'essaie de tracer cette piste sur une carte et d'utiliser avec OpenLayers . Cela fonctionne, mais plusieurs milliers de points font en utilisant la carte une expérience bâclée et lente.
Je comprends qu'avoir plusieurs milliers de points de sous-optimaux. Il y a des myriades de points qui peuvent être supprimés sans rien perdre presque: quand il y a plusieurs points, ce qui représente à peu près la ligne droite et nous déplaçons avec la même vitesse constante entre eux, nous pouvons simplement quitter le d'abord et le dernier point et jetez autre chose.
J'ai pensé à utiliser GPSBABEL pour un travail de simplification / optimisation de ce type de piste, mais, hélas, c'est Le filtre de simplification ne fonctionne qu'avec des itinéraires, c'est-à-dire analyser uniquement la forme géométrique de chemin de chemin, sans horodatages (c.-à-d. Ne pas vérifier que la vitesse était grossièrement constante).
Y a-t-il des utilitaires / une bibliothèque / algorithme / algorithme de prêt à l'emploi pour optimiser pistes ? Ou peut-être que je manque une option intelligente avec GPSbabel? gpxlogger (1) (fourni en tant que client pour GPSD ). Le récepteur GPS met à jour ses coordonnées toutes les deux secondes, la logique GPXLogger est très simple, elle écrit l'emplacement ( lat , lon , ELE ) et un horodatage ( temps ) reçu de GPS tous les n secondes ( n = 3 dans mon cas).
10 Réponses :
J'ai couru dans un problème similaire. Le taux à laquelle l'unité GPS prend des points est beaucoup plus grande que nécessaire. Beaucoup de points ne sont pas géographiquement éloignés les uns des autres. L'approche que j'ai prise est de calculer la distance entre les points à l'aide de la formule Haversine. Si la distance n'était pas plus grande que mon seuil (0,1 miles dans mon cas), j'ai jeté le point. Cela obtient rapidement le nombre de points à une taille gérable.
Je ne sais pas quelle langue vous recherchez. Voici un projet C # que je travaillais. En bas, vous trouverez le code Haversine.
http://blog.bobcravens.com/2010/09 / GPS-utilisant-the-netduino /
J'espère que cela vous va aller.
Bob
Merci, mais votre exemple est beaucoup plus simple que ce dont j'ai besoin. Si je comprends bien votre code correctement, vous venez de filtrer des points qui ne diffèrent pas beaucoup d'une distance donnée d'un précédent. Je veux simplifier davantage, en vérifiant que nous maintenons la même vitesse constante pendant un certain temps. Dernier point, mais non le moindre, vous utilisez la formule Haversine, alors qu'il est préférable d'utiliser Formule de Vincy - Openlayers comprend la mise en œuvre de celle-là. Merci pour la réponse quand même :)
@Greycat Pourquoi est-il préférable d'utiliser la formule de voisinage plutôt que de Haversine?
Haversine est beaucoup moins précis: elle suppose que la planète est la sphère, tout en assume un sphéroïde oblat, qui est beaucoup plus proche de la Terre vraiment.
@Greycat précision est presque sans importance pour ce contexte. Vous n'avez pas besoin de précision lorsque vous jeûtiez la plupart de vos données en premier lieu :) sur les petites distances (sous 1 mile), nous parlons de simplifier les pistes GPS, est-ce qu'il importe vraiment si le point est un Peu de pieds lors de leur décider si le point de piste est nécessaire ou non? Haversine est plus rapide ...
Vrai, mais si nous reviendrons dans le contexte du problème initial, nous n'utiliserons aucun d'entre eux de toute façon - en fait, il suffit d'utiliser des coordonnées de polygone + l'algorithme 3D Douglas-Pebucker donne d'excellents résultats.
Pour les points qui sont vraiment proches de chacun, l'autre La formule Haversine est absolument correcte pour calculer les distances. Vous pouvez même utiliser un simple pythagore pour cela. Mkompf.com/gps/distCalc.html
Ceci est probablement np-dur. Supposons que vous ayez des points A, B, C, D, E.
Essayons un simple algorithme déterministe . Supposons que vous calculiez la distance entre le point B et la ligne A-C et il est plus petit que votre seuil (1 mètre). Donc, vous supprimez B. Ensuite, vous essayez de la même chose pour la ligne A-D, mais c'est plus grand et d pour C-E, qui est également plus grand.
Mais il s'avère que la solution optimale est A, B, E, car le point C et D sont proches de la ligne B-E, mais sur des côtés opposés.
Si vous supprimez 1 point, vous ne pouvez pas être sûr que cela devrait être un point que vous devriez rester , sauf si vous essayez chaque solution possible (qui peut être Étape suivante: Essayez A force brute ou branche et lié algorithme. Ne fonctionne pas, ne fonctionne pas pour la taille réelle. Vous pouvez ignorer cette étape en toute sécurité :)
Étape suivante: d'abord, faites un algorithme déterminé et améliorez-le avec un algorithme métaheunique (Tabu Recherche, recuit simulé, algorithmes génétiques). En Java, il y a quelques implémentations open source, telles que beools planificateur .
Dans l'ensemble, vous aurez probablement une solution réalisable (bien que pas optimale) avec le premier algorithme déterministe simple, car vous n'avez que 1 contrainte.
Un cousin lointain de ce problème est probablement la variante du vendeur itinérant dans laquelle le vendeur ne peut pas visiter toutes les villes, mais doit en choisir quelques-uns. n ^ n en taille, donc sur n = 80 c'est plus que le nombre minimum d'atomes dans l'univers connu).
Si nous nous efforçons de trouver une solution vraiment optimale (avec un nombre cible donné de points à gauche), alors oui, c'est probablement le NP-dur, mais «« assez bon », la solution me convient. Fondamentalement, il se résume à la recherche d'une bonne approximation d'une ligne dans un espace 3D de '' (x, y, t) '', composé à l'aide de segments droits.
Vous voulez jeter ininterresting points. Vous avez donc besoin d'une fonction qui calcule à quel point un point est intéressant, vous pouvez alors calculer à quel point tous les points sont intéressants et jetez les points n les points les moins intéressants, où vous choisissez n pour mince le jeu de données suffisamment. On dirait que votre définition d'intéressante correspond à une accélération élevée (écart par rapport à un mouvement de ligne droite), qui est facile à calculer.
Je ne connais pas mon nombre de points cible de priori. Mais en général, oui, la solution assez simple consiste à avoir une métrique simple pour chaque point de savoir comment il est exactement intéressant (de préférence sur une fenêtre coulissante de "k" points "K '" points "K" après-vente) . Avez-vous une idée de la façon dont cette métrique ressemblerait probablement - j'ai un peu expérimenté et je ne peux pas en venir avec un?
Laissez le point d'intérêt être x_2, le point précédent soit X_1 et le point suivant être x_3. Laissez les heures à laquelle vous étiez à ces points être T_1, T_2, T_3. Ensuite, la vitesse avant le point est v_12 = (x_2 - x_1) / (t_2 - t_1) et la vitesse après le v_23 = (x_3 - x_2) / (T_3 - T_2). Le vecteur d'accélération est A = (v_23 - v_13) / (T_3 - T_1). Vous voudriez utiliser la magnitude de ce vecteur | A |.
Ce serait une approximation de l'accélération instantanée, pas une accélération moyenne pondérée dans une fenêtre coulissante. Je ne suis pas sûr que cela fonctionnera - c'est-à-dire de révéler exactement des points non intéressants, mais garantira que tous les points intéressants resteraient.
Je suppose que vous devez garder des points où vous changez de direction. Si vous divisez votre piste dans l'ensemble des intervalles de direction constante, vous ne pouvez laisser que des points limites de ces intervalles.
Et, comme Reedwald l'a souligné, vous voudrez laisser des points où votre accélération n'est pas nulle.
regarder RAMER-DOUGLAS-PEucker Algorithme de polygones complexes de lissage, également Douglas-PEucker algorithme de simplification de ligne peut vous aider à réduire vos points.
Merci, je pensais qu'il y ait déjà eu un algorithme disponible, il suffit de le manquer! Suis-je raison que la seule chose que j'ai besoin ici est l'adaptation de cet algorithme dans un espace 3D (c'est-à-dire des coordonnées) et de définir une "distance orthogonale" dans un tel espace?
Ouais, vous devrez cartographier le paramètre en quelque sorte :)
Vous ne savez pas à quel point cela fonctionnera bien, mais que diriez-vous de prendre votre liste de points, de la distance entre eux et donc de la distance totale de l'itinéraire, puis de décider de la distance de résolution, puis tout simplement linéaire interpolant la position basée sur chaque étape de x mètres. C'est-à-dire pour chaque solution que vous avez une "distance de Démarrer" mesurez-vous et que vous interpitez simplement où N * X est pour votre route. (Vous pouvez décider du nombre de points que vous souhaitez et divisez la distance totale pour obtenir la distance de votre résolution). En plus de cela, vous pouvez ajouter une fonction de fenêtres à prendre peut-être les points de point de courant +/- z et à appliquer une pondération comme EXP (-K * dist ^ 2 / précision ^ 2) pour obtenir la moyenne pondérée d'un ensemble de points où dist La distance entre le point répolié brut et la précision est la précision supposée de la position GPS.
Une méthode vraiment simple consiste à retirer à plusieurs reprises le point qui crée l'angle le plus large (dans la plage de 0 ° à 180 ° celle de 180 ° signifie qu'il s'agit d'une ligne droite entre ses voisins) entre ses voisins jusqu'à ce que vous ayez assez de points . Cela commencera à éliminer tous les points qui sont parfaitement conformes à leurs voisins et iront de là.
Vous pouvez le faire en ο (n journal (n)) en faisant une liste de chaque index et son angle, triant que Liste de l'ordre décroissant de l'angle, en gardant combien vous avez besoin de l'avant de la liste, triant cette liste plus courte dans l'ordre décroissant de l'index et en supprimant les index de la liste des points. P>
def simplify_points(points, how_many_points_to_remove)
angle_map = Array.new
(2..points.length - 1).each { |next_index|
removal_list.add([next_index - 1, angle_between(points[next_index - 2], points[next_index - 1], points[next_index])])
}
removal_list = removal_list.sort_by { |index, angle| angle }.reverse
removal_list = removal_list.first(how_many_points_to_remove)
removal_list = removal_list.sort_by { |index, angle| index }.reverse
removal_list.each { |index| points.delete_at(index) }
return points
end
Oui, comme mentionné précédemment, l'algorithme Douglas-Petucle est un moyen simple de simplifier les chemins connectés 2D. Mais comme vous l'avez signalé, vous devrez l'étendre au boîtier 3D pour simplifier correctement une piste GPS avec une dimension temporelle inhérente associée à chaque point. Je l'ai fait pour une application Web de la mienne en utilisant une implémentation de PHP de Douglas-Pebucker.
Il est facile d'étendre l'algorithme au boîtier 3D avec un peu de compréhension de la façon dont l'algorithme fonctionne. Dites que vous avez un chemin d'entrée composé de 26 points étiquetés A à Z. La version la plus simple de ce chemin a deux points, A et Z, donc nous commençons là. Imaginez un segment de ligne entre A et Z. Numérisez maintenant à travers tous les points restants B à Y pour trouver le point le plus éloigné du segment de ligne AZ. Dis dire que le point le plus éloigné est J. Ensuite, vous numérisez les points entre B et I pour trouver le point le plus éloigné du segment de ligne AJ et les points de numérisation K à Y pour trouver le point le plus éloigné du segment JZ, etc., jusqu'à ce que les points restants Tous se trouvent dans un seuil de distance souhaité.
Cela nécessitera quelques opérations vectorielles simples. Logiquement, c'est le même processus en 3D que dans 2D. Si vous trouvez un algorithme de Douglas-Petucle mis en œuvre dans votre langue, il pourrait avoir une mathématique 2D vectorielle mise en œuvre, et vous devrez étendre celles-ci pour utiliser 3 dimensions.
Vous pouvez trouver une implémentation 3D C ++ ici: 3D Douglas-Pebucker en C ++
Vos coordonnées X et Y seront probablement en degrés de latitude / longitude, et la coordonnée Z (heure) peut être en quelques secondes depuis l'époque UNIX. Vous pouvez résoudre ce divergence en décidant d'une relation temporelle spatiale appropriée; Disons que vous voulez voir une journée d'activité sur une zone de carte de 1 mile carré. Imaginez cette relation en tant que cube de 1,6 km d'ici 1 jour, vous devez presciser la variable de temps. La conversion des degrés sur la distance de surface est non triviale, mais pour ce cas, nous simplifions et dit qu'un degré est de 60 milles; Puis un mile est de 0,0167 degrés. Un jour est de 86400 secondes; Ensuite, pour rendre l'équivalent des unités, notre facteur de présidence pour votre horodatage est 0.0167 / 86400, ou environ 1/5 000 000.
Si, dites, vous voulez voir l'activité GPS dans la même zone de carte carrée de 1 mile carré de plus de 2 jours à la place, la résolution temporelle devient la moitié aussi importante, de sorte qu'elle diminue deux fois plus loin, à 1/10 000 000. Amusez-vous.
Si vous recherchez une classe PHP, cela fait cela, voici 2 que j'ai trouvé: github.com/david-r-edgar/rdp-php Github.com/gregallensworth/php -Geometry Ici vous pouvez tester votre fichier simplification en ligne, lire avec la configuration et voir instantanément les résultats et les modifications: lab.easyblog.it/maps/gpx-simplify-Optimizer
Essayez ceci, c'est gratuit et opensource Service en ligne:
Pourriez-vous expliquer où puis-je trouver des sources pour ce service?
Ah, donc c'est la mise en œuvre du RDP. Merci!
Oui ... Fourche le code de repo GitHub si vous voulez essayer un autre algorithme!
Bibliothèque Java OpenSource Geokarambola (aucune dépendance Android mais peut être utilisée dans Android) qui inclut une classe GPXPathManipulatrice qui fait la simplification / la réduction de la piste (3D / élévation). Si les points ont des informations d'horodatage qui ne seront pas supprimées. https://sourceforge.net/projects/geokarambola/
C'est l'algorithne en action, de manière interactive https: //lh3.googleusercontent. COM / -HVHFYZFCY58 / VSYE7NVRMII / AAAAAAAHDG / 2-NFVFOAAHDG / 2-NFVFBD4SHZCVTYCDPI2VXOYKZVFLQ / W360-H640-NO / MODIFIP360X640.05_82_05.gif
Cet algorithme est basé sur la réduction du nombre de points en éliminant ceux qui ont la plus grande erreur XTD (distance de la distance croisée) jusqu'à ce qu'une erreur tolérée soit satisfaite ou que le nombre maximum de points est atteint (les deux paramètres de la fonction), Wichever vient en premier.
Un algorithme alternatif, pour la simplification de la piste comme la piste (je l'appelle «Streamplification») est la suivante: Vous conservez un petit tampon des points que le capteur GPS vous donne, chaque fois qu'un point GPS est ajouté à la mémoire tampon (élévation incluse) Vous calculez la distance XTD max XTD (distance de croix) de tous les points du tampon au segment de la ligne. Unit le premier point avec le dernier point de la mémoire tampon (nouvellement ajouté). Si le point avec le plus grand XTD viole votre erreur XTD maximum toléré (25 m me a donné d'excellents résultats), vous coupez le tampon à ce point, enregistrez-le en tant que point sélectionné pour être ajouté à la piste pluviale. Coupez la partie de fuite de la Tampon jusqu'à ce point coupé et continue. Au bout de la piste, le dernier point du tampon est également ajouté / rincé à la solution. Cet algorithme est suffisamment léger qu'il s'exécute sur un SmartWatch AndroidWear et donne une production optimale, peu importe si vous vous déplacez lentement ou rapide, ou si vous êtes debout au même endroit pendant une longue période. La seule chose que Maters est la forme de votre piste. Vous pouvez aller pour de nombreuses minutes / kilomètres et, tant que vous déménagez dans une ligne droite (un couloir dans des écarts d'erreur XTD tolérées) L'algorithme de planification de Streamplify ne produira que 2 points: celles de la dernière courbe et entrée sur la courbe suivante.
