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

[Roland Olbricht]

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

In this scenario, it might be worth a thought to do the preprocessing on the 
server. The polygon coordinates for the areas will be much less data than the 
roads itself. And on the server, preprocessing of the residental areas for 
the 4 LODs is rather cheap.

> * This will never shrink a polygon, however I think the impact by this
> limitation is neglectable.

I think this can and should be stated as an assertion: shrinking polygons will 
get quite complicated. And in the real world, a residental area is unlikely 
to suddenly disappear. Only in the rare case that a road has been accidently 
tagged as residental, a shrinking would be required. And this can be done by 
a manually triggered reset of the data.

> 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
[...]
> 3 => merge the polygons onto one and join the 2 relations

This might get expensive: as one relation would disappear, you have to update 
the entries in the node->relation index for all the nodes of the disappearing 
relation. If you are primarly interested in drawing the areas on a map, it 
might be cheaper to keep two distinct polygons even if they are overlapping. 
Given the assumption that we never shrink polygons, there is no harm in 
forgetting that a certain node belongs to more than one residental area.

[...]
> 4 => create a new polygon and a relation with all residential roads
> contained and the surrounding polygon

That also might get expensive. But I don't see any way to circumvent this 
operation.

> and if it is 
>   related to a surrounding landuse=residential.

I would expect that this is the essential part of the algorithm: depending on 
the datastructure for the areas, it might be expensive to find the area 
something is contained in. Do you already have a good datastructure for that 
operation? Depending on the amount of data, the aforementioned index might 
work or just be too slow. I'm using stripes with a width of 1 degree of 
latitude at the moment - this is reasonably working, but looks like a 
bailout.

Assumed we are anyway in the case of few LODs, a much simpler approach might 
be appropriate: Consider the map as a bitmap of pixels, for example with the 
doubled resolution of the LOD exactness. Then one can just mark every pixel 
that is touched by a residental road as residental. A datastructure for 
pixels will be much simpler than a datastructure for polygons or even 
relations - for pixels, you can simply use the quadtile index of a node to 
check whether there is a pixel that contains the respective node.

Roland