computing distance

[Shawn Anderson]

I have a customer who wants to have a "find the nearest dealer" function on their website, where the user would put in their address and the page would return dealers within X miles of their location.

My initial thought is to outsource the computation to someone like google maps or yahoo, assuming that can be done.

Otherwise, how could that be done in house?
Is there a programming library somewhere that does that?

[Shawn Anderson]

I found this

http://www.alk.com/pcmiler/web-services.asp

You have to call to get a price. If you have to ask how much it costs......

[John R. Heathcote]

Shawn,

Are you looking for a direct line of sight measurement, or a shortest route/traveling salesman solution?

JR

[Shawn Anderson]

Traveling distance.

For instance, a customer is online looking for a widget and wants to know where he can go buy one. He puts in his address (or maybe even just zip code) and it gives him a list of the top 3 (or 5, etc.) closest stores that carry the widget.

[Emil Menzel]

Try asking Google -- dealerName myZipCode
It worked for the 2 dealers I tried just now, & has usually worke before.

Google Mobile version for iphone will even look up your GPS coordinates for you, & do even better.

[John R. Heathcote]

Shawn,

Traveling distance.

This being the case you might want to look at various "shortest path" algorithms. These algorithms are doable, but they will probably require some sort of mapping files (preferably with spatial data in geodetic coordinates, or UTM) for the area in question to show the route to the store, possible store inventory or access to such an inventory to help narrow the search.

For instance, a customer is online looking for a widget and wants to know where he can go buy one. He puts in his address (or maybe even just zip code) and it gives him a list of the top 3 (or 5, etc.) closest stores that carry the widget.

This sounds like a simple proximity search and in this case could be accomplished through a direct line of sight computation. Get coordinates of the user, and target stores and use a^2 + b^2 = c^2. Even this method might require some sort of mapping or access to same that could provide coordinate data of the user's present location in comparison with possible target stores. Very important, whatever method is used to generate coordinate data, they should use the same coordinate system. Converting between various coordinate systems/datums can be very messy.

[Eric Pearson]

Shawn --

It seems like this thread is talking about two different things:

1) Using an external program/database that has detailed data about streets (such as Google Maps) to calculate an exact route and the exact travel distance.

2) Estimating the relative distances, using real-world logic.

John said "a^2 + b^2 = c^2" but that only applies in a metro area that has a north/south and east/west grid of roads. I live in an area with lots of lakes and rivers, so we tend to use the phrase "you can't get there from here".

What you really want to provide to the end-user is the relative distances to the various stores, right? "Which one is closest to me?"

Blunt Force solution: Take the spherical coordinates of the from/to locations, and calculate the distance. Forget Pythagoris, simply double it. Assume the worst-case situation that the roads aren't ideal. Then list the locations in descending order.

If a web-site visitor sees that the nearest store is 5 miles away, and it's really only 3.5 miles by road... will they complain?

Just MO.

-- Eric

[Scott Slater]

If you can get the LAT/LON coordinates for each ZIP in your area, and then that of the dealer, you can calculate the distance and direction between the points.

[Michael Mattias]

Just include a link to MapQuest or Google maps. You can get not only miles, but driving directions as well.

And if it's not the "best" route? Blame Mapquest.

[John R. Heathcote]

Eric,

John said "a^2 + b^2 = c^2" but that only applies in a metro area that has a north/south and east/west grid of roads.

That formula applies anywhere, not just in urban locations, even though it is 2D.

I live in an area with lots of lakes and rivers, so we tend to use the phrase "you can't get there from here".

Could be a valid point. I live in the mountains

Blunt Force solution: Take the spherical coordinates of the from/to locations, and calculate the distance.

Why use spherical coordinates? If the distance is, say, 10 miles the correction for the curvature of the earth is for all practical purposes negligible. Besides, the spherical coordinate method assumes the mapping coordinates in the data base are very accurate, to the nearest cm, and most mapping data bases are not that accurate.

