Discussion in 'Programmer's Corner' started by Eric007, Jul 25, 2018.

1. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,140
38
Hi All,

Trust you are well

I need an algorithm to implement in a method whereby you can add a distance to a coordinate (latitude, longitude).
Example, let's say you would like to add say 5 km to the coordinates below to get new lat. and new coordinates:
lat.: 40.712775
lon.: -74.005973

Any help/guidance would be appreciated.

Eric

Jan 18, 2008
6,391
1,230
3. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
Add 5 km in which direction?

Does it not make sense that if you go 5 km north that you will get a different set of final coordinates than if you go 5 km southwest?

What model of the Earth are you using? A simple sphere? Or one of the standard oblate spheroids?

Since your coordinates have 8 sig figs, that implies that you are looking for a level of accuracy consistent with about 10 cm, so this really matters.

There's also the question of what defines the path to be followed. For instance, if you say that you are going to move "east", then does that mean that at every point in the journey you are moving east relative to that point (meaning that you stay at the same latitude for the entire trip) or does it mean that you move along a great circle path that goes through your initial starting point and is tangent to your initial vector? Or something else?

Eric007 likes this.
4. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,140
38
Thank you so much @WBahn for all these important questions that I didn't even think about.
And you are right, I will get a set of coordinates which is perfectly fine. Which direction to add x distance? I would say all directions. Basically I need a set of coordinates whose distance with my location (in this case the above lat., lon.) is 5 km or whatever.

The method signature will be something like: public void GetCoordinates(double latitude, double longitude, int distance)
this will actually return a collection... not void

5. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
How big is the collection it is returning? The set of coordinates that are a given distance from a given coordinate is infinite in size. If you set the resolution to be comparable to your eight sig-figs, then you are looking at a set of coordinates that is over 300,000 in size (for a 5 km distance).

Also, why is the distance an integer? What about the problem makes it so that you can't ask for something that is 5.2 km from your coordinate?

It might help if you describe the problem you are trying to solve. There might be a cleaner way to come at it.

For instance, if you are trying to determine if some object at one coordinate is within a given distance of another object at a second coordinate, then this is a much simpler task (particularly if you are assuming a spherical Earth).

6. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,140
38
Alright I will start with this: "It might help if you describe the problem you are trying to solve. There might be a cleaner way to come at it."

I know/have my current location in terms of latitude and longitude and I have this method that returns locations (lat. & long.) of places around me, if they exist of course. Now what I need is to be able to specify the distance from my location so that let say I specify 1.1km... the method should not return locations of places that are > 1.1km from me.

And yes the distance parameter should be 'double', not 'int'. So this is a small part of the problem I need to solve.

7. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
So, if I understand you correctly you have a collection of "things" and each of these things has a lat/long.

What you are trying to do is write a function in which you specify a lat/long and a range and what gets returned is a subset of this collection of things such that it contains any and all items that are within the specified range of the specified location.

If that is correct, then your problem becomes pretty simple -- especially if you are using a spherical model of the Earth (and you still haven't indicated what model of the Earth you are planning to use).

What you want to do instead, as your first step, is write a function that takes two lat/long coordinates and returns the great circle distance between them. Then, in the function you are trying to write, simply call this function on every item in your collection using the specified lat/long.

If your collection of items is huge, then sort it by latitude because you can limit your search to items that lie within a range of latitudes.

8. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,140
38
Correct BUT this: "So, if I understand you correctly you have a collection of "things" and each of these things has a lat/long."
Actually my current method takes, among other parameters, my current location (lat. & lon.) and returns a list of "things/objects".
These objects have some properties that I use to get their locations. The problem now is trying to restrict the range of the location of these returned things.
I hope I shed more light...

As for the model of earth, let take the one that will make things easier...spherical for example.

9. ### jpanhalt Expert

Jan 18, 2008
6,391
1,230
Since you are talking about a very small radius relative to Earth, as a first approximation, can't you just assume a flat Earth and a constant distance for each degree longitude based on your latitude?* Then it is just finding points within a circle on a plane.

*Edit: Assuming you are not at or near either of Earth's poles.

Last edited: Jul 25, 2018
Eric007 likes this.
10. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
So with a spherical model, what you can do is rely on some basic trig and vector relations to solve for the great circle distance between two arbitrary points.

First, imagine taking a globe and picking two points on the surface of it. Now connect each of those two points to the center with straight lines. If you knew the angle included between the two lines, then you could easily find the arc distance between the two points.

Let's say that the included angle is θ and the radius of the sphere is R. The arc distance is simply

L = R·θ (where θ is in radians, of course)

So we just need a way to find θ.

Now consider the vector dot and vector cross products:

A·B = |A| |B| cos(θ)
A×B = |A| |B| sin(θ)

While you could use either of these to get θ, and while the dot product is easier to calculate, since you are probably working with very small angles you probably want to work with the cross product to minimize roundoff errors, plus, it gives you the option of using the approximation that sin(θ) ≈ θ, depending on your accuracy requirements. If you are working with distances of about 5 km, then the angles you are working with are on the order of 100 μrad which means you can use the approximation up to about 8 or 9 sig figs.

The next thing is to get the cross product in terms of the lat/long angles. The easiest way to do that (other than looking it up -- but you could have done that with the great circle distance from the beginning if you don't care about understanding what you are doing) is to convert to rectangular coordinates since we know that:

<x1,y1,z1> × <x2,y2,z2> = <x3,y3,z3> = <(y1·z2 - z1·y2), (z1·x2 - x1·z2), (x1·y2 - y1·x2)>

|A×B| = |<x3,y3,z3>| = √(x3² + y3² + z3²)

and we know that |A| = |B| = R, so we have

sin(θ) = |A×B| / R²

If we align our rectangular coordinate system so that the x-y plane is coincident with the equator (and the center of the Earth is at the origin) then we can put 0° longitude on the positive x-axis and the North Pole on the positive z-axis. This also puts the positive y-axis at 90° E longitude (which is consistent with the normal positive/negative lat/long convention).

Given a (lat/long) of (σ,φ) the z-dimension is trivial

z = R·sin(φ)

The x- and y- dimensions are almost as easy once we realize that if we look down from the North Pole we are effectively working with a 2D circle of radius R·cos(φ), yielding

x = R·cos(φ)·cos(σ)
y = R·cos(φ)·sin(σ)

You can now plug these back into the prior equations find that R drops out of the equation for θ.

Eric007 likes this.
11. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
That will depend on the resolution he needs. It will also depend on how big the distances are that he is working with. While he's given 5 km as an example, he might also at times want all objects within 500 km or 5000 km.

Jan 18, 2008
6,391
1,230

13. ### WBahn Moderator

Mar 31, 2012
23,101
6,949
Neither can I, which is why I'm hoping he will fill in some more of these details. In the meantime, all I can do is offer solutions that aren't dependent on them or try to give an idea of the limits of those solutions.

14. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,140
38
Maybe a flat earth would be a good approximation as I need a very simple solution since it contribute only 1/5 of my overall solution.
Oh it is already 12:28am and my system is shutting down already...

Mar 31, 2012
23,101
6,949