advice needed: efficient approach to find streets that are close to a given point

Giganews Newsgroups
Subject: advice needed: efficient approach to find streets that are close to a given point
Posted by:  busnet (goog…@00l.de)
Date: Thu, 12 Jul 2007

Hi.
I've got the following problem: I have a huge xml-file that represents
a street map of a city. Each street is stored as a couple of
coordinates (start, end and all the turns).
I process that file and try to find those streets that are close to a
given point. So what I do is calculate the distances to EACH street
segment (using linear algebra algorithms, that is, constructing the
vector from two points and computing the distance from the given point
to this vector).
Do you have any ideas how to speed up the process of finding the
nearest street(s)?
I tried to consider only those streets whose endpoints are within a
certain range from the given marker-point, but it was not considerably
faster and if there was a street thats very long and straight the
endpoints may be far away, but the street itself could be quite near.

Any help is appreciated!

Replies