JavaScript and Google Maps

[crmayer]

Hello,
I am working with the google maps API, running routes, which I have working just fine. What we are trying to do now is plot fuel stops along that route.
I am able to get fuel stops that are within the bounds (rectangle) that googles api provides, but when it comes to plotting only fuel stops that are within say 25 miles of the route I am running into problems. I do have it working, but I have to loop through each fuel stop and check it against each point on that line.
One of my test routes is a route from Nebraska to California, so there is like 7600 points along that route.

As you can see, the loop takes a long time, if I return 75 fuel stops, I have to loop 75 times, checking each one agaist the 7600 points.

I am breaking out of the loop if I find a distance within my threshold, but it is still taking too long.

First off, has anybody worked with something similar to this?

I have found some examples on the web, but they seem to call javascript that is not include in the web page, therefore I can not see it.

I am guessing there must be a way to narrow something down, whether it be the number of points along a the line/route, or the number of fuel stops returned.

Any suggestions?

Thanks so much.
- Chris

 

[Bong]

Well, I don't really know if this is faster, and it might need more horsepower than Javascript (maybe a Java applet) but consider this.

Over some interval you're comfortable with, let's say that the path can be safely approximated as linear. Then, instead of 7600 points, you have some smaller number of line segments. Each of the line segments is of the form, y=ax+b, computed from the end points.

Now, instead of comparing each fuel stop to all the points, you can compare it to the line. So, a point (fuel stop) has coordinates, x1 and y1 and you want to find the length, L, of the perpendicular from the line to that point. You use the expression for the line to compute the y-coordinate of the point on the line at x1. Likewise, you compute the x-coordinate of the point on the line at y1. [At this point you can probably come up with a means of discarding a fuel stop if it isn't appropriate to this particular line segment] Now you can have an "x difference", dx, and a "y difference", dy. The length along the line (hypotenuse), S, of the right triangle whose right angle is at x1,y1 is dx^2 + dy^2. After a little elementary algebra, the distance, L, from the fuel stop to the line is
L=sqrt(dx^2-c^2) where
c=S[red]+[/red]sqrt(S^2+dy^2-dx^2) or
c=S[red]-[/red]sqrt(S^2+dy^2-dx^2), only one of which will be real.

_________________
Bob Rashkin

 

[Bong]

Actually, they both should be real in the mathematical sense but only one will be valid (L must be greater than 0).

_________________
Bob Rashkin

 

[crmayer]

What I am doing right now is I am taking a point from that line every 25 miles (which is the distance parameter we are looking for).

I am then only compairing those points to the fuel stops. This is cutting down on the number of line points.

This is running now in about 5 to 10 seconds.