Search Canadian Postal Codes within given Radius (using Longitude & Latitude)

Hello, I want to be able to implement a search, where it returns all Canadian Postal Codes, that is within a given Radius of another Canadian Postal Code.
Before I do so, I'd like to hear some opinions from experienced professionals, about the correct design.
I find that my way is a little overkill or very brute, (or maybe I'm actually right, i need confirmation)..

------------------------------------------------------------------------
----- Given:
- Using Asp.net 2.0, C#

- Sql Server 2005

- An import file with all postal code with longitude and latitude in the following format:
Code / Longitude / Latitude
(ie, L3M 2Z9 / 2001245 / -45754)

- Formula to calculate 2 points on Earth:
6371 km * cos-1(cos(Long1-Long2)cos(Lat1)cos(Lat2)+sin(Lat1)sin(Lat2))
6371km is the Radius if Eath.

- There is almost 1 000 000 postal codes in Canada.
------------------------------------------------------------------------
----- Specs & Requirements
- User enters a Canadian Postal Code and a Radius range (km), all Postal Code within that range shall be displayed.

- The search query must perform better than 1 second, the lower the better

-----------------------------------------------------------------------------------------------
---- My initial Approach:

So I hope it's clear up to here.
Now how do I do this?
Let me tell you what I was originally thinking of doing. It's the most straightforward concept you can think of. Import all, and compute all at each search:

- Import the whole import file to Sql Server Database, where the table has 3 fields:
PostalCode, Longitude, Latitude

- When user press Search (with Postal Code and Radium (km) given)
The query would look something like this: (Parameters: ~PostalCode~, ~Radius~)

Select t1.* from tblPostalCode t1, tblPostalCode t2
where (6371 km * cos - 1( cos( t1.Longitude - t2.Longitude) cos( t1.Latitude) cos( t2..Latitude) + sin(t1.Latitude) sin(t2..Latitude))) <= ~Radius~
and t2.PostalCode = ~PostalCode~

-----------------------------------------------------------------------
----- My Concerns
I haven't dont this yet. But I estimate that this query would take forever
There is almost a million postal codes in Canada. Not to mention it might extend to Us Zip code in the future, but let's put that aside for now.
In my query.. it would have to compute that formula a million time. I think it's a bit dumb.

What do you think? Is there an official way to do this? Maybe another DB design, with some pre-calculation/work at Import instead? I can't have user wait for more than a second per search.

You could limit the data it has to search through by matching on the first letter of the postal code since each province would be different. That would cut you down to only having to do the calculations on a few hundred thousand. You may want to include bordering provinces, but no need to do calculations on BC if you are looking in Ontario.

0

chshwongAuthor Commented:

Thanks FJS159

I'm sure filtering province through first letter would already be a great start.
Already around 10 times less comparison.

I'm not an expert in cartography however, looking at it logiacally, imagine all your postcodes laid out on a grid. Write the XY grid references next to the postcode such as: postcode1, x, y. postcode2, x, y. etc.

Then, you could pick any 2 postcodes say, pc45, 23.45, 98.06 and pc4023, 601.34, 994.03 and calculate their distance using pythagoras' thereom where the right-angled triagle ABC = A:(23.45, 98.06), B:(601.34, 994.03) and C:(577.98, 895.97) where C is x2-x1, y2-y1. The distance is AB (the hypotenuse).

To find the relative distances of other postcodes, you simply read down the list fetching a postcode's XY coordinates, calculate C and find AB. If it falls in range then add the postcode and distance to your target list. By noting the gradient of AB you could also pinpoint it's relative position.

Finally, you could limit your search to fall within a limited range. The limited range is (x1 + or - range) for x2 and (y1 + or - range) for y2.