Hello, > issue: > Where they are missing, I would like to generated landuse=residential > automatically in these places by evaluating the strongly connected > graphs of residential-streets. > Where such polygons have been created by mappers they will be used > instead but there are too few of them to rely on them to be present. > > question: > Dies anyone have a good idea for an algorithm that could do this?
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: - We assume that every point which is less than a given distance (e.g. 100 m) from a residental road is residental and draw a line around that area. - Imagine the planet (or a smaller area) covered with equidistant scanlines along the latitudes (the distance between two scanlines e.g. 0.0001 degrees of latitude ~= 11,1 m). Now you add for every segment of every residental way all the intervals of points on each scanline that are less than 100m from any point of that way (simplified: take into account only the endpoints of the segment and the intersections with the scanlines - the inaccuracies won't matter compared to the scanline gaps or the projection correction). After the tool has taken the union of all those intervals, it spans a way from interval border to interval border - that's the desired polygon around the residental area. - the algorithm is n log n in the number n of intersection points, which in turn are linear in the number of scanlines or the total length of all residental roads. Regards, Roland _______________________________________________ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev