stelzbock+2009-01-29 15:17:34--

[...] 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 [...]

Wie schon LanX- mehrmals sagte, geht es hier darum, die Menge an Treffern moeglichst weit einzuschraenken, damit die Suche schnell geht. Eine Loesung im vierdimensionalen Raum zu suchen ist dafuer nicht unbedingt optimal -- zum Beispiel wird die Datenmenge fuer einen vierdimensionalen R-Tree wesentlich groesser und dadurch dauert auch die Suche nach einem Treffer etwas laenger...

Der Vollständigkeit halber für mathematisch Interessierte:

Ich glaube mich zu erinnern das man sowas normalerweise mit Normalenvektoren löst. Die würde man in nur einer Karte repräsentieren, in dem sie am Mittelpunkt der Gerade orthogonal ansetzen.

Dann ähnliche Geraden erkent man dann dadurch dass Ihre Mittelpunkte beieinader liegen und das normierte Skalarprodukt nahe 1 liegt.

Welchen Abstandszahl man da vernüftigerweise ansetzt und ausrechnet, weiß ich allerdings nicht ...

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

Auch dein Abstandsbegriff ist ziemlich angreifbar, wieso sollte man den Abstand im 4D heranziehen? Wieso nicht das Mittel der Abstände der Start udn Endpunkte?

also ich kann da nen Sinn erkennen, Angenommen da und de sind die Distanzen von Anfang und Ende zweier Strecken. Dann wär das geometrische Mittel sqrt(da²+de²), es wär aber da=sqrt( (x0-x1)² +(y0-y1)² ) , de entsprechend! Wenn man das nun einsetzt bekommt man genau den geometrischen Abstand im 4-Dimensionalen.

Das geometrische Mittel (gm) hätte auch den Vorteil zum arithmetischen Mittel (am) parallele Strecken zu favorisieren!
da=2,de=2 => am=2, gm=sqrt 8
da=1,de=3 => am=2, gm=sqrt 10

Hallo,
eins vorweg, ich hab von Euklid, R-Tree und Spezial-Mathe keinen blassen Schimmer und wollte nur erwähnen, daß mein Arbeitskollege früher auch mit solchen Geodaten zu tun hatte, und der hat dafür die GIS-Erweiterung von postgresql eingesetzt

http://www.giswiki.org/wiki/PostGIS


In meinem jugendlichen Leitsinn würde ich die Daten evtl. erstmal in so eine DB reinschaufeln um sie dann effizienter verarbeiten zu können. Nur eine Idee, sorry wenn ich völlig falsch liege.

Viele Grüsse

Frank

@SuperFrank: Ich denke, deine Idee, das mit PostGIS zu loesen, ist gar nicht dumm. Im Endeffekt laeuft das zwar auch auf zweidimensionale R-Trees hinaus, aber man muss sich nicht um die Implementation kuemmern ;-)

Da allerdings auch das Einrichten und Verwenden von PostGIS nicht ganz ohne Tuecken ist, wuerde ich es nur empfehlen, wenn man wirklich oefter auf die Daten zugreifen will, was laut OP hier nicht der Fall ist.

So, liebe Leute :)

Et hat jefunkt!

Die Dauer hat sich jetzt von 14Tagen auf sage und schreibe 20min verkürzt!

Ich habe folgendes gemacht, falls es jemand interessiert:

1.) Kanten aus Karte 1 in ein Hash eingelesen.
2.) Kanten aus Karte 2 in ein R-Tree, wobei ich nur den Startpunkt verwendet habe. Das Standard Perl-Modul Tree::R. Da es keine Punkte aufnimmt, sondern nur Rechtecke, habe ich einfach x1=x2=x und y1=y2=y gesetzt, als faktisch einen Rechteck mit der Fläche Null. Das nacheinander einfügen dauert etwa 8 min. Die ID sowie Start + Endpunkt habe ich dann als Objekt daten im Tree gespeichert.
3.) Dann bin ich alle Edges aus Karte 1 durchgegangen.
4.) Für jedes Edge habe ich wieder nur den Startpunkt genommen. Dann hab ich ein Rechteck von etwa 500 Metern um den Startpunkt aufgespannt, und dann mit Hilfe von query_completely_within_rect() alle Edges in ein Array eingelesen, deren Startpunkte innerhalb des Rechtecks lagen. Also Quasi eine Umkreissuche.
5.)Die Resultierenden Edges aus dieser Suche (im Durchschnitt etwa 300) habe ich dann mittels des 4-dim eukl. Abstands überprüft und den besten als Match gespeichert.

3.),4.),5.) habe dann den Rest der Zeit gedauert.

Am Ende gab es für ca. 9000 Edges kein Mapping, was aber ok, da sich das Kartenmaterial nicht 100% überdeckt und an den Rändern Bereich auftreten können, die es in der einen Karte nicht gibt.



Also,nochmal vielen vielen Dank für all die hilfreichen Beiträge!

Gruß Jan

KurtZ+2009-01-30 20:20:20--

also ich kann da nen Sinn erkennen,

So durchdacht hast du recht! 8 )

Allerdings hängt das wirklich von den Daten und deren Fehlern ab... wenn hier bis zu 500m Verschiebungen zulässig sind gruselt es mir was bei Straßen gleicher Größenordnung für Fehler auftreten...

LanX-+2009-01-31 21:48:06--

Allerdings hängt das wirklich von den Daten und deren Fehlern ab... wenn hier bis zu 500m Verschiebungen zulässig sind gruselt es mir was bei Straßen gleicher Größenordnung für Fehler auftreten...

Naja, die 500 Meter, sind ja nur ein beliebiger Wert um den Wertebereich für den zweiten Algorithmus nicht zu klein werden zu lassen. Es wird ja trotzdem noch der Beste Treffer gesucht. Allerdings hast du in sofern recht, es wird, sofern mindestens einer in der Wertemenge drin ist, auf jeden Fall einer genommen.

Ich könnte jetzt den Radius so lange verkleiner bis der Ausschuss an nicht zuordbaren Kanten zu groß wird. So sind es immerhin schon 6000 von 200.000. Aber ich bin erst mal mit der Geschwindigkeit zufrieden! :)

Es wäre auch möglich, den Komponentenweisen Abstand (x,y) der Treffer vom Mittelpunkt des Rechtecks zu messen. Der größte Abstand (jeweils für x,y) entspräche dann der Mindestgröße die das Rechteck haben müsste, um alle Straßen zu erfassen.