ich arbeite an einem Patch für JOSM bzgl. der Validierung von type=multipolygon Relationen (MP)
Dabei habe ich ein Problem mit dem Handling von doppelten Way-Membern. Nach meinen Verständnis des wiki (1) gibt es keine Möglichkeit, ein gültiges MP zu erzeugen, bei dem ein oder mehr Way-Member doppelt auftauchen, egal ob mit gleicher oder verschiedener Role. Ein möglicher Sonderfall wären “touching inner”. Jemand könnte auf die Idee kommen, den gemeinsamen Teil zweier inner als einzelnen Weg zweimal für beide inner zu verwenden, aber dann gäbe es jeweils drei Wege, die an den beiden Endknoten “ankommen” und das ist nicht erlaubt. Nach meinen Verständnis ist also so eine Relation mit doppelten Way-Membern nie ein gültiges MP.
Gibt es da irgendwelche Einwände?
Bitte auch für type=boundary, da die in ihrem Aufbau 100%-tig identisch sind. Ist ne historische Sache, wieso es da zwei Typen gibt. (*)
Es mag kleine Unterschiede in Josm geben, weil z.B. bei type=boundary ausser outer/inner nur bestimmte andere punktförmige Member (admin_centre, label) erlaubt sind, aber der Teil mit den geschlossenen Ringen sollte identisch sein.
Huch. Denkst Du da an Relationen als Member eines MP?
(Mit “type=boundary” hab ich mich noch nicht beschäftigt. Daher die dumme Frage:) Kann man die “type=boundary”-Relationen als “Abkürzung” für zwei Relationen betrachten?
Ein MP mit nur “type=multipolygon” und allen “inner”- und “outer”-Membern.
Eine Eigentliche-Boundary-Relation mit den Tags, den anderen Membern und dem MP als “Area-Member”?
Wenn man das so sehen könnte, dann wäre der gemeinsame und der eigene Regelteil für boundaries klar getrennt und nichts müsste doppelt beschrieben oder geprüft werden…
Sehe ich nicht ganz so. Bei MP gibt es - soweit ich weis - keine role=subarea. Bei boundaries wird das aber schon/noch intensiv genutzt.
Umgekehrt ist im wiki für MP kein role=label erwähnt, wird aber durchaus benutzt.
Das Beispiel mit Ecke Jungholz ist interessant. Nach meinem Verständnis ist https://openstreetmap.org/relation/16239 ungültig, weil
sich da mehr als 2 Wege in einem Node treffen. Muss man das bei boudary als Spezialfall zulassen? Oder meinst Du, dass wäre auch bei MP in Ordnung?
Jo, subarea hab ich vergessen. Es geht mir allerdings NUR um die inner/outer Member, die ja letztendlich die Fläche beschreiben. Dafür sollten die Regeln für type=multipolygon und type=boundary identisch sein.
Type=multipolygon und type=boundary sollten hier immer identisch behandelt werden. Ich kann mir jederzeit Multipolygone (landuse?) vorstellen, die ähnlich aufgebaut sind.
An dieser Ecke haben sich schon alle möglichen Leute die Zähne ausgebissen - ich auch. Bitte ändere dort erstmal nichts, ansonsten sind die AL2 von DEU und AT defekt. Osm2pgsql als Preprozessor OSM->Mapnik hat da keinerlei Probleme, das in OGC-konforme Polygone umzuformen.
Ich wäre aber wirklich froh, wenn du da Licht ins Dunkel bringst. Das Thema der OGC-konformen Geometrien dürfte dir ja hoffentlich bekannt sein.
nicht “offene Linienzüge” sondern “offene Wege”. Das ist hier der Fall. Die Linien dürfen sich zwar auf diese Art begegnen, aber es dürfen maximal 2 dort enden. Anders gesagt: wenn eine Linie aufhört muss immer klar sein, mit welcher Linie es es weitergeht. Anders gesagt: es darf nie mehrere Möglichkeiten geben, geschlossene Linienzüge zu bilden. Ansonsten ist die Flächenberechnung und die Berechnung der “drinnen”/“draußen”-Eigenschaft für vorgegebene Punkte grauenhaft.
Als ich vorhin drauf geschaut habe, trafen sich an dem Knoten 4 Wege, keiner geschlossen. Nach den Regeln im engl. wiki wäre es also ungültig. Wenn ich die Die OGC-Regeln richtig verstehe, sagen sie nicht ganz das gleiche: :" The boundaries of any two elements may touch, but only at a finite number of POINTs." Bin kein English Experte, aber aus meiner Sicht sagt das nichts darüber aus, wieviele “elements” sich in einen bestimmten “POINT” berühren dürfen.
Ich bin bisher auch immer davon ausgegangen, dass ein inner an keiner Stelle einen outer Ring berühren darf, geschweige denn schneiden.
Das finde ich aber so nicht im wiki, und aus den OGC Beispielen werde ich nicht schlau. Habe ich da eine falsche Vorstellung?
Ich hoffe, du nimmst keine OGC-Beipiele von OSM-Wiki-Seiten. Die könnten schon mißverständlich oder gar falsch sein.
Das Problem ist wohl, dass OSM “älter” ist als OGC. Wir haben einige “geometrische Konstruktionen”, die es so nicht im OGC gibt. Z.B. bedeuten gleiche Begriffe wie “Polygon” in OSM und im OGC völlig was anderes.
Unser Multipolygon mit einem Outer und eventuellen Innern ist bei OGC ein einfaches Polygon. Und unser Konstrukt, einen Ring aus mehreren Teilstücken aufzubauen, ist OGC zumindest fremd.
Ich erkenne aber zunehmend Pläne das OSM-Datenmodell an OGC anzunähern. Der type=area wäre ein Schritt in diese Richtung - aber ob der je mit der API08 gegangen wird? Und wann?
Ich kenne mich mit OGC nicht gut aus … ich komme eher von der Mathe-Seite.
Aber wenn ich es richtig verstanden habe, dann tritt das beschriebene Problem innerhalb von OGC nicht auf. Die machen das in zwei Schritten: Der äußere Rand ist in OGC ein Ring-Objekt und das ist wiederum eine bestimmte Reihenfolge von (sagnwama) Ways. Wir schreiben die Ways aber ohne Reihenfolge einfach alle als “outer” rein. Deshalb müssen wir verlangen, dass man daraus eindeutig einen Ring machen kann. (Nicht perfekt eindeutig … es ist OSM egal, ob rechts rum oder links rum und wo Anfang/Ende ist). Aber wenn irgendwo vier Wegenden aufeinandertreffen, dann kann man zwei signifikant verschiedene Ringe bilden.
Das Problem liegt aber nicht an OGC. Wenn wir direkt die mathematischen Algorithmen zur Flächenberechnung von Polygonen benutzen, dann bekommen wir je nach Reihenfolge der Wayaneinanderfügung unterschiedliche Flächenmaße.
Na ja, ursprünglich wollte ich nur etwas an der Performance der Tests verbessern, siehe auch http://forum.openstreetmap.org/viewtopic.php?id=55275
Die meisten dort genannten Probleme sind unterdessen behoben bzw. deutlich kleiner, aber bei der Arbeit an den Patches ist mir aufgefallen, dass einige Fehler mit dem vorhandene Code gar nicht gefunden werden können. Beispiel: Zwei Dreiecke, die so übereinander liegen, dass kein Knoten innerhalb der Schnittfläche liegt. Die Schnittfläche ist dann ein Sechseck. JOSM stört sich bisher nicht dran.
Dann habe ich den Test total umgeschrieben und jetzt bekomme ich (natürlich) auch an Stellen Warnungen, an die ich vorher nicht gedacht habe, insbesondere eben wenn sich inner und outer Ringe berühren.
Dies kann auf verschiedene Arten passieren:
entweder haben sie dort auch einen gemeinsamen Node oder
der Node eines Rings liegt genau auf der Linie eines anderen Rings.
Aus meiner Sicht ist beides eine Warnung wert, auch wenn es beim Rendern nicht stört. Richtig?
Danke, kannte ich noch nicht, muss ich mir noch mal genauer anschauen.
Wie oben erwähnt war ich zunächst eher an der Performance der Tests (und an der Darstellung des Ergebnisses) interessiert.
Geschichte dazu:
Vor einiger Zeit habe ich mal mit dem “Multipolygon View” von OSMI (2) experimentiert und habe mich geärgert, das in OSMI die problematische Stelle markiert wird aber JOSM “nur” die beteiligten Wege als Problemfälle markiert. Wenn dann beide Wege ~ 2000 Punkte haben und eng ineinander verschlungen sind (ist z.B. in Japan durch Importe oft der Fall), dauert die Suche in JOSM ewig, mit einem OSMI Layer geht es viel flotter, aber OSMI wird auch nur alle paar Tage aktualisiert.
Ich habe dann für JOSM ein Ticket eröffnet (1) und versuche seitdem, die Spezialfälle aufzudröseln.
Ist immer noch “Work in Progress”.
Ich kenne die Projekte selbst nicht im Detail und bin nicht so tief in der Thematik drin, dachte halt das könnte evtl. relevant und hilfreich sein:
fixing-polygons-in-osm: scheint eine neue Initiative zu (Multi-)Polygonen von Jochen Topf zu sein, die er vermutlich erst in einem Area Workshop zur SotM vorstellen und diskutieren wird
osm-testdata: Beispiele für gültige und ungültige Multipolygone + Testdaten für die Prüfung
Ja, das ist ein bisschen das Dilemma für Open Source Entwickler - überall wo man vorbeikommt stößt man auf neue Baustellen, um die sich mal jemand kümmern müsste (und man hinterlässt natürlich auch selbst welche).
Dies Problem holt mich gerade wieder ein: https://josm.openstreetmap.de/ticket/18861
Im engl. Wiki steht bei https://wiki.openstreetmap.org/wiki/Relation:multipolygon#Valid_Multipolygon_conditions
zuerst ganz klar, dass es nicht erlaubt ist, dass sich mehr als zwei nicht geschlossene Wege den gleichen Endpunkt teilen, dann wird aber wieder eingeschränkt:
“(Exception - points shared by an even number of unclosed ways might be part of touching inner rings which is ok.)”
Leider gibt es aber keinen Hinweis darauf, wie die Ringe in so einem Fall zu bilden sind.
Noch schlimmer: Wenn es eine Möglichkeit gibt, da mehrere durchgezogene geschlossene Linien zu bilden, dann gibt es immer mehrere Möglichkeiten und außerdem mehrere Möglichkeiten, nur eine durchgezogene Linie aus allen Teilen zu bilden. Diese Linien hätten dann mathematisch unterschiedliche Flächen auch wenn man für jeden einzelnen Ring den Betrag bildet. (Eine symmetrische Acht hat mathematisch die Fläche 0, wenn man sie auf die übliche Art malt.) Mit dieser Ausnahme wird also die normale Flächenberechnung von MPs kaputt gemacht, denn mit dieser Regel müssten komplizierte Operationen bei jeder Flächenberechnung durchgeführt werden, die man sonst nur beim Prüfen von MPs braucht.
Wenn man eine Fläche in Form einer 8 hat, dann kann man das einfach als zwei Flächen sehen, die sich an einem Punkt treffen, das wäre okay. Wenn man aber der 8 so folgt, wie man sie zeichnen würde, also so als Schleife, dann kommt ein ungültige Fläche (mit Selbstüberschneidung) raus. An einem Punkt können beliebige viele Grenzen zusammen kommen, eine Kleeblattform ist erlaubt. Man muss dann aber immer schauen, ob man das auch sinnvoll zusammensetzen kann zu einem Objekt was global gültig ist. Das ist richtig schwierig und u.U. sehr teuer. Ich habe da ewig im libosmium rumgebastelt, bis ich das halbwegs hinbekommen habe und mein Algorithmus scheitert an sehr aufwändigen komplexen Multipolygonen, weil es einfach zu langsam wird. Davon gibts aber zum Glück nur eine Handvoll, alles merkwürdige Grenzen in den USA.
Bei Simple Features können keine zwei Grenzwege (“boundaries” in Simple-Feature-Sprache) übereinander liegen, das ist auf jeden Fall nicht erlaubt. Bei OSM geht das manchmal, bei den touching inner rings. Bei der Konvertierung muss man dann die Segmente der Ways einfach weglassen, die man doppelt hat, dann passt es wieder.
Ein wichtiger Unterschied zwischen OSM und Simple Features (OGC) (Multi)Polygons ist, dass Simple Features eine Richtung der “boundaries” vorgibt, während OSM das nicht vorschreibt. Dadurch sind OSM-Polygone schwieriger zusammenzusetzen, wenn an einem Punkt mehr als 2 Linien zusammenkommen. Bei OSM gibt es dafür die inner/outer roles, aber da kann man sich auch nicht drauf verlassen, dass die da sind und korrekt sind. Hier ist die Situation im JOSM aber ein bischen anders, als wenn man, wie ich, Multipolygone sozusagen nachträglich extrahiert und zusammenbaut. Beim Validieren in JOSM kannste ja prüfen, ob inner/outer richtig gesetzt sind und wenn nicht, dann die Validierung ablehnen. Ich kann das nicht mehr nachträglich, weil es einfach zu viele Multipolygone gibt, wo inner/outer nicht gesetzt sind oder nicht stimmen. Ich ignoriere also inner/outer einfach und gehe rein nach der Geometrie. Im JOSM kannste nach inner/outer zusammenbauen und wenn dabei nichts gültiges rauskommt, dann einen Fehler melden.
Bei JOSM geht es um drei verschiedene Programmteile:
Beim Laden der Daten muss möglichst schnell ermittelt werden, wie ein MP gerendert werden soll. Da werden zur Zeit die Roles herangezogen und dann die jeweiligen Wege zusammengeklebt. Dabei wird auch die Reihenfolge der Member beachtet. Wenn dabei Überschneidungen rauskommen, stört JOSM sich nicht dran.
Im Relationseditor ermittelt ein komplett anderer Algorithmus, ob bzw. wie die Member in der gegebenen Reihenfolge Ringe bilden.
Die angezeigte Ringe haben stimmen also nur evtl. mit denen aus 1) überein.
Bei der Prüfung von Relationen wird das Ergebnis aus 1) diversen Plausibilitätsprüfungen unterzogen. Im Moment kommt dann meist eine Warnung, dass sich Ringe selbst schneiden, und an denen stört sich der Ersteller des JOSM Tickets 18861.
Wenn jetzt ein Mapper mit dem Relationseditor versucht, die Warnung loszuwerden, dann verzweifelt er wahrscheinlich
Wie Jochen schon sagte: Es ist nicht trivial, aus einem Satz von Wegen ein gültiges MP zu basteln, wenn man diese vielfach verwendeten Punkte erlauben will. Das Bild mit dem Kleeblatt hatte ich heute auch schon im Kopf
Ein anderer Ekel-Fall wären alle schwarzen Felder eines Schachbretts, jeweils aus 2-Punkte-Wegen zusammengesetzt, mit Rolle outer in einem MP. Mit Brute-Force Suche läuft man sich da vermutlich tot, wenn man Überschneidungen vermeiden will.
Wir haben in JOSM aber einen Algorithmus, der das relativ flott zusammenpuzzelt. Der wird bei der Funktion “Überlappende Gebiete verbinden” verwendet. Da werden nämlich tatsächlich die geschlossenen Wege zuerst an allen Berührungspunkten getrennt und dann so zusammengesetzt, dass keine Überschneidungen da sind. Ganz nebenbei werden dabei auch die Überlappungen entfernt.
Die Grundidee ist dabei, dass man immer dort, wo mehrere Wege anknüpfen, denjenigen wählt, der den spitzesten Winkel im Uhrzeigersinn bildet. Wenn man auf diese Weise an eine Stelle kommt, wo man schon mal war, dann hat man einen geschlossenen Ring, den man “rausschneiden” kann.
Wegwerfen wollen wir bei den MP natürlich nichts, Fehler im MP sollen ja sichtbar sein. Mal sehen, ob ich das hinbekomme.
@Jochen: Die Problemfälle aus den USA würden mich natürlich interessieren. Kannst Du mal die ids posten?
Den Ansatz mit dem kleinsten Winkel habe ich auch mal probiert und das letztlich verworfen. Ich weiß jetzt aber auch nicht mehr, wie das genau war, ob ich es einfach nur praktisch nicht hinbekommen habe oder ob es da ein grundsätzliches Problem gab. Man muss ja auch immer aufpassen, dass einem die Numerik da nicht einen Strich durch die Rechnung macht bei sehr spitzen Winkeln oder so.
Wir haben also eine Datenstruktur mit dem Designfehler “mehrere Interpretationen möglich” und müssen in jedem verarbeitenden Programm die in sich widersprüchlichen mit großem Aufwand rausfriemeln um zu einer klaren Lösung zu kommen. Das ist kein guter Zustand. Es gibt ja nicht nur die hier genannten Programme.
Wir sollten endlich im API eine vierte Datenstruktur “Fläche” einführen, die die jetzigen Flächen “geschlossene Linie mit bestimmten Tags” und “Pseudorelation MP” ersetzt und zur dritten OSM-Flächenform “coastline” weitgehend kompatibel ist. (In der Datenbank wäre es nach wie vor eine Relation … nur mit einer internen Markierung) Dazu muss man nur die Rollen “inner” und “outer” durch “left” und “right” ersetzen (geben an auf welcher Seite sich das gemappte Objekt befindet). “coastline” ist dann nur noch ein Sonderfall desselben Konzepts bei dem die Rolle “right” immer gilt und die zusammenfassende Struktur weggelassen wird. (Das ändert natürlich nichts an den speziellen Problemen der Coastline, die sich aus der planetumfassenden Riesenstruktur ergeben)
