3

I need to write a java program to find from a given GPS position P, the nearest set (2 positions) of GPS positions(from a set of GPS positions) am GPS position. The situation is illustrated in the figure Here all the positions marked are GPS positions. From the given position P, i want to find the set of points which are nearest to P, in this case (B,C).

Here all the positions marked are GPS positions. From the given position P, i want to find the set of points which are nearest to P, in this case (B,C)

It would be really helpful if anyone could share an algorithm or code snippnet related to this.

Simon Warta
  • 10,850
  • 5
  • 40
  • 78
java_new
  • 83
  • 1
  • 7
  • 3
    just subtract the coordinates a,b,c,d and e from p ? the smallest win! – Danny. Sep 12 '13 at 13:24
  • @DanP. That's just completely false. It's not even an Euclidian distance!! – johan d Sep 12 '13 at 13:30
  • @ndj There are other distance functions apart from the Euclidian distance function. However, the question probably asks for the Euclidian distance function. – RaptorDotCpp Sep 12 '13 at 13:35
  • @RaptorDotCpp: I know that, I just said "it's not even an Euclidian distance" :) See my answer for more details. – johan d Sep 12 '13 at 14:01

4 Answers4

4

You have to compute the distance between P and all the other points, then take the min. That was the obvious part.

The difficult part is to compute the distance between two gps coordinate. GPS use the WGS84 geodesic system to represent points on earth. There is also different ways to compute a distance on a ~sphere (loxodromic distance and great circle distance are the main ones). Euclidian distance is always false on a sphere (not even close) because at non-zero latitude, 1°Lat < 1°Lon...
See Distance using WGS84-ellipsoid for the computation by yourself, or GDAL if you accept a lib which will do it for you.

You can use GDAL to convert points representations in others geodesic systems. You can for instance project points on a plan geodesic system, then use (x,y,z) coordinates, then compute distances (or better: squared distance = x²+y²+z²).

I think the google map api provide an easy to use distance methode for gps coordinate, if by chance your already using it.

Community
  • 1
  • 1
johan d
  • 2,798
  • 18
  • 26
2

Store the points into a list and then find the neighbouring points or minimum distance points.

This post might be helpfull to you.

Community
  • 1
  • 1
code_fish
  • 3,381
  • 5
  • 47
  • 90
1

If you're looking for an algorithmic implementation check out R-Trees. They can be a good way to look for point or bounding-box type of searches.

There is a great library I have been using for some time that works well for me that has implemented the R-Tree algorithm. Check out JSI, Java Spatial Index (http://jsi.sourceforge.net/).

I'll leave the exploration of the API to you. Good luck!

Baldy
  • 2,002
  • 14
  • 14
1

You might consider making a Quadtree out of the data. It's a way of representing 2-d spacial data making it easy to do nearest neighbor lookups in log(n) time. Construction of the tree is nlog(n) though so if you need to consider construction and nearest neighbor then you'd have nlog(n) complexity.

It shouldn't be hard to find a nearest neighbor algorithm for a quadtree (which is just a 2-d version of a k-d tree). Wiki gives a general overview of it here

For further reading if you need to expand this to any other number of dimensions you should read up on K-D Trees.

EDIT: It just hit me that if you're needing to construct the Quadtree it'll be faster to just loop through all of the other points, find the distances and keep track of the smallest 2. If you're unsure of finding the distance think back to triangles and the Pythagorean Theorem.

Don
  • 3,987
  • 15
  • 32