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

Question

I need to sort the coordinate list for the rectangle counterclockwise and make the northeast corner the first coordinate. These are geographic coordinates (i.e. Longitude, Latitude) in decimal form. ^one

For example, here are 4 corners of a rectangle, starting from the northwest 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 them counterclockwise and change the anchor / starting point to the northeast:

 [ { "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 have initially (i.e. clockwise or counterclockwise). I do not know in which corner the first coordinate in the list will be displayed.

---

¹ _{This is not a real rectangle when displayed on the surface of the earth, however, since I have 2 opposite angles, I call it a rectangle for readability. Forms that wrap + 180 / -180 longitude or + 90 / -90 latitude are not a problem.}

Answer 1

Decision

seems pretty simple:

 >>> 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 normalizes input into the space [0, 2pi] , and it is natural to sort it “counterclockwise”. Note that the% operator and the * operator have the same priority, so the parentheses around (2 * math.pi) are important to get the correct result.

Answer 2

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

You get the 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 should not be python code)

Answer 3

Instead of sorting, you can simply "rearrange" the rectangle in any order you need.

In the source set, collect the minimum and maximum latitude, as well as the minimum and maximum longitudes. Then build the rectangle in any order.

Northwest corner - maximum latitude and longitude mines. The southwest corner is min latitude and min longitude. Etc.

Answer 4

Associate a corner with each point (relative to the inside point), and then the movement around is trivial.

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

Answer 5

If you take the cross product of two vectors from an angle, then the sign of the result will tell you, clockwise or counterclockwise.

Answer 6

It is easy. First, we sort the coordinates so that we know in what order we have them, then we just select them:

Sort them first with lat, then lng, the largest first. Then we replace 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) 

Exit

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

(Cons in the key function exist so that large values ​​are sorted to smaller values. Sorting, we put north in front of the south, then east to west to get the desired order, we just replace the last two (southern) values.)

Answer 7

So, you have 4 points.

You always start from the point of NW.

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

This is a simple test of the first two points if the list is clockwise or counterclockwise.

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

If you find that the points are clockwise, simply flip the last 3 points in the list.

So.

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

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

You can see if you cancel pts2-4, your list will become counterclockwise clockwise.

EDIT: I had points starting with NE, fixt.