lnafziger
asked on
Determine distance from US border
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 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 FunctionASKER
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
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
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
> 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
ASKER
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. :-)
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. :-)
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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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