Get the id of the next closest location

[p309444]

Hi.

I have an application in which the user can select a location and view it's distance from several Points Of Interests (POIs).

When I retrieve these distances, I would also like to retrieve the ID's of the locations that are the next closest and the next furthest away from each POI. eg. If we have 10 locations, each of them a mile further away from a certain POI the I would like to return: The name of the POI, The distance from that POI, The ID of the next closest location, and the ID of the next furthest location. An example row of the result set could be: 'Football Ground', '1.5', 24, 784 (because the location we are viewing is 1.5 miles from the football ground and location 24 is the next closest and 784 is the next furthest away.

Note: it is possible that the location we are viewing is the closest to or furthest from a POI, in that case we would need to return -1 as the id of the next closest or furthest location to let the front end know that we can't get any closer or further.

I would like to do this in one statement if possible. I created a function that will calculate the distance between 2 points, and have been using it around the application:

 
create FUNCTION [dbo].[fnc_calc_distance]
(
    @lat1 as float,
    @lng1 as float,
    @lat2 as float,
    @lng2 as float
)
RETURNS float
AS
BEGIN
    declare @result as float    
    select @result = (3959*acos(cos(radians(@lat2))*cos(radians(@lat1))*cos(radians(@lng1)-radians(@lng2))+sin(radians(@lat2))*sin(radians(@lat1))))
    RETURN @result
END
 
 

And sample table structures/ data are as follows:

 
CREATE TABLE tbl_locations(
    [houseID] [int] NOT NULL,
    [lat] [decimal](14, 10) not NULL,
    [lng] [decimal](14, 10) not NULL) 
 
insert into tbl_locations
    values (1, 54.9834400000, -1.6314250000)
insert into tbl_locations
    values (2, 54.9860420000, -1.5912680000)
insert into tbl_locations
    values (3, 54.9882050000, -1.5707710000)
 
CREATE TABLE tbl_poi(
    [ID] [int] NOT NULL,
    [name] [varchar](32) NOT NULL,
    [lat] [decimal](14, 10) NOT NULL,
    [lng] [decimal](14, 10) NOT NULL)
 
insert into tbl_poi
    values (1, 'Football Ground', 54.9752430000, -1.6219210000)
insert into tbl_poi
    values (1, 'Train Station', 54.9898610000, -1.6047600000)
 

Im using SQL Server 2008.

Thanks in advance.

Chris

[Delerna]

Hi Chris
I am here to assist people to overcome stumbling blocks in something they are writing, not to fill orders for complete working queries for free. I apologise if I have gotten you wrong but that is how your post comes accross, at least it does to me because there is no question anywhere in it!

If you have a question please post, along with what you have tried and I will be glad to assist.
What you did post is nicely done by the way.

[p309444]

EDIT: I have missed a column from each of the tables. Both tables need a column adding called region of type int. For the purposes of this, the values in this column of every row should be 1

[p309444]

I guess what I am asking is what is the best way to go to to get this done.

I have tried several methods, each one with it's own pitfalls. I didnt include them because I wanted people to look at this problem from a fresh slate, however I will detail two methods I have used:

declare @locationid int = 1
 
select p.id,
    dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng) as distance,
    c.houseID as closerid,
    dbo.fnc_calc_distance(p.lat, p.lng, c.lat, c.lng) as closerDistance,
    f.houseid as furtherdistance,
    dbo.fnc_calc_distance(p.lat, p.lng, f.lat, f.lng) as furtherDistance
from tbl_poi p
    left join tbl_locations l on l.region = p.region
    left join tbl_locations c on c.region = p.region
    left join tbl_locations f on f.region = p.region
where l.houseID = @locationid
    and dbo.fnc_calc_distance(p.lat, p.lng, c.lat, c.lng) < dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng)
    and dbo.fnc_calc_distance(p.lat, p.lng, f.lat, f.lng) > dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng)
 

This method fails because if the location if the closest or further from a POI then that POI will not be returned. The problem is in the where clause.

That led me onto this:

declare @locationid int = 1
 
select p.ID, p.name, 
    x.closerid, y.furtherid,
    x.closerDistance, y.furtherDistance
from tbl_poi p
    left join (
        select p.id,
            dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng) as distance,
            c.houseID as closerid,
            dbo.fnc_calc_distance(p.lat, p.lng, c.lat, c.lng) as closerDistance
        from tbl_poi p
            left join tbl_locations l on l.region = p.region
            left join tbl_locations c on c.region = p.region
        where l.houseID = @locationid
            and dbo.fnc_calc_distance(p.lat, p.lng, c.lat, c.lng) < dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng))x
        on p.ID = x.id
    left join (
        select p.id,
            f.houseid as furtherid,
            dbo.fnc_calc_distance(p.lat, p.lng, f.lat, f.lng) as furtherDistance
        from tbl_poi p
            left join tbl_locations l on l.region = p.region
            left join tbl_locations f on f.region = p.region
        where l.houseID = @locationid
            and dbo.fnc_calc_distance(p.lat, p.lng, f.lat, f.lng) > dbo.fnc_calc_distance(p.lat, p.lng, l.lat, l.lng))y
        on p.ID = y.id
 

Which WILL return every POI regardless if the location is the closest or furthest from it. BUT, what I need to do now is only return the closest and the next furthest location, not every location that is closer or further away. (A bit confusing I know but just bear with me).

