You are not logged in.

#1 2011-03-23 13:25:06

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

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/viewtopi … 56#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

Offline

#2 2011-03-23 13:41:19

Nop
Moderator
Registered: 2009-01-26
Posts: 2,733

Re: 50 km x 50 km "Chunks"

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


Nothing is too difficult for the man who does not have to do it himself...
Projekte: Reit- und Wanderkarte mit Navigation - Kartengenerator Map Composer - GPS Track Editor Track Guru

Offline

#3 2011-03-23 14:52:55

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

Nop wrote:

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.

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.

Nop wrote:

Die Chunks aus unterschiedlichen Updateständen sind ja nicht miteinander kompatibel.

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

Offline

#4 2011-03-23 15:18:42

SimonPoole
Member
Registered: 2010-03-14
Posts: 2,018

Re: 50 km x 50 km "Chunks"

wyo wrote:

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.

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

Last edited by SimonPoole (2011-03-23 15:19:06)

Offline

#5 2011-03-23 15:48:30

aighes
Member
From: Shanghai
Registered: 2009-03-29
Posts: 5,305
Website

Re: 50 km x 50 km "Chunks"

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.


Viele Grüße
Henning, developer of RadReiseKarte

Offline

#6 2011-03-23 15:51:18

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

SimonPoole wrote:

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.

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

Offline

#7 2011-03-23 16:04:33

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

aighes wrote:

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.

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

Offline

#8 2011-03-23 16:23:46

aighes
Member
From: Shanghai
Registered: 2009-03-29
Posts: 5,305
Website

Re: 50 km x 50 km "Chunks"

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.

Last edited by aighes (2011-03-23 16:25:30)


Viele Grüße
Henning, developer of RadReiseKarte

Offline

#9 2011-03-23 18:46:37

EvanE
Member
Registered: 2009-11-30
Posts: 5,716

Re: 50 km x 50 km "Chunks"

aighes wrote:

... 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)

Offline

#10 2011-03-23 19:40:40

speedpilgrim
Member
Registered: 2010-06-24
Posts: 107

Re: 50 km x 50 km "Chunks"

EvanE wrote:

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?


Deine eigene kleine Garmin-Karte - schnell, aktuell, individuell - µMap

Offline

#11 2011-03-24 10:41:40

ikonor
Member
Registered: 2010-11-08
Posts: 597
Website

Re: 50 km x 50 km "Chunks"

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

  http://googleblog.blogspot.com/2010/12/ … 0-for.html

Offline

#12 2011-03-24 10:45:12

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

speedpilgrim wrote:

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

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

Offline

#13 2011-03-24 10:55:12

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

aighes wrote:

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.

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.

aighes wrote:

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

Warum? Kannst du das nochmals erläuern?

Wyo

Offline

#14 2011-03-24 11:03:38

wyo
Member
From: Thalwil
Registered: 2010-08-04
Posts: 667
Website

Re: 50 km x 50 km "Chunks"

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

Offline

#15 2011-03-24 11:38:12

aighes
Member
From: Shanghai
Registered: 2009-03-29
Posts: 5,305
Website

Re: 50 km x 50 km "Chunks"

wyo wrote:

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

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.

wyo wrote:

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.

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.

wyo wrote:

Warum? Kannst du das nochmals erläuern?

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.


Viele Grüße
Henning, developer of RadReiseKarte

Offline

#16 2011-03-24 12:32:24

speedpilgrim
Member
Registered: 2010-06-24
Posts: 107

Re: 50 km x 50 km "Chunks"

wyo wrote:

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

Link: http://wiki.openstreetmap.org/wiki/User … ecial_Maps
Kachel-Server: http://openstreetmap.teddynetz.de/latest/osm
Kachel-Auswahl: http://ulrichkuester.de/OSM/CoordinateToOSMTile.html


Deine eigene kleine Garmin-Karte - schnell, aktuell, individuell - µMap

Offline

#17 2011-06-06 22:42:53

mapistanbul
Member
Registered: 2009-12-06
Posts: 1

Re: 50 km x 50 km "Chunks"

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

Offline

#18 2011-11-02 23:11:24

ikonor
Member
Registered: 2010-11-08
Posts: 597
Website

Re: 50 km x 50 km "Chunks"

mapistanbul wrote:

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.

Nachtrag der Vollständigkeit wegen:

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

Offline

Board footer

Powered by FluxBB