0
$\begingroup$

I have a database of locations. Each location is a latitude and longitude pair. Now for each query, I want to get top "X" nearest locations around a given latitude longitude point. How do I actually calculate the distance between two lat long points and is there any efficient algorithm to do this instead of a simple for loop?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This is more of a maths question than an engineering one $\endgroup$
    – Fred
    Apr 18, 2018 at 12:07
  • $\begingroup$ quadtree. You want a quadtree. It is a very nice data structure. I suggest to visit cs.stackexchange.com . $\endgroup$
    – peterh
    Apr 18, 2018 at 19:47
  • $\begingroup$ The equation can be found via google. $\endgroup$
    – paparazzo
    Apr 23, 2018 at 14:34

1 Answer 1

Reset to default
1
$\begingroup$

Your question comes down to a basic math problem. You have two points in polar coordinates you want to find the distance between.

For simplicity, it is probably acceptable to model the earth as a sphere. Convert each polar coordinate to cartesian. Now you subtract them and compute the square root of the sum of the squares of the components.

Note that the above method gives you straight line distance. If all your "near here" regions are small enough, then that is a valid approximation. If your distance are large enough so that you want to take the curvature of the earth into account, then you need to find the angle between the two points as seen from the center of the earth.

Find the vectors from the center of the earth to each point, unitize these vectors, then take the dot product. The angle between the points is the arc-cosine of this dot product.

Beware of precision. On a computer, you will probably want to use "double precision" for any cartesian components.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.