Comparaison d'un "chemin" (ou trace GPS) d'un véhicule

Question

J'ai une question d'algorithme difficile, je ne trouve aucun algorithme approprié à partir de beaucoup de recherche, donc j'espère que quelqu'un ici sur stackoverflow pourrait savoir la réponse. J'ai un ensemble de coordonnées x, y pour un véhicule qui se déplace dans un espace 2D, les coordonnées sont enregistrées aux «points de décision» dans la période de temps (c.-à-d. Ils se sont arrêtés et ont déterminé où se déplacer prochain). Ce que je veux faire est de trouver un mécanisme pour comparer efficacement ces chemins (c'est-à-dire ne pas passer par chaque point individuellement). En outre, je m'intéresse au «modèle» de leur mouvement, pas nécessairement aux points individuels auxquels ils sont allés. Cela signifie que le "chemin" est considéré comme identique si vous le réfléchissez autour d'un axe, ou si vous le faites pivoter de 90,180 ou 270 degrés. Fondamentalement, j'essaie de distiller une sorte de «comportement» à la façon dont ils se déplacent dans l'espace, puis d'examiner les différents «comportements» à des fins de classification.

Cheers,

Aidan

Answer 1

Cela peut être plus compliqué que vous cherchez, mais il semble que ce que les gars ont fait à astrometry.net peut être semblable à ce que vous cherchez. Essentiellement, vous pouvez télécharger une image de certaines étoiles, et il va déterminer la position dans le ciel auquel il appartient, avec la rotation, vous pouvez être en mesure d'utiliser un modèle similaire correspondant à ce que vous recherchez. Ils ont un grand pdf expliquant comment cela fonctionne here, et apparemment vous pouvez les envoyer par courriel et ils vous enverront le code source (les détails sont dans le pdf).

Edit: apparemment, vous pouvez télécharger le code directement here.

Hope it helps.

Answer 2

il y a plusieurs approches que vous pouvez faire:

Utilisation de chemins vectoriels et traduction matricies avec deux algorithmes, A * (une étoile) algorithme (pour trouver les meilleurs itinéraires de ce qu'on appelle les fonctions gourmandes), et algorithme "le plus proche voisin" - ces deux algorithmes sont couramment utilisés pour comparer l'efficacité des chemins pour les routes.

vous ne le savez peut-être pas, mais le problème que vous avez est connu sous le nom de "voyageur de commerce" problème et a beaucoup de nombreuses approches.

donc rechercher

problème du voyageur de commerce A * le plus proche voisin

regarder aussi

algorithme de marche aléatoire - pour l'approche la plus fondamentale

une approche comportementale appris essayer réseaux de neurones "ANN" ou algorithmes génétiques

les mathématiques pour ce type de problème sont couvertes par ce qu'on appelle la "théorie des graphes"

Answer 3

Il semble que ce qui est nécessaire est essentiellement une métrique pour comparer deux chemins (N en général) et choisir le meilleur? Si c'est le cas, je suggérerais des statistiques simples. Je commencerais par l'histogramme de cap (orientation), l'histogramme relatif (par rapport au cap précédent) et ainsi de suite. Une autre chose vient à l'esprit: la distance/orientation entre les points de covariance. Ou simplement créer une sorte de "statistiques" (nombre de tours, etc.) et comparer ces chemins en utilisant cela.