[OSM-dev] multipolygons/areas - consistency vs scalability vs topology

[Ben Supnik]

Hi Frederik,

> If we do this the classic way - "something built of something" - then
> we'd have to have at least four levels to do that. In today's terms, we
> could have
>
> Continent (Multipolygon Relation) e.g. "Europe"
> --> has many -->
> Coastlines (Superway Relation) e.g. "France's Atlantic Coast"
> --> has many -->
> Coastline Fragments (Way)
> --> has many -->
> Nodes

My initial reaction to 'build something with something' was panic - more 
complexity in my processing code, but my own fear aside, build something 
of something might be reasonable.

But...from my perspective the mixing of geometric and non-geometric 
information using relations right now is problematic.  My thinking is:

- If we want a geometric "container" to _not_ be broken, we need to have 
pretty much _all_ clients be aware of it and be able to present it. 
(E.g. "hey user, I don't know _what_ this 'park' thing is, but it's an 
area and it's right there, and it will look like a triangle, not a quad 
if you delete a node".)

- Since relations might be geometric or not, a client program can't 
display a relation sanely without knowing whether semantically the tags 
on a relation 'make it' geometric.

- The people applying the tags probably had some idea of what they were 
trying to do, so they could have picked a geometric or non-geometric 
aggregating object at the time.

In other words: not only would I like to see relation type=multipolygon 
be replaced with 'area', but _if_ a super-relation of ways is desirable 
for a "long way" then I would like to see a "composite" object, whose 
definition is basically "I have the geometry of all of the geometry 
inside me."  (So a composite of points is a point cloud, a composite of 
ways is one or more longer ways.)

> Personally I have always argued in favour of multipolygons built from
> superway relations (indeed I am of the opinion that everywhere you could
> possibly use a way, you should also be able to use a superway relation
> instead, including arbitrary levels of cascading superways), but this
> idea has not been widely picked up yet.

There is one other thing you'd be able to do if there was more hierarchy 
in the system: you could build an area of areas.  This would mean that a 
large area could be built of _area tiles_ rather than simply having a 
nicely cut up outline.

> Among the current ideas for areas on the wiki, one would effortlessly
> scale up to continents:
> http://wiki.openstreetmap.org/wiki/The_Future_of_Areas/Tagging_Outlines
> - this is basically a generalisation of what we currently do for
> coastlines, but of course entirely different from the classic modelling
> of areas.

It scales up well as a data model, but it's problematic for clients in 
two ways:
- You need to grab an insanely huge amount of data to know if an 
interior point is inside or outside.  E.g. given a point in the middle 
of no-where within a bounding box region with no coastlines...am I land 
or water?
- A simple break in the coastline causes a leak...having to "find the 
nearest coastline" is, IMO, another level of processing expense.  That 
is, it's one thing to parse complex correct data, it's another to have 
to have all clients repair broken data on the fly in the same way.

I'm not saying this is a good idea, but ... areas of areas would allow 
you to build the ocean out of fixed size tiles, and each tile would be 
small enough to scale for clients.

> There's at least one idea on the wiki that is very much unbreakable:
> http://wiki.openstreetmap.org/wiki/The_Future_of_Areas/Triangles - sadly...

Yes, hard to break...but also hard to edit, since the triangulation is 
sort of a 'deconstruction' of the more complex area.  I suppose a client 
could reconstruct the area, edit, then deconstruct it again.

> This is not a unique feature of relation-based multipolygons. Even a
> plain simple way that looks innocent enough
>
> <way id="1">
> <nd ref="1" />
> <nd ref="2" />
> </way>
>
> could turn out to have an invalid geometry when you look at the contents
> of its referenced entities.

True, but (and I see OSM through a very narrow prism, so if I'm only 
seeing a small, skewed subset of use/data, please yell at me) it seems 
to me that this kind of breakage is a different _category_ of breakage 
than what goes wrong with multipolygons.

That is: when there is a 'child editing error' of a way, the result is a 
new way that can usually still be rendered* but would be in the wrong 
place, a fairly obvious error in an editing client.

When there is a 'child editing error' of an area, the result is that we 
may not even be able to visualize the area because the entire notion of 
'inside' and outside' has been broken.

> Enforcing valid topology on multipolygon relations is too expensive in
> terms of computing power. The validity of the resulting polygon would
> have to be checked whenever a single node is moved that is part of one
> of the constituting ways.

I agree with that...and it's what makes me wonder whether the current 
scheme tries to do too much by allowing sharing and linking.  But it's 
hard to imagine removing those features without removing a lot of 
functionality.

> Any halfway sane contribution to this discussion is welcome. If you're
> in the mood, why not distil some ideas from your post into
> http://wiki.openstreetmap.org/wiki/The_Future_of_Areas/Issues_for_Solutions.
> Also, I think the topic could benefit from some clearly defined "use
> cases", i.e. we could simply write down a number of common uses for
> areas in OSM and then rate each of the proposed ideas against how well
> they work for each use case.

I will put some 50% sane use cases up on the Wiki. :-) :-)

cheers
Ben