On Wed, 22 Apr 2009 13:11:48 +0200, Tobias Wendorff <tobias.wendo...@uni-dortmund.de> wrote: > Gernot Hillier schrieb: >> Auf der folgenden Seite ist auch schon seit längerem ein schöner >> Algorithmus dafür vorgeschlagen: >> http://wiki.openstreetmap.org/wiki/OSM_tags_for_routing#City > > Dabei entstehen aber deutliche Lücken. Ich würde da eher > Voronoi-Diagramme vorschlagen.
a) Auf dem Erdboden GIBT es deutliche Lücken zwischen Ortschaften. Wenn es sie nicht gäbe und keine Polygone vorliegen würde Voronoi die gleichen Fehler machen. b) Voronoi hilft nur wenn mehrere Ortschaften im Suchradius gefunden werden. Dass man hier die nächstgelegene nimmer ist selbstverständlich und führt somit zum exakt gleichen Ergebniss. Das Ergebniss unterscheidet sich also nur wenn weit ausserhalb einer Ortschaft eine Strasse auftaucht. Diese kann gut und gerne aber auch zu gar keiner oder einer nicht in der Karte eingetragenen Ortschaft gehören. c) Für Voronoi musst du die gesammte Welt verarbeiten. In vielen Fällen ist das nicht möglich und schon das Durchsuchen aller Nodes im Radius einer Stadt nach einem place-node kann zu teuer sein. b) Mit dem Algorithmus lässt sich bei sich ändernden Karten ein korrekter Index aller Ortschaften aufrechterhalten ohne auf mehr als die sich ändernden Elemente zu schauen. Insbesondere ist nur 1 Datenbankzugriff (kombiniertes Update/Insert-Komanto) nötig und keine aufwendige 2D-Area-Suche nach vorhandenen Ortschaften vor einem Update um die Form der Voronoi-Region zu ändern. Fazit: Voronoi würde wohl funktionieren ist aber oft nicht praktikabel und bringt keinen den Aufwand an Bandbreite, Speicherplatz, Arbeitspeicher und nicht zu letze Rechenzeit rechtfertigenden Mehrwert. Marcus _______________________________________________ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
