On Fri, 27 Feb 2009 11:18:49 +0100, Roland Olbricht <roland.olbri...@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 _______________________________________________ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
