[OSM-dev] auto-generating landuse=residential polygon around highway=residential -streets

marcus.wolschon at googlemail.com marcus.wolschon at googlemail.com
Fri Feb 27 10:41:56 GMT 2009


On Fri, 27 Feb 2009 11:18:49 +0100, Roland Olbricht
<roland.olbricht at gmx.de> wrote:

> What is the particular situation, i.e. what accuracy is necessary? A good

> starting point might be a scanline approach as for the 12-nm-brim, which
is
> a 
> matter of minutes for the entire planet but not very precise:

In LOD1 I don't care for +-10m, in LOD2 +-500m and in LOD2 +-10Km .

The scanline-aproach works fine if you have a complete map and
apply this preprocessing.

However I doing all such operations on the fly.
e.g. the user already has a local map in LOD0-3 and chooses
download->countryX.
First all nodes are handed to LODDataSet.addNode().
Then all ways are handed to LODDataSet.addWay().
Then all relations are handed to LODDataSet.addRelation().

Usually the map already present is much larger then the newly
imported part. Think of having half a continent on disk and
on the road downloading a small strip between start and target(s)
via a mobile phone before starting the route-calculation to update
the part of the map you will most likely be driving on 5 minutes later.

I therefor require the algorithm to work with incremental updates.
I do have fast, indexed access to:
* the residential road currently being added
* all nodes of the road
* all relations the road is a part of
* all relations and ways and relations of the nodes

Thus I can do something incremental like:
* check if an older version of the way added exists and if it is
  related to a surrounding landuse=residential.
1 => if so, enolarge the polygon if we cross it's boundary now and exit
* recursively get all connected residential roads
=> if we encounter one related to a surrounding landuse=residential.
2 => if so, enlarge the polygon if we cross it's boundary now and exit
=> if we encounter multiple related to different surrounding
landuse=residentials.
3 => merge the polygons onto one and join the 2 relations
* no existing poylgon was found
4 => create a new polygon and a relation with all residential roads
contained and the surrounding polygon

Notes:
* Case 4 should only happen with 1 residential road as the others have
undergone the same algorithm.
* I case 1,2,3 we usually do not visit all ways or nodes except the 1 or 2
polygons and the newly added roads
* This will never shrink a polygon, however I think the impact by this
limitation is neglectable.


Marcus





More information about the dev mailing list