Während ich auf Eingebung wartete (die kam inzwischen, danke, ich les die später…), hab ich mal couchmappers Verfahren eingebaut. Testweise mal am Jakobs- und am Sebastiansplatz in München. Das sind zwei benachbarte Flächen, der Sebastiansplatz (rechts) hat kein Hindernis drin und ist nur als Fläche in OSM, Der Jakobsplatz (links) hat zwei Gebäude und ein paar Parkbänke als Hindernisse. Ausserdem hat schon jemand einen Pfad über den Jakobsplatz gelegt.
Der Routinggraph sah so aus:
Zur Vorbereitung sucht man sich alle Ecken dieser Plätze und bricht den vorhandenen Graphen dort auf. Dabei entstehen ein paar Punkte an den Aussenkanten, und noch unsichtbare an den Inneren:
Und dann holt man ein Artillerieregiment, zielt genau auf den kleinen Spatzen, feuert und Dann verbindet man jeden dieser Knoten mit jedem anderen, sofern man dazu die Fläche nicht verlassen muss.
Das ganze wird dann ein bisschen unübersichtlich, die meisten der neu entstandenen Wege sind auch nicht sinnvoll, aber man kann Routen. Und wenn man den Graphen nicht sieht, überzeugt der Vorher-Nachher-Vergleich schon:
In dem Fall hat der Router sogar vorher den Sebastiansplatz gemieden, weil der Weg an der Kante länger war und ist nur einem Stück Hausmauer am Jakobsplatz gefolgt.
Was noch getan werden müsste:
- Alle nicht sinnvollen Wege wieder rauswerfen, wobei fraglich ist, was davon sinnlos ist. Das Ziel könnte ja auch ein Haus am Platz sein, dann wäre es doof, nur die Zuwege zum Platz zu berücksichtigen.
- Alle neuen Wege verbinden. So wie es jetzt ist, kann man zwar halbwegs perfekt über den Platz, aber man kann nur schlecht den Platz verlassen. Der Router sucht dann einfach den nächsten Weg am Startpunkt und führt mich zu irgendeiner Kante, wo der Weg halt hinführt. Und erst ab da wird optimiert (in der Hausaufgabe4 ist der Startpunkt auch ein Knoten, aber dazu muss ich schon bei der Vorverarbeitung wissen, wo der Startpunkt ist).
Aber das ist kein Problem, Kreuzungen zwischen den 698 neuen Wegen gibts genug.
Ich glaube, der Aufwand ist zu hoch für das bisschen Ergebnis, aber andererseits schön routen tut der Router jetzt schon…
Grüße, Max
**Nachtrag: **
Um zu verdeutlichen, was brute force Algorithmen so anrichten, hab ich das mal für München durchgerechnet, dauert nicht mal eine halbe Stunde.
München besteht derzeit aus 56288 Wegen. Das ergibt fürs Routing 132327 Wegestückchen. Dazu kommen noch 245 Fussgängerzonen, die teilweise ungünstig überquert werden.
Nach der Abkürzungssuche stehen 206674 Wege im Routinggraphen. So schlichte Gebilde wie der Giesinger Bahnhofsplatz, über den man schon vorher gut geroutet wurde, werden dank der vielen Bäume und Parkbänke in ein 7675-kantiges Routingmonster verwandelt. Kompliziertere Flächen wie der Coubertinplatz werden in 14011 Wege zerlegt.
Statt der vorher 132327 müssen jetzt bei jeder Routing-Berechnung 206674 Wege berücksichtigt werden, 56% Zuwachs für 0.5% Fussgängerzonen.