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

If you take the cross-product of two vectors from a corner then the sign of the result will tell you if it's clockwise or counterclockwise.

Answer 2

So, you have 4 points.

You always start with the NW point.

You know that the points are sorted, just not in which direction.

It's a simple test of the first two points whether the list is clockwise or counter clockwise.

if (pt1.y != pt2.y) then direction = clockwise.

If you detect that the points are clockwise, simple reverse the last 3 points in the list.

So.

Counter clockwise points: (0,1), (0,0), (1,0), (1,1)

Clockwise points: (0,1), (1,1), (1,0), (0,0)

You can see if you reverse pts2-4 your clockwise list becomes counterclockwise.

EDIT: I had my points starting from the NE, fixt.

Answer 3

Rather than sorting, you can just "rebuild" the rectangle in any order you desire.

From the original set, collect the min and max latitude and min and max longitude. Then construct the rectangle in any order you want.

Northwest corner is max latitude and min longitude. Southwest corner is min latitude and min longitude. Etc.

Answer 4

Associate an angle with each point (relative to an interior point), and then moving around is trivial.

To calculate the angle, find a point in the middle of the shape, for example, (average_lat, average_lng) will be in the center. Then, atan2(lng - average_lng, lat - average_lat) will be the angle of that point.

Answer 5

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".

Answer 6

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)

Answer 7

It is easy. First, we sort the coordinates so we know in which order we have them, then we simply pick them out:

Sort them first by lat then by lng, biggest first. Then we swap the last two:

L = [
  { "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
]


L = sorted(L, key=lambda k: (-k["lat"], -k["lng"]))

L[-2], L[-1] = L[-1], L[-2]
import pprint
pprint.pprint(L)

output

[{'lat': 34.495238999999998, 'lng': -117.147217},
 {'lat': 34.495238999999998, 'lng': -118.127747},
 {'lat': 34.095174, 'lng': -118.127747},
 {'lat': 34.095174, 'lng': -117.147217}]

(The minuses in the key function are there so that bigger values sort before smaller values. By sorting we put north before south, then east before west; to get the desired order we simply swap the two last (southern) values.)