Thanks again

Chris

[Delerna]

OK, your attempts show me more clearly what you are trying to do and convinces me I was wrong in my assumption.

I don't have your complete scenario I think, so I will present Ideas
that you can play with that might lead you to a solution.


Anyway, please note that I am using SQL 2000 so sytax might vary as well as 2008 having better ways of doing certain things

First a query that returns every possible combiation of two locations whithin a region along with the distance from the selected POI

   declare @locationid int 
   set @locationid= 1 
 
    select a.ID,a.Name,b.HouseID,dbo.fnc_calc_distance(a.Lat,a.Lng,b.Lat,b.lng) as Distance
    from (SELECT * from tbl_poi) a
    join (SELECT * from tbl_locations) b on a.region=b.Region
    where a.ID=2
 

If you run that you will notice that the current location joined to the current location returns 0.0 as the distance

wrap the above up as a sub query sorted by distance and selecting the top 2 records with the current joined to current location filtered out, should give you the next 2 closest POI's as two records

select Top 2 Name,a.HouseID,Distance
from
(
    select a.ID,a.Name,b.HouseID,dbo.fnc_calc_distance(a.Lat,a.Lng,b.Lat,b.lng) as Distance
    from (SELECT 1 as j,* from tbl_poi) a
    join (SELECT 1 as j,* from tbl_locations) b on a.j=b.j and a.region=b.Region
    where a.ID=2
)a
where Distance<>0.0
order by Distance
 

Now all you need do is pivot that into 1 record and handle the -1 requirement
Since 2008 can do those things more easily than 2000 I will leave that to you.

I hope that I have understood you correctly and that this helps

[p309444]

Hi.

I just thought I would post the final solution that I came up with for this problem.

Its pretty lengthy so I'll try my best to describe it.

Firstly, I created a view called vw_distance which was just all the pois joined to all the locations. This view had 3 columns: poiID, locationID and distance (distance being the distance between the location and the poi)

The next bit is where the magic happens:

I took the poi table and done a left join to it with the location table on region.
I then wrote a subquey that would get me the next closest location. It does this by selecting max(distance) from vw_distance, grouped by poiid. BUT, we dont just wantt he max distance, we want the max distance that is LOWER than the current distance, so, I joined to vw_distance again so that I could add a where clause that said get me the max(distance) where distance < the current distance. So, the subquery looks like this:

select a.poiid, MAX(a.distance) as dc 
                    from vw_distance a
                        left join vw_distance b
                            on a.poiid = b.poiid
                    where a.distance < b.distance
                        and b.houseid=@id
                    group by a.poiid

Once I had that, It's really easy to alter it to retrieve the next further location- just change the MAX to a MIN and the < to a >.

I joined these two subqueries to my original query and now i was able to pull back a list of all the POI, the distance from the current location, and the distance of the next closest and next furtherest location from the POI:

  select p.ID, p.name, dc.dc, 
        dbo.fnc_calc_distance(p.lat, p.lng, s.lat, s.lng) as distance,
        round(dbo.fnc_calc_distance(p.lat, p.lng, s.lat, s.lng)*20, 0) as time,
        df.df
    from tbl_poi p
        left join tbl_locations s on p.region = s.region
        left join (    select a.poiid, MAX(a.distance) as dc 
                    from vw_distance a
                        left join vw_distance b
                            on a.poiid = b.poiid
                    where a.distance < b.distance
                        and b.houseid=@id
                    group by a.poiid)dc 
            on p.ID = dc.poiid
        left join (    select a.poiid, min(a.distance) as df
                    from vw_distance a
                        left join vw_distance b
                            on a.poiid = b.poiid
                    where a.distance > b.distance
                        and b.houseid=@id
                    group by a.poiid)df 
            on p.ID = df.poiid

Now that I had this, all I had to do was to get the IDs of the locations that had the said distances above.

This was relatively simple and achieved by joining good old trusty vw_distance back to my original query on distance. I had to do this twice again, one for closer and one for further.

So, all in all:

    select p.ID, p.name, dc.dc, cid.houseid as closer, 
        dbo.fnc_calc_distance(p.lat, p.lng, s.lat, s.lng) as distance,
        round(dbo.fnc_calc_distance(p.lat, p.lng, s.lat, s.lng)*20, 0) as time,
        df.df, fid.houseid as further
    from tbl_poi p
        left join tbl_locations s on p.region = s.region
        left join (    select a.poiid, MAX(a.distance) as dc 
                    from vw_distance a
                        left join vw_distance b
                            on a.poiid = b.poiid
                    where a.distance < b.distance
                        and b.houseid=@id
                    group by a.poiid)dc 
            on p.ID = dc.poiid
        left join (    select a.poiid, min(a.distance) as df
                    from vw_distance a
                        left join vw_distance b
                            on a.poiid = b.poiid
                    where a.distance > b.distance
                        and b.houseid=@id
                    group by a.poiid)df 
            on p.ID = df.poiid
        left join vw_distance cid
            on p.ID = cid.poiid
                and dc.dc = cid.distance
        left join vw_distance fid
            on p.ID = fid.poiid
                and df.df = fid.distance
    where
        s.houseid = @id

This project is coming to an end and I've have had to overcome some pretty challenging stuff to get it this far.

If anyone can think of a better way to do this then please post!

Thanks