> 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 _______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
