[OSM-dev] auto-generating landuse=residential polygon around highway=residential -streets

[Roland Olbricht]

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