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

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

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

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

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

Solution 5

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.

View more solutions

Comments

[Crescent Fresh]

I don't know if the list starts at NW. Sorry if that was unclear.

[Crescent Fresh]

I need more than the direction, I need the list sorted in the order posted for further operations.

[Crescent Fresh]

"Rebuilding" the list from two opposing corners is equivalent to sorting the entire list I suppose, albeit a bit unorthodox.

[Aaron]

@Crescent Fresh - Knowing the direction is the first step to sorting it properly, isn't it? If you need it in counter-clockwise order and the list as is is in clockwise order then you reverse the list and - ta da - you have it in counter-clockwise order.

[Adrian McCarthy]

+1 because this explanation is clearer than mine and makes the assumption explicit

[Crescent Fresh]

@Curd: the footnote at the bottom of the question was trying to convey what you stated (didn't want to get into Lines of Lat/Lng in the question). Anyway, finding the opposing corners (lat0, lat1) and (lng0, lng1) is itself a search for minimum and maximum points (yielding SW and NE corners respectively), correct?

[Crescent Fresh]

Sorry, I'm not making myself very clear: I need the list sorted starting with the north-east corner. Simply knowing the direction does not tell me which item in the list is north-east.

[Crescent Fresh]

Nice. This looks similar to what @tom10 was trying to convey (without the mapping to [0, 2pi]), is that right?

[SilentGhost]

yeah, haven't seen his reply before I've implemented my code. the only difference indeed is obtaining this order. and I've tested my code too :)

[Crescent Fresh]

@SilentGhost: you say in your answer the list will be sorted clockwise, but doesn't this actually sort it counterclockwise as I asked for?

[Crescent Fresh]

I wonder if this works crossing the equator or prime meridian (where lat/lng flips from - to +)...

[Crescent Fresh]

Should work fine actually. Would have liked it better without the swapping though ;) +1

[u0b34a0f6ae]

it is not possible without swapping: we need to sort north before south before we know which points are the southernmost, which we then sort reversely wrt east-west.

[SilentGhost]

@Crescent Fresh: sure, it sorts counter-clockwise, it was just a typo.

[Curd]

@Crescent Fresh: in your question above I don't understand what you mean by "opposing corners...". With "(lat0, lat1)" I just meant the list of your two latitude values. The order doesn't matter.

[Crescent Fresh]

@Curd: in my scenario I have 4 coordinates, not 2. Finding the 2 that you speak of is an effort to find 2 out of the 4 that are opposite to each other.