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

[Frederik Ramm]

Hi,

On 04/15/2011 04:16 AM, Ben Supnik wrote:
> - Is there any chance of having an area primitive so scalable that it
> scales all the way up to the major continents? Right now continents are
> sort of an exception - you need to go pull down the pre-processed
> coastline shape files because the data processing to build a continent
> or ocean is particularly non-trivial.

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


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.

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.

> - Is there any chance that we could have an area primitive spec so
> simple that it _can't_ be broken. (E.g. naively a list of list of nodes,
> which would be pretty hard to break unless a user intentionally wanted
> to trash it.)

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

> - Is the gap between 'simple' and 'huge' polygons so large that one spec
> doesn't fit all?

... it will be very hard to find something that can accommodate both 
"simple" and "huge". We might end up with two entirely different solutions.

> Finally, one more random thought: I think one of the things that makes
> relation-based multipolygons more fragile than the rest of the map (from
> a geometric standpoint) is that the consistency of a multipolygon ring
> depends on the _contents_ of _referenced_ entities.

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.

> E.g. For my
> perimeter to be sane, way 1 and way 2 _have_ to share a common node. The
> editor of way 1 may have no way of knowing that (since way 1 is self
> consistent even if one of its end nodes is deleted, removing one line
> segment), but the multipolygon is now broken.
>
> (This is a different case than deleting a node that is referenced in the
> way, where there might still be a way to guess what the way should look
> like.)

Many of us are indeed working on code that does precisely this - guess 
what the polygon should look like - in the error cases you describe. For 
example, osmium (http://wiki.openstreetmap.org/wiki/Osmium) has code 
that will automatically connect a pair of nearest dangling nodes, and 
also remove small self-intersections to salvage otherwise invalid 
multipolygons. As far as I know, osm2pgsql and imposm also do limited 
polygon repair.

> The implication might be that building polygons out of ways is what
> makes polygons fragile - it allows for clever topology-like features but
> without an API that _enforces_ topology-like rules, it's easy to break
> stuff.

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.

> Okay, I think I'm done now ... no real point here ... frankly I'd be
> happy with nearly any area-like feature in a future API revision.

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.

Bye
Frederik