[OSM-dev] auto-generating landuse=residential polygon around highway=residential -streets
roland.olbricht at gmx.de
Fri Feb 27 16:47:53 GMT 2009
> However I doing all such operations on the fly.
> e.g. the user already has a local map in LOD0-3 and chooses
> 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
> 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
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.
More information about the dev