Function F_FIND_SEARCH_LIMITS - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

General SQL Server Forums

Script Library

Function F_FIND_SEARCH_LIMITS

Author

Topic

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2008-10-10 : 16:39:39

The returned values from function F_FIND_SEARCH_LIMITS can be used to setup a bounded search of a table containing min/max Latitude and Longitude values for applications that need to return values within a specified distance from a central point.

This allows use of table indexes to do an efficient search for values than may be within the search radius. The result set can then be trimmed by calculating the great circle distance to eliminate values outside the search radius. Function F_GREAT_CIRCLE_DISTANCE can be used to calculate the distances of that result set. Typically, about 75% of the values from the bounded query will be within the search radius.

The algorithm used in F_FIND_SEARCH_LIMITS is a loop where the calculation is refined on each loop until the error is very small. A direct calculation would be better, but this produces results accurate to less than a meter over the widest possible search ranges, and handles especially difficult search limit calculations with a large search radius and/or high latitudes close to the Earths pole. Note that it will not allow a search radius of less than 1 meter or that comes within 100 kilometers of the Earths North or South poles.

This function uses function F_GREAT_CIRCLE_DISTANCE on the link below.
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=81360


if object_id('dbo.F_FIND_SEARCH_LIMITS') is not null
	drop function dbo.F_FIND_SEARCH_LIMITS
go
create function dbo.F_FIND_SEARCH_LIMITS
	(
	@Latitude	float,
	@Longitude 	float,
	@SearchRadius	float
	)
returns	@search_Limits table
	(
	MaxLongitude		decimal(9,6)	not null,
	MinLongitude		decimal(9,6)	not null,
	MaxLatitude		decimal(9,6)	not null,
	MinLatitude		decimal(9,6)	not null
	)
as
/*

Function: F_FIND_SEARCH_LIMITS

Function F_FIND_SEARCH_LIMITS is used to find the min/max limits
of Latitude and Longitude for the search radius passed in
parameter @SearchRadius from the point on the earth defined by
input parameters @Latitude and @Longitude.

The returned values can be used to setup a search of a table
containing Latitude and Longitude values for applications
that need to return values within a specified distance from
a central point.  This allows use of table indexes to
do an efficient search for values than may be within the 
search radius.  The result set can then be trimmed by
calculating the great circle distance to eliminate
values outside the search radius.

The calculation is refined in a loop to produce a result that
is accurate to less than 1 meter from the actual distance,
and is slightly larger that the search radius to prevent
excluding valid points.

Parameter @SearchRadius is in kilometers.
To use it with miles, multiply @SearchRadius by 1.609344E

This function uses function dbo.F_GREAT_CIRCLE_DISTANCE
to calculate great circle distance.
 
*/

begin

declare @Degrees	float
declare @MaxLon		float
declare @MinLon		float
declare @MaxLat		float
declare @MinLat		float
declare @DegreePerKM 	float
declare @DistanceToPole	float
declare @WorkDistance	float

declare	@mess		varchar(400)
declare @cr 		varchar(2)
declare @x 		int

set @cr = char(13)+Char(10)
set @mess	= ''

-- Verify parameter @Latitude is valid
if abs(@Latitude) >= 90.0E
	begin
	set @mess = 'Greater than maximum allowed Latitude, '+
	', Latitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(abs(@Latitude),6))),'NULL')
	goto Error_Exit
	end

-- Verify parameter @Longitude is valid
if abs(@Longitude) > 180.0E
	begin
	set @mess = 'Greater than maximum allowed Longitude, '+
	', Longitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(abs(@Longitude),6))),'NULL')
	goto Error_Exit
	end

-- Verify parameter @SearchRadius is greater than .001 kilometer
if @SearchRadius < .001E
	begin
	set @mess = 'Minimum search radius is .001'+
	', Search Radius = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@SearchRadius,6))),'NULL')
	goto Error_Exit
	end

set @DistanceToPole = dbo.F_GREAT_CIRCLE_DISTANCE(0E,abs(@Latitude),0E,90E)

