WisFaq!

Dynamische kortste afstandsbepaling

Hallo,

Ik heb een geografische route berekend door een routeplanner. De beschikbare informatie is opgebouwd uit de coordinaten van veel (3000) korte rechte lijnen van (X1, Y1) naar (X2, Y2) naar (X3, Y3) etc.
Nu krijg ik dynamisch (elke 10 seconden) een positie binnen met (Xd, Yd) coordinaten.
Hoe bepaal ik nu zo efficient mogelijk welke van de (3000) korte rechte lijnen ik moet hebben.
Vervolgens hoe bepaal ik de kortste afstand.

Bedankt voor de denkhulp, John

John
19-9-2004

Antwoord

Hallo, John.
Ik ben geen deskundige op dit gebied. Omdat de vraag nog niet beantwoord is, probeer ik een intuïtieve aanpak.
Ik zou me dan bij elke stap zo veel mogelijk richten op het einddoel (X_e,Y_e).
Noem twee punten naburig als er bij de 3000 een rechte lijn is van het ene punt naar het andere.
Dus bepaal telkens (dwz bij elke d) het naburig punt (X_d+1,Y_d+1) zó dat de richtingscoëfficiënt van het lijnstuk van (X_d,Y_d) naar (X_d+1,Y_d+1) zo veel mogelijk lijkt op de richtingscoëfficiënt van het lijnstuk van (X_d,Y_d) naar (X_e,Y_e).
Dus zorg telkens dat ((Y_d+1-Y_d)/( X_d+1-X_d))/((Y_e-Y_d)/(X_e-X_d)) zo min mogelijk van 1 verschilt.
Het kan zijn dat u op een gegeven moment geen geschikt punt (X_d+1,Y_d+1) kunt vinden dat ook maar enigszins in de richting van het einddoel ligt (het verschil van bovengenoemd dubbelquotiënt met 1 is bijvoorbeeld steeds minstens 0.5). U bent dan op een "dood spoor", en moet terug naar het voorlaatste punt (X_d-1,Y_d-1) om daar nu de "een na beste" stap te proberen in plaats van de "beste" die u op dood spoor zette. Is er geen "een na beste" stap, ga dan nog verder terug.
U kunt natuurlijk vele varianten op deze procedure proberen.
Bijvoorbeeld, u kunt telkens 2 stapjes vooruit kijken ipv 1. Of u kijkt verder vooruit naarmate u dichter bij het einddoel komt.
Een andere opzet: zoek bij (X_d,Y_d) het naburig punt (X_d+1,Y_d+1) zo dat de afstand Ö((X_d+1-X_e)²+(Y_d+1-Y_e)² tot (X_e,Y_e) minimaal is.
Bij het bepalen van de beste route "vergeet" u natuurlijk de stappen die naar dood spoor leidden.
Wij zijn eens naar Rhenen gewandeld, afgaande op de Cunerakerk. Maar op een gegeven moment stonden we vlak bij de kerk aan de verkeerde oever van de rivier ... toen moesten we dus terug om een brug te zoeken.

hr
30-9-2004