Hallo, ich habe eine Liste mit Koordinaten (x|y) und möchte darin gerne eine bestimmte Koordinate effizient suchen. Die Koordinaten sind sortiert (mehr oder weniger), sodass ich mir folgendes überlegt:
Code:
koordinate searchPosition(long, lat, v) { //v = Vergleichswert
if(strecke[v].long == long && strecke[v].lat == lat) {
return strecke[v];
} else if(strecke[v].long > long && strecke[v].lat > lat) {
return searchPosition(long, lat, v/2);
} else if(strecke[v].long < long && strecke[v].lat < lat) {
return searchPosition(long, lat, v + v/2)
}
}
Jetzt ist das aber nicht vollständig, weil es auch sein kann, dass long kleiner und lat größer (oder anders herum) ist, weil es sich hierbei um Positionen von Bahnhöfen handelt und man dort ja nicht immer durch exakt einen Punkt fährt (es gibt ja Beispielsweise verschiedene Gleise) und es kann auch sein, dass ein Punkt nicht exakt so in der liste vorhanden ist. Wie würde ich diese Methode vervollständigen?
Wenn es `n` eindeutige Bahnhöfe gibt, dann würde ich diese doch nicht durch irgendeine Geokoordinate mit beliebigen geografischen Ausmaßen bzw. Unschärfe repräsentieren.... sondern mit einer eindeutigen Id/Identität.
Ja das ist schon richtig, der Punkt ist, dass mir diese Koordinaten von der Bahn zur Verfügung gestellt wurden. Aber mal angenommen, ich nehme so eine ID und ermittle die Koordinaten selbst, dann hätte ein Bahnhof ja im einfachsten Fall vier Eckpunkte. Wie würde ich hier am besten suchen ob und wenn ja in welchem Bahnhof man sich gerade befindet?
Hier geht es doch nur um eine Zuordnung: er will für einen Punkt wissen, bei welchem Bahnhof sich dieser befindet. Der Punkt wird also eine gewisse Nähe zum Bahnhof haben, zumindest wird es keine Unsicherheiten aufgrund weniger Meter Abweichung geben.
Na ja, dann soll sie oder er in searchPosition mit lat und lon alle Bahnhöfe durchgehen und jeweils die Entfernung bestimmen. Die geringste Entfernung ist dann wahrscheinlich der gesuchte Bahnhof.
Also passt auf, das ganze ist mir erstmal zu kompliziert, weshalb ich mich dazu entschieden habe, das Ganze annäherungsweise als Rechteck zu gestalten:
Ich habe die Koordinaten A und B durch die ein Rechteck gebildet wird und den Punkt P, der überprüft werden soll.
Dann gilt doch:
A.long <= P.long
A.lat >= P.lat
B.long <= P.long
B.lat <= P.lat
und den Punkt
"lat":50.102439994129544,"long":8.542163271369174
Dieser liegt eigentlich im Bahnhof, meine if-Abfrage sagt aber, dass er außerhalb liegt und ich finde den Denkfehler einfach nicht