-- Verify that the Search Radius is no closer than 100 kilometers from a pole of the Earth
if @SearchRadius+100 > @DistanceToPole
	begin
	set @mess = 'Latitude too close to pole for search radius,'+@cr+
	'Latitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@Latitude,6))),'NULL')+
	', Search Radius = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@SearchRadius,6))),'NULL')+
	', Distance to Pole = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@DistanceToPole,6))),'NULL')
	goto Error_Exit
	end

-- Get number of degrees for a search at the equator
set @Degrees = @SearchRadius/(dbo.F_GREAT_CIRCLE_DISTANCE(0E,0E,0E,90E)/90.000000000E)

-- Get great circle distance 90 degrees away on the same latitude
-- for initial estimate of degrees per kilometer.
set @DegreePerKM = (90E)/dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude,0E,@Latitude,90E)

select
	@MaxLon = @Longitude + (@DegreePerKM*@SearchRadius),
	@MinLon = @Longitude - (@DegreePerKM*@SearchRadius),
	@MaxLat	= @Latitude + @Degrees+.0000000001E ,
	@MinLat	= @Latitude - @Degrees-.0000000001E

declare @count int
set @count = 0

while 1=1
begin
	-- Calculate great circle distance along latitude line
	set @WorkDistance = dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude,@Longitude,@Latitude,@MaxLon)

	-- Exit when calculation is good enough or loop count greater than 15
	if @WorkDistance-@SearchRadius < 0.0000005E or 
	   @count > 15
		begin
		break
		end

	set @count = @count+1

	-- Refine estimate of degrees per kilometer
	set @DegreePerKM = (@MaxLon-@Longitude)/@WorkDistance
	
	-- Recalculate the min/max estimate with the refined degrees per kilometer
	set @MaxLon = @Longitude+(@DegreePerKM*@SearchRadius)
	set @MinLon = @Longitude-(@DegreePerKM*@SearchRadius)

	end  -- End of While loop

-- Add increment to ensure limits are slightly outside search radius
select
	@MaxLon = round(@MaxLon+0.0000005E,6),
	@MinLon = round(@MinLon-0.0000005E,6),
	@MaxLat	= round(@MaxLat+0.0000005E,6),
	@MinLat	= round(@MinLat-0.0000005E,6)

insert into @search_Limits
select
	@MaxLon,
	@MinLon,
	@MaxLat,
	@MinLat

return

Error_Exit:
-- Cause an conversion error to occur to send an error massage
if @mess <> ''
	select @x=
	convert(int,@cr+@cr+@cr+replicate('*',90)+@cr+@mess+@cr+replicate('*',90)+@cr+@cr+@cr)

return

end
go


-- Test Script to confirm output is valid


declare @Latitude	float,
	@Longitude 	float,
	@SearchRadius	float

set @SearchRadius 	= 3000.000E
set @Latitude		= 50E
set @Longitude		= 0E

select
	Latitude	= convert(numeric(12,6),round(@Latitude,6)),
	Longitude	= convert(numeric(12,6),round(@Longitude,6)),
	SearchRadius	= convert(numeric(12,6),round(@SearchRadius,6))

select
	MaxLat	= a.MaxLatitude,
	MinLat	= a.MinLatitude,
 	MaxLon	= a.MaxLongitude,
	MinLon	= a.MinLongitude
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a

Select
	KmToMaxLon =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude, @Longitude, @Latitude, a.MaxLongitude),6)) ,
	KmToMinLon =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude, @Longitude, @Latitude, a.MinLongitude),6)) ,
	KmToMaxLat =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.MaxLatitude, @Longitude),6)) ,
	KmToMinLat =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.MinLatitude, @Longitude),6))
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a



--End of Test Script

Results of Test Script:


Latitude       Longitude      SearchRadius   
-------------- -------------- -------------- 
50.000000      .000000        3000.000000

(1 row(s) affected)

MaxLat      MinLat      MaxLon      MinLon      
----------- ----------- ----------- ----------- 
76.979649   23.020351   42.557769   -42.557769

