Je suis un programmeur logistique et on m'a demandé de comprendre si un point GPS est "hors route" où la route consiste en un certain nombre de points géospatiaux (latitude, longitude).
Quel est le meilleur algorithme de détermination si un point est proche de la route? J'utiliserai C # et SQL Server, mais cela ne compte vraiment pas beaucoup si je sais quel algorithme utiliser.
J'ai considéré
Je n'ai pas de diplôme en mathématiques, mais je peux probablement gérer quoi que ce soit compte tenu des termes corrects et d'un moteur de recherche.
Je devrai effectuer au moins 4000 calculs une heure, il n'est probablement pas acceptable que la solution de mappage n'est probablement pas acceptable en raison du volume.
5 Réponses :
Google pour " distance le long de la piste " et vous devriez trouver les formules couramment utilisées dans l'aviation. Alternativement, la distance croisée pourrait également être ce que vous voulez.
Merci, cela semble être la réponse que je cherchais.
Pouvez-vous prendre votre itinéraire existant en tant que séquence de segments de ligne en 2-D, puis prenez votre point de requête et trouvez le point le plus proche et le segment de ligne la plus proche? La distance entre ce segment des points / lignes la plus proche serait la distance que vous aimez.
Si vous collez à des latitudes relativement faibles (en dessous de 60 degrés), vous pourrez peut-être traiter la latitude et la longitude comme si elles étaient simplement plates, comme sur une projection Mercator.
Sinon, vous ne pouvez pas transformer le système de coordonnées pour être relatif à un grand cercle qui traverse certains des points d'itinéraire.
Sauf si vous avez affaire à des millions de points d'itinéraires, vous ne devriez pas avoir de problème avec le temps de la CPU.
C'est l'une des formules que j'ai envisagées, mais j'ai trouvé des cas où cela ne fonctionnera tout simplement pas en fonction de la forme de la route. La plupart d'entre eux ne sont nulles près d'une ligne droite et certains d'entre eux sont doubles sur eux. Il est encore plus compliqué lorsque le temps est impliqué, mais j'ai sauvé cela pour une autre question.
Que diriez-vous de ce qui suit ...
itérer à travers tous les segments de ligne
lineesegslope = calculer la pente pour chaque segment de ligne
Dessinez une ligne prétendue du point en question qui intersecte le segment de ligne actuel. Ceci est fait en inversant la linesegslope et en multipliant par -1 pour obtenir la nouvelle pente, puis remplacez votre point cible X, Y et une nouvelle pente dans Y-Y1 = B * (X-X1). Votre X va dans X1, votre Y va dans Y1, et votre Newslope va dans B.
faire une équation pour le segment de ligne.
Si vous dessinez les deux lignes les unes sur les autres, ils doivent faire un X lorsque chaque coin est de 90 degrés.
Calculez l'intersection des deux lignes
Calculez la distance entre le point d'intersection et votre nouveau point. Si c'est plus grand qu'une valeur tolérable, le nouveau point est trop loin.
Cela ressemble à un gâchis, mais j'espère que cela devrait fonctionner.
L'angle des points sur la route vs le point en question est de ce qui le jette lorsque je l'ai dit. Si le segment de ligne est loin du point, mais l'angle des deux points de la route est tel que la ligne est très proche du point lorsqu'elle est étendue, elle produira une réponse incorrecte. J'ai du mal à comprendre cela un peu si j'ai peut-être une mauvaise réponse avec cela.
Je vois ce que tu dis, bonne prise. Je pense que dans ce cas cependant, les extrémités des segments de ligne seraient les points les plus proches. Vous pouvez ensuite calculer la distance entre le point cible sur le segment de ligne. Fun petit problème que vous avez ici.
Une approche naïve serait d'insérer le nouveau point GPS à divers endroits le long de la route. Commencez par l'insérer avant votre premier point P0, puis entre vos premier et second points P0, et P1, et ainsi de suite jusqu'à ce que vous essayiez de l'insérer comme dernier point. Chaque fois que vous essayez de l'insérer à un emplacement, calculez la distance totale du circuit et enregistrez Enregistrer la distance totale la plus courte. Cela peut être accéléré par des distances de la jambe précalculantes et de stocker cette somme. Vérifiez la distance en soustrayant la distance de la jambe pour la jambe que vous insérez le nouveau point et ajoutez la nouvelle distance du point P (N) à votre point GPS sur P (n + 1). Si cette distance totale la plus courte est dans votre niveau de tolérance, vous pouvez l'accepter.
Ce n'est probablement pas le "meilleur" algorithme (selon votre définition de la meilleure), mais il est O (n) sur le nombre de points de votre route pour la complexité de temps et d'espace. Donc, à moins que vous ayez un énorme nombre de points dans votre itinéraire, chaque chèque doit être un peu inférieur à une seconde, de sorte que cela devrait être dans vos exigences de temps.
En outre, assurez-vous d'utiliser Equations de distance Haversine lors de l'informatique distance entre des points consécutifs sur votre itinéraire.
Le mieux pour moi est rapide et précis dans une très grande partie des circonstances. Le niveau de tolérance dans cette situation devra se développer lorsque la distance entre les points de la route est plus grande.
je vais devoir faire au moins 4000 calculs une heure, donc en utilisant un La solution de mappage n'est probablement pas acceptable en raison du volume.
En fait, c'est un exemple parfait où une solution de cartographie serait bénéfique. Pas votre traditionnel "Regardez une carte et déterminer la distance", mais "laissez la base de données déterminer quelle est la voie la plus proche de votre point GPS.
Puisque vous dites que vous n'êtes pas opposé à utiliser une base de données différente, vous pouvez envisager:
- SQL Server 2008, qui a Moteur de base de données spatiales fonctions, ou
- PostgreSQL avec la source Open-Source Postgis (spatial) extension, qui a des fonctions d'analyse significativement plus spatiales qui MS SQL 2008.
Jetez un coup d'œil à la postgis ST_DISTANCE Fonction ou MS SQL Server 2008 STDISTANCE fonction. Ceci est un bon Entrée de blog décrivant les avantages de SQL2005 VS SQL2008.
Vous pouvez également envisager de lire (ou de demander de la cartographie plus détaillée) des messages sur gis.stackexchange . Que tout le groupe est dédié à l'analyse spatiale. Quelques bonnes discussions pour vous de jeter un coup d'œil à ce serait
Merci. J'ai eu un ami suggérant que gis.stackexchange aussi bien. La vitesse est ma préoccupation avec l'utilisation d'une solution de mappage. Je dois au moins 4000 d'entre elles une heure. Mais vous avez raison est probablement la solution la plus précise.
Ce que vous avez demandé est une question intéressante. Cette solution de superficie-de-triangle ne fonctionnerait pas car deux points très éloignés généreraient un triangle avec une grande surface, même lorsque le point n'est que légèrement hors route. Pas sûr d'avoir une meilleure solution. Merci de me donner quelque chose à penser.
Quelle version de SQL Server utilisez-vous? Avez-vous des attributs sur l'emplacement de bus autre que LAT / LONG? Que diriez-vous de l'identifiant de bus, de la route ID, etc. qui peut être attaché à la bonne route / route, il devrait être sur?
@Ryandalton 2005 Malheureusement. Si je comprends bien, il y avait des très jolies fonctionnalités concernant les données spatiales. Je ne suis pas au-dessus de Mongo ou d'une autre base de données, mais cela finira par suivre un peu plus de travail pour configurer et maintenir une autre base de données avec des informations en temps réel.
@Brianwillis ouais c'est pourquoi j'ai posé la question. Je pensais que cela ne travaillerait pas. Ni l'autre ne constaterait pas la distance du point GPS aux lignes impliquées.