LanX-+2009-01-29 12:35:11--

Du kannst als Datenstruktur also einfach eine der vielen 2D Lösungen im CPAN heranziehen, und die nächsten Nachbarn von Start- udn Endpunkt untersuchen.

Nein, das hab ich auch schon überlegt. Es geht eben, wie ich schon oben geschrieben habe nicht, weil die Richtung nicht einbezogen ist. Man kann also entweder einen Richtungsvektor bestimmen oder der einfachheit halber gleich mit 4 Punkten rechnen!

LanX-+2009-01-29 12:35:11--

EDIT:
tatsächlich müsste man sicherheitshalber tiefer gehen und auch kriterien für den Richtungsvektor betrachten, was hilft es wenn die "nächste" Straße orthogonal verläuft?

Das orthogonale ist gar nicht das Problem, sondern das zwei entgegengesetzte Spuren einer Straße von den Punkten her als passend ausgesucht würden. Es ist aber wichtig, dass die Fahrzeuge in die selbe Richtung fahren wie ursprünglich geplant. Denn sonst müssten sie, um Ihr Ziel zu erreichen, bei der nächsten Kreuzung wieder umkehren.

Im Extremfall könnte es passieren, dass z.B. auf einer Autobahn alle Fahrzeuge von ursprünglich mehreren Spuren in beiden Fahrtrichtungen auf ein Spur einer Fahrtrichtung gemappt werden, weil diese Edge zufällig das erste ist, was durch den Algorithmus gefunden wird. Das hätte aber fatale Folgen für die Simulation!

stelzbock+2009-01-29 12:52:26--

Nein, das hab ich auch schon überlegt. Es geht eben, wie ich schon oben geschrieben habe nicht, weil die Richtung nicht einbezogen ist. Man kann also entweder einen Richtungsvektor bestimmen oder der einfachheit halber gleich mit 4 Punkten rechnen!

Sorry das ist Schmarrn, du brauchst jeweils zwei 2D-Karten, eine für die Startpunkte und eine für die Endpunkte.

Suche den nächsten Startpunkt BS zum Startpunkt AS einer Kante A und vergleiche dann die Endpunkte AE und BE.

wg Abstand=1/2( |AS-BS| + |AE-BE| ) bekommst du gleich eine Schranke für den weitere Suche. ¹

Da Start udn Endpunkte in verschiedenen Karten sind kann es keine Verwechslung geben!!!

EDIT:
(¹) außerdem wenn du |AS-BS| schon minimal gewählt hast kommen nur noch Kanten C mit
|AE-CE| <= |AE-BE| in Frage um das Ergebnis zu verbessern!

Und dein 4D Ansatz brint dir IMHO nix wenn die Richtungen nicht stimmen.

Stell dir vor 2 kleine Gassen treffen rechtwinkling aufeinander und der Fehler in der anderen Karte legt den start der einen Gasse auf den der anderen, dann kanns passieren das du die Gassen falsch zuordnest.

Zumindest müsstest du darlegen wieso das nicht passieren kann!

LanX-+2009-01-29 13:26:10--

Sorry das ist Schmarrn, du brauchst jeweils zwei 2D-Karten, eine für die Startpunkte und eine für die Endpunkte.
...

Also ich bin für alles offen, was mir die Arbeit erleichtert :)

Aber das Problem ist ja dann, wie willst du die Zuordnung zum Edge herstellen. Du hast dann in Zwei unabhängigen Karten zwei optimale Start und Ednpunkte gefunden, die aber ziemlich Sicher zu verschiedenen Edges gehören!?

du musst natürlich zu jedem Start auch seinen Endpunkt assozieren. Am besten du legst in jeder Karte eine Referenz auf die komplette Kante (Sx,Sy,Ex,Ey) ab...

Ja, ok, ich hätte dann einen optimalen Startpunkt und einen optimalen Endpunkt und jeweils die dazu zugeordnete Kante, die mit hoher Wahrscheinlichkeit nicht die selben sein werden.

Die Frage ist jetzt, wie verfahre ich jetzt weiter, um eine einzige Kante zu finden, die das optimale Ergebnis darstellt.

Und durch 4D ist eben genau die Richtung dabei, und zwar auch nicht verwechselbar, da jede Komponente eine eigene Dimension beschreibt. 4 Punkte stellen eine Kante dar, die ersten beiden Start und die letzten beiden den Endpunkt. UNd das ist bei beiden Karten so. Wenn ich nun den eukl. Abstand berechne, ziehe getrennt die einzelnen Koordinaten von einander ab.

Somit ist das Richtungsproblem gelöst. Sollte in deinem Beispiel diese Gasse aus Karte A in Karte B gesucht werden, und es gibt zwei Gassen die Rechtwinklich zueinander stehen, dann wird die zu A parallele Gasse automatisch den kleineren Abstans ergeben. Ist in Karte B nur eine Gasse an dieser Stelle, die allerdings rechtwinklig zu A steht, ist es auch egal, da es in diesem Fall einfach den optimalen Match darstellt!

Ich will mich aber überhaupt nicht gegen dein 2D Modell wehren, da es für mich den attraktiven Vorteil hätte, dass ich der fertige R-Tree modell nehmen kann. Aber ich bin momentan noch sicher, ob das funktioniert! ICh hoffe es ist nur ein Verständnisproblem meinerseits ;)

Gruß Jan

@stelzbock: Ich denke, Du koenntes folgendes machen: Du speicherst alle Anfangspunkte des neuen Datensatzes in einem R-Tree und assoziierst sie jeweils mit ihrem Endpunkt. Dann suchst Du zu jedem Anfangspunkt im alten Datensatz nahegelegene Anfangspunkte des neuen Datensatzes ueber den R-Tree und waehlst under den gefundenen Treffern denjenigen aus, bei dem auch der Endpunkt gut passt.

Fuer den zweiten Auswahlschritt duerfte ein direkter Vergleich der Abstaende ausreichen, da ja wohl pro Anfangspunkt nur wenige Treffer vorliegen werden -- im Mittel wuerde ich bei 2D-Kartendaten nur etwas mehr als vier Treffer pro Startpunkt erwarten.

@murphy...

Ja, so in der Art hatte ich es auch schon überlegt! Und so werde ich es auch wahrscheinlich machen... Wäre natürlich noch schöner das ganz für 4D zu haben, aber der Aufwand ist dafür zu groß, dass ich es nur einmal machen muss...

Danke!

stelzbock+2009-01-29 14:18:37--

Ja, ok, ich hätte dann einen optimalen Startpunkt und einen optimalen Endpunkt und jeweils die dazu zugeordnete Kante, die mit hoher Wahrscheinlichkeit nicht die selben sein werden.

Die Frage ist jetzt, wie verfahre ich jetzt weiter, um eine einzige Kante zu finden, die das optimale Ergebnis darstellt.

was du immer noch nicht verstehst ist das du weitersuchen musst bis du alle möglichen Kanten ausprobiert hast. Der Gag ist die Zahl der möglichen Kanten schnell einzuschränken.

Wenn dein bisheriges Optimum eine Kante mit Abstand X ist dann sind alle Kanten deren Eckpunkte 2X entfernt sind unmöglich !!! Das schränkt deinen Suchraum so schnell ein dass deine Suchschleife schnell abbricht. Tatsächlich kannst du den Suchraum noch stärker einschränken aber versteh das erst mal ...

Vom mathematischen sehe ich aber noch einige Fallstricke und ich würde euch schon raten einen Profi einzustellen statt rumzuraten...