(1 row(s) affected)

KmToMaxLon     KmToMinLon     KmToMaxLat     KmToMinLat     
-------------- -------------- -------------- -------------- 
3000.000026    3000.000026    3000.000091    3000.000091

(1 row(s) affected)


/*
Sample script for a typical search against a Zip Code table
*/

declare @MaxLongitude		decimal(9,6)
declare @MinLongitude		decimal(9,6)
declare @MaxLatitude		decimal(9,6)
declare @MinLatitude		decimal(9,6)

declare @Latitude	float,
	@Longitude 	float,
	@SearchRadius	float

-- Set Search Radius in miles
-- set @SearchRadius 	=  20E * 1.609344E

-- Set Search Radius in kilometers
set @SearchRadius 	=  35E

-- Set Latitude/Longitude of search center
set @Latitude		=  38.980022E
set @Longitude		= -83.276192E

-- Get Search limits
select
	@MaxLongitude	= a.MaxLongitude,
	@MinLongitude	= a.MinLongitude,
	@MaxLatitude	= a.MaxLatitude,
	@MinLatitude	= a.MinLatitude
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a


-- Query Zip code Table
select
	-- Show distance
	Distance =
		convert(decimal(9,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE),6)),
	*
from
	dbo.T_ZIP_CODE a
where
	-- Select only items within search limits
	a.LATITUDE  between @MinLatitude  and @MaxLatitude	and
	a.LONGITUDE between @MinLongitude and @MaxLongitude	and
	-- Select only items where distance is within search radius
	dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE) <= @SearchRadius
order by
	-- Order closest to farthest
	dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE)

/*
End of script for typical search against a Zip Code table
*/

CODO ERGO SUM

dmbware
Starting Member

4 Posts

Posted - 2008-12-02 : 12:22:02

Michael I have a DB with 50k records of properties each having a lat and long, map code, zip code and address. What I am trying to do is pull all properties that fall within a 1 mile radius of a given property. Can you lend me your thoughts on how to approach this equation? Should I use zip code with long and lat?

quote:

Originally posted by Michael Valentine Jones

The returned values from function F_FIND_SEARCH_LIMITS can be used to setup a bounded search of a table containing min/max Latitude and Longitude values for applications that need to return values within a specified distance from a central point.

This allows use of table indexes to do an efficient search for values than may be within the search radius. The result set can then be trimmed by calculating the great circle distance to eliminate values outside the search radius. Function F_GREAT_CIRCLE_DISTANCE can be used to calculate the distances of that result set. Typically, about 75% of the values from the bounded query will be within the search radius.

The algorithm used in F_FIND_SEARCH_LIMITS is a loop where the calculation is refined on each loop until the error is very small. A direct calculation would be better, but this produces results accurate to less than a meter over the widest possible search ranges, and handles especially difficult search limit calculations with a large search radius and/or high latitudes close to the Earths pole. Note that it will not allow a search radius of less than 1 meter or that comes within 100 kilometers of the Earths North or South poles.

This function uses function F_GREAT_CIRCLE_DISTANCE on the link below.
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=81360


if object_id('dbo.F_FIND_SEARCH_LIMITS') is not null
	drop function dbo.F_FIND_SEARCH_LIMITS
go
create function dbo.F_FIND_SEARCH_LIMITS
	(
	@Latitude	float,
	@Longitude 	float,
	@SearchRadius	float
	)
returns	@search_Limits table
	(
	MaxLongitude		decimal(9,6)	not null,
	MinLongitude		decimal(9,6)	not null,
	MaxLatitude		decimal(9,6)	not null,
	MinLatitude		decimal(9,6)	not null
	)
