SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2000 Forums
 SQL Server Development (2000)
 Distance between zip codes
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

slacker
Posting Yak Master

115 Posts

Posted - 09/22/2004 :  03:14:42  Show Profile  Reply with Quote
Im writing an application that needs to find the distance between two zip codes and return only records that are within a certain radius. I have the formula's I need. I can imagine that this is a pretty resource intensive operation especially on result sets. Is there a good method to optimize complex math operations itself. I was going to write a udf called GetZipDistance AND IsInRadius that took the lattitude and longitude coordinates as parameters. I was also considering creating a table that stored the distances but it would have ended up being over a billion records :).

Edited by - slacker on 09/22/2004 03:15:36

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 09/22/2004 :  04:14:40  Show Profile  Reply with Quote
Could you calculate a x,y coordinate for each zipcode,
and only return the zipcodes were sqrt((zip1.x-zipn.x)^2+(zip1.y-zipn.y)^2) < radius ?

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */
Go to Top of Page

slacker
Posting Yak Master

115 Posts

Posted - 09/22/2004 :  06:25:49  Show Profile  Reply with Quote
Heres what I got working... Sql server laughed at it. Funny thing is I think it was losing the most speed from having to do a table scan.
This will get you pretty accurate results as far as distance goes. for doing a radius you would just check radius <= distance. The thing i was worried about was the mathematical functions. But.. I did a display execution plan and it said the computer scalar cost was like.. 4% of the cost of the query. and that was with 100 records.. ill at most pull 20-30 at a time. This will show miles.


declare @zip1 int
declare @lat1 decimal(18,6)
declare @long1 decimal(18,6)
select @zip1 = 92591
select @lat1 = Lattitude, @long1 = longitude from T_ZipCodes where zip = @zip1
select top 100
zip,

(DEGREES(ACOS(
SIN(RADIANS(@lat1)) *
SIN(RADIANS(lattitude)) +
COS(RADIANS(@lat1)) *
COS(RADIANS(lattitude)) *
COS(RADIANS(@long1 - longitude))
) 
)
) * 69.09
as distance

from T_ZipCodes


Edited by - slacker on 09/22/2004 07:54:06
Go to Top of Page

SamC
White Water Yakist

USA
3460 Posts

Posted - 12/02/2004 :  07:11:58  Show Profile  Reply with Quote
Just curious... what solution did you finally settle on for this problem?
Go to Top of Page

ehorn
Flowing Fount of Yak Knowledge

USA
1630 Posts

Posted - 12/02/2004 :  08:07:51  Show Profile  Reply with Quote
Have a look at:

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=30843&SearchTerms=zipcode
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/02/2004 :  17:06:38  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
there was another big question on distances between points (long and lat points). And there was some question on the number of comparisons that had to be made.

This may be slightly off topic, but you can make some very easy restrictions to approximate mileage boundaries. If for example you want a 20 mile radius from a given point, simply calculate the distance in a cardinal direction (North, East...) so that if long or lat were the same the other would have to change by x degrees


lets say that it is .250 degrees (just for simplicity)

using the origin point, lets call this (a,b), we can build three simply conditions to approximate the mileage restrictions without applying the calculation to EVERY single row!

Set @approxDegrees = .250

Where newPoint_a between (origin_a - @approxDegrees) and (origin_a + @approxDegrees)
and newPoint_b between (origin_b - @approxDegrees) and (origin_b + @approxDegrees)
and abs(newPoint_a - origin_a) + abs(newPoint_b - origin_b) < @approxDegress*1.5

this builds a range that looks like a square with the four corners cut off:

  ___
 /   |     |
 \___/


Just some thoughts I had as I was skimming through!!

Corey
Go to Top of Page

SamC
White Water Yakist

USA
3460 Posts

Posted - 12/02/2004 :  18:04:51  Show Profile  Reply with Quote
I'd figure this myself, but when there are math wizards out there... and this is entertainment anyway (I don't need to solve this problem)...

Here's the question...

Using the flat-earth approximation of Corey's, How large must the radius be to have an error of: (A) 1 mile and (B) 5% ?

Extra credit: (C) X miles and (D) Y%
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/02/2004 :  18:58:40  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
have a maximum error of a) 1 mile b) 5%

or

have a average error of a) 1 mile b) 5%

or

have a total error of a) 1 mile b) 5%

???


Corey
Go to Top of Page

SamC
White Water Yakist

USA
3460 Posts

Posted - 12/02/2004 :  19:03:35  Show Profile  Reply with Quote
Hey - good question. How about MAX?
Go to Top of Page

SamC
White Water Yakist

USA
3460 Posts

Posted - 12/02/2004 :  19:06:43  Show Profile  Reply with Quote
I'm going to take a guess. If the earth was perfectly round, and a flat approximation was used, 100 miles would give a 1 mile max error? It probably gets quadratically worse as the radius increases?
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/02/2004 :  19:28:10  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
oh and I also fixed the approximation...

the condition should be:
Where abs(origin_a - newPoint_a) <= @approxDegrees
and abs(orign_b - newPoint_b) <= @approxDegrees
and abs(newPoint_a - origin_a) + abs(newPoint_b - origin_b) <= @approxDegress*sqrt(2)

Thats much more accurate... I am working on the error approx... but I got dinner to eat

Corey
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/02/2004 :  20:41:06  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
Here is what I got for maximum error:

take the (+,+) quadrant of a unit circle which is defined by the function:
y = (1+x^2)^(1/2) where 0<=x<=1

also add in the approximation constraints:
x <= 1
y <= 1
y <= (2)^(1/2) - x

