How can I sort a coordinate list for a rectangle counterclockwise?

Question

I need to sort a coordinate list for a rectangle counterclockwise, and make the north-east corner the first coordinate. These are geographic coordinates (i.e. Longitude, Latitude) in decimal form.¹

For example, here are the 4 corners of a rectangle, starting with the north-west corner and moving clockwise:

[
  { "lat": 34.495239, "lng": -118.127747 }, # north-west
  { "lat": 34.495239, "lng": -117.147217 }, # north-east
  { "lat": 34.095174, "lng": -117.147217 }, # south-east
  { "lat": 34.095174, "lng": -118.127747 }  # south-west
]

I need to sort these counterclockwise and change the "anchor"/starting point to be north-east:

[
  { "lat": 34.495239, "lng": -117.147217 }, # north-east
  { "lat": 34.495239, "lng": -118.127747 }, # north-west
  { "lat": 34.095174, "lng": -118.127747 }, # south-west
  { "lat": 34.095174, "lng": -117.147217 }  # south-east
]

I do not know what order the list will be in initially (i.e. clockwise or counterclockwise). I do not know which corner the first coordinate in the list represents.

---

¹_{This is not a true rectangle when mapped to the surface of the earth, however since I do have 2 opposing corners I am calling it a rectangle for readability. Shapes that wrap +180/-180 longitude or +90/-90 latitude are not an issue.}

Answer 1

solution seems pretty straightforward:

>>> import math
>>> mlat = sum(x['lat'] for x in l) / len(l)
>>> mlng = sum(x['lng'] for x in l) / len(l)
>>> def algo(x):
    return (math.atan2(x['lat'] - mlat, x['lng'] - mlng) + 2 * math.pi) % (2*math.pi)

>>> l.sort(key=algo)

basically, algo normalises the input into the [0, 2pi] space and it would be naturally sorted "counter-clockwise". Note that the % operator and the * operator have the same precedence so the parenthesis around (2*math.pi) are important to get a valid result.

Answer 2

Assuming that your "rectangles" are always parallel to the equator and meridians (that's what your example implies, but it's not stated explicitely), i.e. you have just two pairs of different lat and lng values: (lat0, lat1) and (lng0, lng1).

You get following 4 corners:

NE: (lat = max(lat0, lat1), lng = max(lng0, lng1))
NW: (lat = max(lat0, lat1), lng = min(lng0, lng1))
SW: (lat = min(lat0, lat1), lng = min(lng0, lng1))
SE: (lat = min(lat0, lat1), lng = max(lng0, lng1))

(this is not supposed to be python code)