as
/*

Function: F_FIND_SEARCH_LIMITS

Function F_FIND_SEARCH_LIMITS is used to find the min/max limits
of Latitude and Longitude for the search radius passed in
parameter @SearchRadius from the point on the earth defined by
input parameters @Latitude and @Longitude.

The returned values can be used to setup a search of a table
containing Latitude and Longitude values for applications
that need to return values within a specified distance from
a central point.  This allows use of table indexes to
do an efficient search for values than may be within the 
search radius.  The result set can then be trimmed by
calculating the great circle distance to eliminate
values outside the search radius.

The calculation is refined in a loop to produce a result that
is accurate to less than 1 meter from the actual distance,
and is slightly larger that the search radius to prevent
excluding valid points.

Parameter @SearchRadius is in kilometers.
To use it with miles, multiply @SearchRadius by 1.609344E

This function uses function dbo.F_GREAT_CIRCLE_DISTANCE
to calculate great circle distance.
 
*/

begin

declare @Degrees	float
declare @MaxLon		float
declare @MinLon		float
declare @MaxLat		float
declare @MinLat		float
declare @DegreePerKM 	float
declare @DistanceToPole	float
declare @WorkDistance	float

declare	@mess		varchar(400)
declare @cr 		varchar(2)
declare @x 		int

set @cr = char(13)+Char(10)
set @mess	= ''

-- Verify parameter @Latitude is valid
if abs(@Latitude) >= 90.0E
	begin
	set @mess = 'Greater than maximum allowed Latitude, '+
	', Latitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(abs(@Latitude),6))),'NULL')
	goto Error_Exit
	end

-- Verify parameter @Longitude is valid
if abs(@Longitude) > 180.0E
	begin
	set @mess = 'Greater than maximum allowed Longitude, '+
	', Longitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(abs(@Longitude),6))),'NULL')
	goto Error_Exit
	end

-- Verify parameter @SearchRadius is greater than .001 kilometer
if @SearchRadius < .001E
	begin
	set @mess = 'Minimum search radius is .001'+
	', Search Radius = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@SearchRadius,6))),'NULL')
	goto Error_Exit
	end

set @DistanceToPole = dbo.F_GREAT_CIRCLE_DISTANCE(0E,abs(@Latitude),0E,90E)

-- Verify that the Search Radius is no closer than 100 kilometers from a pole of the Earth
if @SearchRadius+100 > @DistanceToPole
	begin
	set @mess = 'Latitude too close to pole for search radius,'+@cr+
	'Latitude = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@Latitude,6))),'NULL')+
	', Search Radius = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@SearchRadius,6))),'NULL')+
	', Distance to Pole = '+
	isnull(convert(varchar(20),convert(decimal(20,6),round(@DistanceToPole,6))),'NULL')
	goto Error_Exit
	end

-- Get number of degrees for a search at the equator
set @Degrees = @SearchRadius/(dbo.F_GREAT_CIRCLE_DISTANCE(0E,0E,0E,90E)/90.000000000E)

-- Get great circle distance 90 degrees away on the same latitude
-- for initial estimate of degrees per kilometer.
set @DegreePerKM = (90E)/dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude,0E,@Latitude,90E)

select
	@MaxLon = @Longitude + (@DegreePerKM*@SearchRadius),
	@MinLon = @Longitude - (@DegreePerKM*@SearchRadius),
	@MaxLat	= @Latitude + @Degrees+.0000000001E ,
	@MinLat	= @Latitude - @Degrees-.0000000001E

declare @count int
set @count = 0

while 1=1
begin
	-- Calculate great circle distance along latitude line
	set @WorkDistance = dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude,@Longitude,@Latitude,@MaxLon)

	-- Exit when calculation is good enough or loop count greater than 15
	if @WorkDistance-@SearchRadius < 0.0000005E or 
	   @count > 15
		begin
		break
		end

	set @count = @count+1

	-- Refine estimate of degrees per kilometer
	set @DegreePerKM = (@MaxLon-@Longitude)/@WorkDistance
	
	-- Recalculate the min/max estimate with the refined degrees per kilometer
	set @MaxLon = @Longitude+(@DegreePerKM*@SearchRadius)
	set @MinLon = @Longitude-(@DegreePerKM*@SearchRadius)

	end  -- End of While loop

