[OSM-dev] auto-generating landuse=residential polygon around highway=residential -streets
roland.olbricht at gmx.de
Fri Feb 27 10:18:49 GMT 2009
> 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.
> 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
- 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
More information about the dev