My contention is if you show the user a map with a series of circles on it representing the various 2D distances, where the center is the users present location and then highlight the stores in question they can visually determine from the map which store is closer and more convenient for them to visit and how to get there.

[Scott Slater]

If you are working in a single metro area, then why not create a grid (2d array) of zipcodes x by y with the distances in between stored in the grid.

   +     zip1    zip2   zip3 ...
zip1      0        8      2
zip2      8        0      9
zip3      2        9      0
...

Once you have your data (can get it from mapquest), as long as it's not alot of data, you can easily determine rough distances based on end users zipcode and the known zipcodes of store locations.

[Paul Purvis]

Michael most always cracks me up.

I thought i saw something on google where you could get long/lat of an address. If that is true, why not predetermine those coordinates ahead of time for each location and just get the address or zipcode of where the customer is and compute it. I saw some math on it a while back. It might have been at some wifi web site location where somebody was computing distance. I believe it was at http://wifi-plus.com

After going there check out their webpage.

http://www.wifi-plus.com/contactus/directions.html

Seems they are using icservices.com.

You might want to look at the Dunkin Donuts website. No we do not have one but it seemed like every street corner did when i was up northeast a few years ago.
Just did a search on their site and it says 126 locations near Providence. RI. Wow.

[Paul Purvis]

here is a web page on some distance math Shawn

http://www.mathforum.com/library/drmath/view/51711.html

[Paul Purvis]

Here you go Shawn.

the google stuff

http://code.google.com/apis/maps/documentation/services.html

a while back, i wanted to verify an address in databases.
I wrote a program that the USPS did not let me run against their database.
We are into financial business. Funny how they thought because we were not a retail outlet or a web site store we where not allowed to use their service. This was pure you know what by government to aid one type business but not treat another business equal to lower losses and improve mailing standards to reduce errors, NO WONDER everybody is doing email and we are not far behind.

[Greg Lyon]

Shawn,

Here's one I wrote. It's geared toward Amateur (Ham) Radio and aiming directional antennas, but the code may be useful for what you want to do. It determines the direction and distance between two latitude/longitudes.

http://www.powerbasic.com/support/pbforums/showthread.php?p=170820#post170820

[Shawn Anderson]

"Which one is closest to me?"

correct. I'm not giving directions, just a list of who's closest. If I'm off a little that's ok.

I never even though about using longitude and latitude. I'm sure that would work except the end user will probably put in a zip code, which I'd have to convert to lat/long somehow.

I'm leaning towards the google resources.

Some great ideas here.
Thanks!

[Michael Mattias]

> except the end user will probably put in a zip code, which I'd have to convert to lat/long somehow.

Zip codes won't always help if you are talking "local" locations.

For example, I live on the very edge of 53402 (Racine) . My closest 'something' is often in 53108 (Caledonia).

(I vote in Caledonia, but the USPS insists it's Racine).

MCM

[Paul Dixon]

MCM,

I vote in Caledonia, but the USPS insists it's Racine

So you list your location as Racine to avoid angering the postal service as angering the state is less troublesome?

Paul.

[Scott Slater]

I never even though about using longitude and latitude. I'm sure that would work except the end user will probably put in a zip code, which I'd have to convert to lat/long somehow.

That is what I suggested in an earlier post in this thread, but as Michael and others have pointed out. Using zipcodes is not enough in many localities. LAT/LON coordinates for a particular ZIP are usually centralized either at the post offices location, or town center. You would need to get multiple coordinates for a given area, and then go by house number and street. At this point something like google maps might be the best solution, as I believe that you can plot your own points (stores in your case) on the map for the end user to see.

[Michael Mattias]

You can put "Houston TX " on the envelope and it would get here as long as the street address is correct and the ZIP code were "53402-2119."

My sister tested this once, although not deliberately.

The 53402 Post Office USED to be located right in the geographic center of the ZIP code. Now it's about a half-mile west of here right on Four Mile Road... right on the northern border, just as I am. And you wonder why the USPS is running in the red?

As an offset, the new post office has 24x7 lobby area where you can buy stamps and mail stuff.

MCM