-- Add increment to ensure limits are slightly outside search radius
select
	@MaxLon = round(@MaxLon+0.0000005E,6),
	@MinLon = round(@MinLon-0.0000005E,6),
	@MaxLat	= round(@MaxLat+0.0000005E,6),
	@MinLat	= round(@MinLat-0.0000005E,6)

insert into @search_Limits
select
	@MaxLon,
	@MinLon,
	@MaxLat,
	@MinLat

return

Error_Exit:
-- Cause an conversion error to occur to send an error massage
if @mess <> ''
	select @x=
	convert(int,@cr+@cr+@cr+replicate('*',90)+@cr+@mess+@cr+replicate('*',90)+@cr+@cr+@cr)

return

end
go


-- Test Script to confirm output is valid


declare @Latitude	float,
	@Longitude 	float,
	@SearchRadius	float

set @SearchRadius 	= 3000.000E
set @Latitude		= 50E
set @Longitude		= 0E

select
	Latitude	= convert(numeric(12,6),round(@Latitude,6)),
	Longitude	= convert(numeric(12,6),round(@Longitude,6)),
	SearchRadius	= convert(numeric(12,6),round(@SearchRadius,6))

select
	MaxLat	= a.MaxLatitude,
	MinLat	= a.MinLatitude,
 	MaxLon	= a.MaxLongitude,
	MinLon	= a.MinLongitude
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a

Select
	KmToMaxLon =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude, @Longitude, @Latitude, a.MaxLongitude),6)) ,
	KmToMinLon =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE(@Latitude, @Longitude, @Latitude, a.MinLongitude),6)) ,
	KmToMaxLat =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.MaxLatitude, @Longitude),6)) ,
	KmToMinLat =
		convert(numeric(12,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.MinLatitude, @Longitude),6))
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a



--End of Test Script

Results of Test Script:


Latitude       Longitude      SearchRadius   
-------------- -------------- -------------- 
50.000000      .000000        3000.000000

(1 row(s) affected)

MaxLat      MinLat      MaxLon      MinLon      
----------- ----------- ----------- ----------- 
76.979649   23.020351   42.557769   -42.557769

(1 row(s) affected)

KmToMaxLon     KmToMinLon     KmToMaxLat     KmToMinLat     
-------------- -------------- -------------- -------------- 
3000.000026    3000.000026    3000.000091    3000.000091

(1 row(s) affected)


/*
Sample script for a typical search against a Zip Code table
*/

declare @MaxLongitude		decimal(9,6)
declare @MinLongitude		decimal(9,6)
declare @MaxLatitude		decimal(9,6)
declare @MinLatitude		decimal(9,6)

declare @Latitude	float,
	@Longitude 	float,
	@SearchRadius	float

-- Set Search Radius in miles
-- set @SearchRadius 	=  20E * 1.609344E

-- Set Search Radius in kilometers
set @SearchRadius 	=  35E

-- Set Latitude/Longitude of search center
set @Latitude		=  38.980022E
set @Longitude		= -83.276192E

-- Get Search limits
select
	@MaxLongitude	= a.MaxLongitude,
	@MinLongitude	= a.MinLongitude,
	@MaxLatitude	= a.MaxLatitude,
	@MinLatitude	= a.MinLatitude
from
	dbo.F_FIND_SEARCH_LIMITS(@Latitude,@Longitude,@SearchRadius) a


-- Query Zip code Table
select
	-- Show distance
	Distance =
		convert(decimal(9,6),round(
		dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE),6)),
	*
from
	dbo.T_ZIP_CODE a
where
	-- Select only items within search limits
	a.LATITUDE  between @MinLatitude  and @MaxLatitude	and
	a.LONGITUDE between @MinLongitude and @MaxLongitude	and
	-- Select only items where distance is within search radius
	dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE) <= @SearchRadius
order by
	-- Order closest to farthest
	dbo.F_GREAT_CIRCLE_DISTANCE( @Latitude, @Longitude, a.LATITUDE, a.LONGITUDE)

/*
End of script for typical search against a Zip Code table
*/

CODO ERGO SUM

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources