On Wed, Oct 22, 2008 at 8:15 PM, Sascha Silbe < [EMAIL PROTECTED]> 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 >> as >> 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 these. 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 distances. > The US makes up more than half of our "planet". >> > Your point being? > My point is that optimizing for Europe is not a priority.
_______________________________________________ Routing mailing list Routing@openstreetmap.org http://lists.openstreetmap.org/listinfo/routing
