?
Solved

Determine distance from US border

Posted on 2009-02-08
7
Medium Priority
?
1,174 Views
Last Modified: 2012-05-06
I have a list of latitudes and longitudes for the US/Canadian border and need to determine if a particular lat/long pair (within Canada) is within 225 miles of the US border.  Obviously this is a fairly complicated line and the 225 miles could be in almost any direction from the point being checked.

This needs to be a generic solution because I need to run it many times over a large number of points.

I have considered two solutions, but have been unable to make either of them work.  Help with either would be greatly appreciated!

1.  Come up with a "new border" which includes all of the area within 225 miles of the border and then see if the point is inside this line.  I know that the code would have to generate a lot of arcs, see where they intersect, and just use the outline of this area to define the new line.  

2.  Calculate a 225 ring around the point and see if it intersects the polyline defining the border at any point.  I'm thinking that this would be easier, but am not sure how to start.

Attached is my excel file containing the lat/long's for the border in both degrees and radians.

Thanks in advance!
'This formula will probably come in handy (whether used to calculate points for a circle, or the expanded border):
 
'Destination point given distance and bearing from start point:
Public Function CalculateDistance()
'd is distance traveled in radians - 225 miles in this case
d = 225 / 3963.1676
'lat1 = Latitude of the starting position
lat1 = 0.706009923115762
'lon1 = Longitude of the starting position
lon1 = 1.14667647042346
'brg is the bearing from lat1/lon1 in radians
brng = 180 * Pi / 180
 
lat2 = ArcSin(Sin(lat1) * Cos(d) + Cos(lat1) * Sin(d) * Cos(brng))
lon2 = lon1 + Application.WorksheetFunction.Atan2(Cos(d) - Sin(lat1) * Sin(lat2), Sin(brng) * Sin(d) * Cos(lat1))
 
End Function
 
Function ArcSin(X As Double) As Double
    ArcSin = Atn(X / Sqr(-X * X + 1))
End Function

Open in new window

US-CAN-Border.xls
0
Comment
Question by:lnafziger
  • 4
  • 2
6 Comments
 
LVL 45

Expert Comment

by:patrickab
ID: 23585782
lnafziger,

In the attached file the cells (border definition cells) coloured yellow are all within 225 miles of the coords in the blue cells. Not mathematically perfect but I reckon it won't be much out.

Hope it helps

Patrick

US-CAN-Border-01.xls
0
 

Author Comment

by:lnafziger
ID: 23586237
Hi Patrick,

Thanks for the solution, however there are two problems which cause a problem for me.

1.  This needs to be done for a very large number of points, and therefore needs to be in a formula which fits into one cell (instead of the many many cases for each point as in your example).

2.  This is only checking to each vertex on the line and there are some fairly large sections of straight lines which could cause errors.  (as an extreme example consider the case where there was a straight line segment of 600 miles.  Now a point that was even ON the border in the 150 mile "dead zone" between the two points that define the border would show greater than 225 miles away.  Basically, I need to calculate the distance to the polyline defined by all of the border points instead of to the points themselves.)

Louis
0
 
LVL 45

Expert Comment

by:patrickab
ID: 23586632
Louis,

> Basically, I need to calculate the distance to the polyline defined by all of the border points instead of to the points themselves.)

If the line was defined by a formula it would be straightforward but as it's a polyline with discreet points I doubt that it can be done without some rather clever coding. However if you are concerned by problems created by straight lines then why not insert a large array of numbers all along the straight lines. It seems a simple enough thing to do. Having done that you would certainly be able to compute it within a mile with some degree of certainty.

Apart from that as you have nearly 11,000 vertices for a border that is less than 3000 miles that means there's a vertex every 1/3rd of a mile or less. I find it hard to believe that that is insufficient accuracy - unless of course you are designing guidance systems for cruise missiles - in which case a miss of 1/3rd of mile would be somewhat devastating.

In fact looking at the vertices even along the straighline sections there are numerous vertices so I believe you there should be little room for concern - thus I believe your point 2 to be incorrect.

If you want just the lat and long of the closest point on the border to a specified lat and long then that is a simple matter to arrange. After all that's all that's needed to determine whether a location is within 225 miles of the border.

Patrick
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:lnafziger
ID: 23587234
Hi Patrick,

I can easily add more points as needed however there is not as much information here as one would think.  A lot of points are needed in order to accurately determine the border in areas where it is changing a lot, however as you get into the west there are large areas where the border is straight.  In fact, there are 983 points where there is more than a mile between points, with the largest being almost 200 miles between points.  This would add quite a bit of data to an already large spreadsheet and since it is theoretically possible to calculate this I would like to figure out how rather than just throw more data at it.

As far as coming up with a solution based on what you have given me so far, you said that it is a simple matter to see which point on the border is the closest?  I can do this using VBA to do the calculation for every point (and can do some simple optimizations to rule out data that I know will be too far away to help reduce the processing overhead) but do you know how to do this in excel?

Thank you so much for your input so far, as I can now see a way to do it!  I would still like to find a mathematically correct solution to the polyline/circle question though.  :-)
0
 
LVL 45

Expert Comment

by:patrickab
ID: 23589797
Louis,

I believe the polyline/arc solution is truly unnecessary. It is a sledgehammer to crack a nut.

The number of rows of vertices that you have, I suggest, is for pratical purposes not a limiting factor. Whether you have 11,000 or 22,000 rows of vertices is irrelevant as to how well Excel functions. Even using an old edition of Excel, such as Excel 2002, it can cope with far in excess of 22,000 rows of data without problem. Not only that it will cope with it fast - provided formulae are used rather than VBA. In fact formulae are in some instances many times the speed of VBA and without exception VBA is slower than formulae. However there are of course many instances where what's needed cannot be achieved without the use of VBA. Having said that I do not believe VBA is needed in this instance.

Let me have a look at the problem this afternoon and see what I can come up with. I'll be back...

Patrick
0
 
LVL 45

Accepted Solution

by:
patrickab earned 2000 total points
ID: 23590665
Louis,

Attached is a new file. Enter the latitude and longitude in the blue cells and in the green cells it will tells you the closest distance those coordinates are from the border. It will also tell you the latitude and longitude of that location on the border that is closest.

On my rather old 1.6GHz, 0.5Gb RAM machine, it takes a few seconds to complete the calculations. However on a new faster machine it should give you the answer pretty well instantly - but do please check that INDEX has recalculated in cells J3 and K3.

I have added Conditional Formatting to column F so that the minimum value is highlighted in red. So that you don't have to search for that value I have put its row number in cell L3.

To ensure that you cover the straight-line sections of the border more comprehensively I believe you will need to add interpolated latitude and longitude data - and then edit the formulae that I have used so as to include the new data.

The distance per degree I have taken as the average between the global polar and equatorial circumferences - this makes it accurate to within 204 yards per degree - which should be adequate.

Hope that helps

Patrick

US-CAN-Border-02.xls
0

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This code takes an Excel list of URL’s and adds a header titled “URL List”. It then searches through all URL’s in column “A”, looking for duplicates. When a duplicate is found, it is moved to the top of the list. The duplicate URL’s are then highlig…
Excel can be a tricky bit of software to get your head around. Whilst you’ll be able to eventually get to grips with the basic understanding of how to get by, there are a few Excel tips that not everybody will even know about let alone know how to d…
This Micro Tutorial will demonstrate in Google Sheets how to use the HYPERLINK function to create live links inside your spreadsheet.
This Micro Tutorial will demonstrate how to use a scrolling table in Microsoft Excel using the INDEX function.

569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question