Determining the method to get proper order of (lat, lang) pairs to draw a closed regular polygon of N Sides

Question

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.

Answer 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)