50 km x 50 km "Chunks"

Ich muss nochmals die von kellerma geäusserte Idee der 50 km x 50 km “Chunks” (http://forum.openstreetmap.org/viewtopic.php?pid=151156#p151156) aufgreifen. Die Idee, OSM Daten nicht in Länder und Region, sondern in definierte Quatrate zu unterteilen finde ich überlegenswert. Wenn man mal davon ausgeht, dass ein Quatrat alle innerhalb, hinein und hinaus führende Objekte (Punkte, Wege, Relationen) enthält und jedes Objekt eindeutig referenziert werden kann, sollte es möglich sein, solche Quatrate zu beliebigen Gegenden zusammenzufügen. Was ein Quadrat jetzt genau enthält, wie gross es ist und wie das mit dem Zusammenfügen genau geht, muss noch im Detail bestimmt werden. Wir können jedoch davon ausgehen, dass dies lösbar ist.

Wir hätten somit einmal eine Art “Tiles” (Quadrate), aber als Rohdaten in Files. Diese könnte man nun wieder über ein normales P2P Netzwerk auf beliebig viele Clients verteilen. Das “rendern” (erzeugen) dieser Quadrate könnte man wie bei den Tiles auf die geänderten Daten in der DB beschränken, womit die Verteilung sich ebenfalls auf die gänderten Quadrate beschränken kann.

Was jetzt ein Client mit seinen Quadraten anstellt, ist allein seine Sache. Die einen können ihre Spezial-DB aktualisieren, die anderen ihre Spezial-Tiles rendern, oder was auch immer damit machen. Die Vorteile einer solchen Lösung liegen auf der Hand. Spezialkarten von beliebiger Grösse, Aussehen oder Gegend wären einfach machbar. Spezielle Server wie XAPI würden nicht mehr gebraucht und die Verteilung via P2P würde auch den Flaschenhals beim Masterserver lösen.

Wyo

Es gibt da ein paar technische Grenzfälle, die eine solche verlustfreie Aufteilung derzeit verhindern.

Wenn eine Straße oder ein Polygon über eine Schneidegrenze geht, muß es aufgeteilt werden. Bei einem sauberen Schnitt entstehen entlang der Grenze künstliche Punkte, die nicht in den OSM-Daten enthalten waren. Wenn sich etwas mehrfach über die Grenze schlängelt, entstehen mehrere Linien bzw. Polygone, die alle dieselbe ID tragen würden, da sie Bruchstücke eines Ganzen sind. Die notwendige Reihenfolge für das Wiederzusammensetzen ist dann nicht mehr erkennbar.

Derzeit kommt kein Tool damit zurecht. Es müßten erst klare Regeln für das Zerlegen, wieder Zusammenfügen und für den Umgang mit solchen Schneideartefakten definiert werden und ein verlustfreier Splitter/Unsplitter geschrieben werden.

Bei einer P2P-Lösung ist eine Datenstruktur gefragt, die auf der einene Seite mit der großen Anzahl an Chunks zurechtkommt, gleichzeitig aber auch häufige (tägliche?) Updates verkraftet. Die Chunks aus unterschiedlichen Updateständen sind ja nicht miteinander kompatibel.

bye
Nop

Genau. Ich habe keine Ahnung, wie das Splitten beim Tile rendern geht, vermute aber dass es eine ganz ähnliche Aufgabenstellung ist. Wenn man z.B. zu jedem Weg, der in/aus dem Quadrat führt den ersten ausserhalb liegenden Punkt mit gibt, dürfte dieser exakt über dem letzten Punkt im benachbarten Quadrat liegen. Solche übereinanderliegende Punkte zu mergen, dürfte kein Problem sein.

Ich sehe da kein Problem, solange die Grenzen eines Quadrats genau definiert sind, sollte auch der Dateninhalt übereinstimmen. Hat es innerhalb eines Quadrates keine Edits gegeben, müssten die Files identisch sein.

Wyo

Leider funktioniert das OSM Datemmodell nicht ganz so, so kann die Geometrie eines Weges ändern ohne das die gleichzeitig eine neue Version des Weges generiert wird. Verschiebe ich z.B. ein Stützpunkt eines Weges, so sind potentiell alle Schnittpunkte falsch über mehrere Kacheln hinweg, ich kann dann aber nicht anhand der Version des Weges merken.

Simon

Updates muss man mit den Planeten machen (macht die Geofabrik ja auch). Dann das ganze in Tiles hacken. Dieses muss mit completeRelation und completeWays (genaue osmosis-Befehle müsste man raus suchen, hab ich gerade nicht im Kopf) passieren. Dann sollte es auch mit dem Puzzlen gehen.

ABER: Das ganze lässt sich nicht wirklich sinnvoll mit dem Planeten machen, weil viel zu viel gechached werden muss.
UND: Das führt bei vielen (alle die die Länder so nutzen, wie sie derzeit vorhanden sind) zu viel mehr rechenaufwand. Erst Tiles mergen und dann zurecht schneiden.

Du machst einen Denkfehler, da die Kacheln erst auf dem Client gerendert werden, muss nur dieser einte Stützpunkt übermittelt werden. Die Schnittpunkte werden dann anhand dieses Stützpunktes neu berechnet.

Es kann sein, dass der verschobene Punkt in ein anderes Quadrat zu liegen kommt, dann müssten natürlich 2 Quadrate übermittelt werden.

Wyo

Mehr Rechenaufwand auf dem Client lässt sich nicht vermeiden, ich halte den aber für vertretbar. Ich kann mich täuschen, aber so kompliziert sollte das mergen nicht sein. Und warum noch schneiden? Es müssten ja nicht 50km x 50km Quadranten sein, man könnte auch 1km x 1km nehmen.

Auf der anderen Seite reduziert sich doch der Download beträchtlich, auch wenn man keine P2P Lösung vorsieht. Hat man mal ein Land heruntergeladen, muss man das nächste mal nur noch die geänderten Quadranten holen. Auch wenn man das nur einmal im Jahr macht, gibt es eine Anzahl Quadranten, die nicht geändert haben.

Wyo

1x1 km2 ist eindeutig zu klein, wenn in jeder Kachel alle Objekte drin sein sollen, die mindestens einen Node in der Kachel haben, weil viele Objekte z.T. deutlich länger als 1km sind. Da lädt man viele Daten mehrfach herunter. Denk nur mal an eine Autobahnrelation. 50x50km2 bzw. 100x100km2 halte ich für sinnvoll.

Zu der Rechenzeit: Die Downloadzeit für Deutschland dürfte gleich sein, eher größer. Dann die Kacheln mergen. Bei 100x100km2 sind das ~70 Kacheln für Deutschland. Das dauert bestimmt 30min auf einem guten PC, dann daraus wieder einen Ausschnitt erstellen, damit das Produkt am Ende auch noch etwas mit Deutschland zutun hat und nciht noch halb Dänemark oder Österreich mit dabei sind. Dauer nochmal 30min. Es kostet also rund 1h mehr Zeit.

Die Erstellung der Tiles dauert auch sehr viel länger und ist aufwändiger. Schrieb ich ja schon oben.

Das das mit den geänderten Quadranten nicht wirklich funktioniert, wurde auch schon geschrieben.

Wenn jemand genau einmal Deutschland oder XXX haben will, magst du recht haben, dass die Methode mit Chunks Mehraufwand bedeutet. Ob man dann die Teile aus den Nachbarländern wegschneidet oder mit rechnet, dürfte vom Aufwand her ähnlich viel sein.

Aber nicht jeder braucht/will ein ganzes Land. Dann sieht die Bilanz schon ganz anders aus.

Einen wirklichen Vorteil haben Leute die einen Grenzen überschreitenden Ausschnitt haben wollen, seien es 100 km rund um Aachen oder die Eifel + angrenzende Teile von Belgien oder südliches NRW + nördliches RLP oder einmal rund um den Bodensee oder Karlsruhe-Basel links und rechts des Rheins. Weitere Beispiele lassen sich sicher leicht finden.

Edbert (EvanE)

Ich verstehe bei der Diskussion um die Größe der “chunks” nicht, was gegen den planet-split von http://wiki.openstreetmap.org/wiki/User:Computerteddy spricht, die gibt es doch schon viele Jahre. Warum soll das Rad denn neu erfunden werden?

Zumindest für Google Maps auf Android scheinen Vektor-“Tiles”/Chunks die bessere Lösung zu sein:

http://googleblog.blogspot.com/2010/12/under-hood-of-google-maps-50-for.html

Kannst etwas genauer sagen, welchen Abschnitt in http://wiki.openstreetmap.org/wiki/User:Computerteddy du genau meinst? Auf die schnelle konnte ich nichts passendes finden.

Wyo

Wieviele Autobahnrelationen gibt es? Wieviele Häuser gibt es? Ich glaube diese Zahlen allein sind schon selbstredend.

Es mag vielleicht sein, dass 1x1 km2 die falsche Grösse ist, aber sicher ist sie eher vernünftig als 50x50 Km2 oder noch grösser. Zudem wenn es einen Splitter/Unspitter mal gibt, dürften mit ein paar wenigen Tests eine vernünftige Grösse bestimmt werden können.

Warum? Kannst du das nochmals erläuern?

Wyo

Was soll man noch dazu sagen, es erklärt eientlich genau, was ich ausdrücken will. Interessant wären natürlich auch die technischen Details wie z.B. Grösse und Unterteilung der Quadrate.

Wyo

Zum Einen besteht die Welt aus mehr, als nur Mitteleuropa, zum Anderen fällt es schon ins Gewicht, wenn ich große Objekte, Autobahnen waren nur ein Beispiel, zigfach herunterladen muss.

Je kleiner das Raster ist, desto größer ist die Gefahr, dass eine Kachel komplett innerhalb eines Polygons liegt. Außerdem steigt die Datenmenge insgesamt an, da viele Daten mehrfach heruntergeladen werden müssen.

Du hast in einer Kachel einen Node, der zu einem Weg gehört, der wiederum zu einer Relation gehört. Wird der Node geändert, musst du alle Kacheln aktualisieren, in denen die Relation mindestens einen Node hat. Solche Änderungen kommen recht häufig vor. Wieder nur ein Beispiel. Ich hoffe du verstehst, wieso das in Gegenden mit hoher Mapperdichte illusorisch ist.

Wenn man genaue Regeln für Schnittkanten erstellt, entfällt die Dopplung der Daten. Allerdings passt das ganze dann wirklich nur innerhalb einer Version der Chunks.

Wenn man viel mit den Extrakten arbeitet denke ich, dass es am besten ist, sich ein Extrakt im pbf-Format auf die Platte zu legen und dieses aktuell zu halten. Anleitungen, wie man das mit osmosis machen kann, gibts im wiki.

Link: http://wiki.openstreetmap.org/wiki/User:Computerteddy#Spezialkarten_.2F_Special_Maps
Kachel-Server: http://openstreetmap.teddynetz.de/latest/osm
Kachel-Auswahl: http://ulrichkuester.de/OSM/CoordinateToOSMTile.html

Hallo,

ich werde in Kürze beginnen meine Bachelorarbeit zu schreiben und visiere ein OSM-Thema an. Die hier beschriebene Idee hat mich gepackt und ich würde mich gern intensiver damit beschäftigen.

Mich würde interessieren: Arbeitet schon irgendjemand an dieser Aufgabe?

Grüße

Nachtrag der Vollständigkeit wegen:

Das Ergebnis dieser Bachelorarbeit ist OSMT - OSM Split and Merge Tool.