these equations generate a tangent lines about the unit circle at the following 3 points
(0,1); (1,0); ((2)^(1/2)/2,(2)^(1/2)/2)

Looking at this graph I determined that the furthest points from the origin occured on

y <= (2)^(1/2) - x when x=1 or y=1

Solving for the other you get the pairs:
(1,(2)^(1/2) - 1) ~ (1,.414214)
and
((2)^(1/2) - 1),1 ~ (.414214,1)

Using the formula for distance provided in the link


a = x/57.2958
b = y/57.2958

d = 3958.75*ArcTan(  (1 - (sin(0)sin(a) + cos(0)cos(a)cos(b))²)^½
                     -----------------------------------------------
                            sin(0)sin(a) + cos(0)cos(a)cos(b)        )

so

using the point ((2)^½-1,1): distance ~ 74.785381537492
using the point (0,1):       distance ~ 69.093197057399
which gives an error of:     distance ~  5.692184480093

error ratio is then: 69.093197057399/5.692184480093 ~ 12.138256814943

this means that for every x miles of range there will be (x/12.138256814943) miles of error

or error = x/12.138256814943

the error % is constant and would be ~ 8.2384%




Please let me know if I am way off base !!!




Corey
Go to Top of Page

SamC
White Water Yakist

USA
3460 Posts

Posted - 12/02/2004 :  22:03:43  Show Profile  Reply with Quote
I'm surprised and suspicious that the error % above is a constant. I'd bet a lot that it's very much not a constant, because for small distances, spherical trig and flat-earth calculations would be almost exactly the same. For large distances, the errors become greater.

I've got to pack for a trip now, but I'll be back Monday nite. I hope Arnold Fribble takes a look at this to give us his 2cents.

Sam
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/02/2004 :  22:54:13  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
Then I'll definitely have to think about it some more... have a nice trip!

Corey
Go to Top of Page

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 12/03/2004 :  05:54:51  Show Profile  Reply with Quote
quote:
Originally posted by SamC
I've got to pack for a trip now, but I'll be back Monday nite. I hope Arnold Fribble takes a look at this to give us his 2cents.



http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=12572
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=16859
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 12/03/2004 :  09:08:21  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
So... Arnold, from the second link I believe I read that you implemented something similar, but that you broke the world up into latitude rings and slightly altered the conditions for each ring.

So basically, the error is not constant, but I would still like to know if you think that the conditions are still a reasonable approximation for quick filtering?

x <= @approxDegrees
y <= @approxDegrees
y <= (2)^(1/2)*@approxDegrees - x

Where the @approxDegrees is an approximation based on the desired mileage range.


I think what I gather is that this would only work within areas that do not cross too many latitude lines.

Thanks for the links!

Corey
Go to Top of Page

X002548
Not Just a Number

15586 Posts

Posted - 12/03/2004 :  11:03:03  Show Profile  Reply with Quote
I always thought it was the Great Circle Formula...wrote this in Access (which has very poor trig support)...guess I should convert it


Function Deg2Rad(NumberArg As Double) As Double
    
        Deg2Rad = NumberArg * ((22 / 7) / 180) ' Return Radians
    
End Function
 Function ArcCos(NumberArg As Double) As Double
   
        ArcCos = Atn((-1 * NumberArg) / Sqr((-1 * NumberArg) * NumberArg + 1)) + 2 * Atn(1) ' Return Inverse Cosine
    
End Function
 Function GreatCircle(X1 As Double, Y1 As Double, X2 As Double, Y2 As Double) As Double
 
        GreatCircle = Kil2Mi((Rad2Deg(ArcCos((Sin(Deg2Rad([X1])) * Sin(Deg2Rad([X2]))) + (((Cos(Deg2Rad([X1])) * Cos(Deg2Rad([X2]))) * (Cos(Abs((Deg2Rad([Y2])) - (Deg2Rad([Y1])))))))))) * 111.23)

End Function
 Function Kil2Mi(NumberArg As Double) As Double
    
        Kil2Mi = 0.62 * NumberArg ' Convert Kilometers to Miles
   
End Function

 Function Mi2Kil(NumberArg As Double) As Double
  
        Mi2Kil = 1.6 * NumberArg ' Convert Miles to Kilometers
    
End Function


Function Rad2Deg(NumberArg As Double) As Double
 
        Rad2Deg = NumberArg * (180 / (22 / 7)) ' Return Degrees.
    
End Function





Brett

8-)
Go to Top of Page

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 12/04/2004 :  08:29:06  Show Profile  Reply with Quote
quote:
Originally posted by Seventhnight

I would still like to know if you think that the conditions are still a reasonable approximation for quick filtering?


I've no idea. I don't understand what you were doing.
Go to Top of Page

elwoos
Flowing Fount of Yak Knowledge

United Kingdom
2050 Posts

Posted - 12/05/2004 :  14:38:10  Show Profile  Reply with Quote
Does anyone have any idea how we could do a similar thing for UK post codes. i.e. determine the (straight line) distance between 2 UK post codes?


steve

To alcohol ! The cause of - and solution to - all of life's problems
Go to Top of Page

Kristen
Test

United Kingdom
22403 Posts

Posted - 12/06/2004 :  01:44:49  Show Profile  Reply with Quote
We use an XML feed to www.postcodeanywhere.co.uk for this sort of thing

Kristen
Go to Top of Page

elwoos
Flowing Fount of Yak Knowledge

United Kingdom
2050 Posts

Posted - 12/06/2004 :  06:06:07  Show Profile  Reply with Quote
Thanks Kristen I'll take a look at that

steve

To alcohol ! The cause of - and solution to - all of life's problems
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.11 seconds. Powered By: Snitz Forums 2000