1

Currently in the process of implementing a service call the fetches some (Lat, lng) pairs from the DB and then process them to determine a definitive order so that the points are arranged in a way so that if I start with a pencil from first point and go through the ordered points I end up drawing a closed polygon with N sides.

To make it more clear consider the (Lat, Lng) pairs as below:

(42.45, -73), (34, -78), (42.78, -72.45), (42.98, -72.56)..and so on..

What I could think of was like if we determine four points:

  1. (topLeft)

  2. (bottomLeft)

  3. (bottomRight)

  4. (topRight)

then we may start drawing the first line like (topLeft)--->(bottomLeft) and as there will be many points that fall in the line so we go through scanning them on the way to (bottomLeft) and so on...

The criteria for topLeft may be like (min(lat), max(lng)) out of all the (lat, lng) pairs.

Please advice if the above Algorithm is a way to accomplish the task or there are better ways to do the same?

Note:- Using Java.

Anirudh
  • 2,286
  • 4
  • 38
  • 64

1 Answers1

1

I'd do it by

  • Determine the geographical centre (ie. average of latitudes/average of longitudes)
  • Determine the angle from the centre to each of the points
  • sort these angles
  • Draw the points in order of angles.

Just be VERY careful if the points can span the date line (180 degrees longitude)

racraman
  • 4,988
  • 1
  • 16
  • 16
  • Thanks! but I am not actually the one rendering the polygon, I am basically ordering the points so that one can draw a closed polygon in that order, so as I see it, you would be getting the ordered points at the point when you "sort these angles"? – Anirudh Jan 15 '14 at 06:44
  • 1
    That's right. This algorithm should guarantee that the points will be returned in an order such that there will be no crossing lines when drawn. – racraman Jan 15 '14 at 07:27
  • 1
    If the points are very close (and away from the international date line!), you could just approximate it with normal cartesian X,Y equations. Otherwise, there's this : http://stackoverflow.com/questions/3932502/calcute-angle-between-two-latitude-longitude-points – racraman Jan 15 '14 at 07:29