[Routing] Default speed limits / built-up areas (was: Re: generalized routing format - pre-computation)
nroets at gmail.com
Wed Oct 22 20:41:40 BST 2008
On Wed, Oct 22, 2008 at 8:15 PM, Sascha Silbe <
sascha-ml-gis-osm-routing at silbe.org> wrote:
> On Tue, Oct 21, 2008 at 01:28:38PM +0200, Nic Roets wrote:
> You type the name of the town, click to center, then type the name of the
>> street. The nearest occurrence will be the first result, so clicking on it
>> will take you there.
>> Implementation : Each wayType has a center point and zero or more "tag
>> values", for example the name. There's an alphabetical index of the names
>> well as a complicated algorithm for handling the case where two tag values
>> are equal by finding the nearest occurrence.
> So you calculate the distance for _all_ nodes matching the name and sort
> them by distance?
No. That will be too slow if the search strings is something like 'fuel'.
wayTypes also have a variable that is calculated on the fly that is the
Z-encoding of its center.
Where names are identical (according to the string comparison function
TagCmp()), the sort that creates the index falls back on the z variable.
When you search for 'fuel' it first finds the 'fuel' with the z variable
closest to your current location. Then it looks for other 'fuel's that
appears near this closest 'fuel' in the index. It takes the best 40 of
With the distance between the worst one and the current location as a
radius, we can draw a circle. This circle is covered by 4 adjacent
'z-squares' forming a larger square. With 'z-square' I mean an area where
the first n bits of the latitude and longitude are constant. So the
algorithm then iterates through each of the 4 z-squares in the 'fuel' part
of the index to find the best ones.
I guess to find the best 40 'fuel's it will typically calculate 200
> The US makes up more than half of our "planet".
> Your point being?
My point is that optimizing for Europe is not a priority.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Routing