Comment trier une liste des coordonnées pour un rectangle anti-horaire?

Question

Je dois trier une liste des coordonnées pour un rectangle dans le sens antihoraire, et rendre le coin nord-est la première coordonnée. Ce sont des coordonnées géographiques (à savoir la longitude, latitude) sous forme décimale. ¹

Par exemple, voici les 4 coins d'un rectangle, en commençant par le coin nord-ouest et dans le sens horaire:

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

Je dois trier ces anti-horaire et changer le « point d'ancrage » / point de départ pour être nord-est:

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

Je ne sais pas quel ordre la liste sera dans un premier temps (à savoir dans le sens horaire ou anti-horaire). Je ne sais pas quel coin de la première coordonnée dans la liste représente.

---

¹ _{Ce n'est pas un vrai rectangle quand mappées à la surface de la terre, mais depuis que j'ai 2 coins opposés je l'appelle un rectangle pour une meilleure lisibilité. Des formes qui enveloppe + longitude 180 / -180 ou + 90 / -90 latitude ne sont pas un problème.}

Answer 1

solution semble assez 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)

En fait, l'entrée algo normalise dans l'espace [0, 2pi] et il serait réglé naturellement « dans le sens antihoraire ». Notez que l'opérateur% et l'opérateur * ont la même priorité si la parenthèse autour (2 * Math.PI.) sont importants pour obtenir un résultat valide.

Answer 2

En supposant que vos « rectangles » sont toujours parallèles à l'équateur et méridiens (c'est ce que votre exemple implique, mais il ne le dit pas explicitement), vous avez donc seulement deux paires de valeurs différentes lat et lng: (lat0, lat1) et (lng0, lng1).

Vous obtenez après 4 coins:

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

(ce n'est pas censé être le code python)

Answer 3

Au lieu de tri, il vous suffit de « reconstruire » le rectangle dans l'ordre que vous désirez.

De l'ensemble original, recueillir les minutes et la latitude max et min et la longitude max. Ensuite, construire le rectangle dans l'ordre que vous voulez.

coin nord-ouest est la latitude max et min longitude. coin sud-ouest est min latitude et la longitude min. Etc.

Answer 4

Associer un angle avec chaque point (par rapport à un point intérieur), puis déplacer est trivial.

Pour calculer l'angle, trouver un point au milieu de la forme, par exemple, (average_lat, average_lng) sera au centre. Ensuite, atan2(lng - average_lng, lat - average_lat) sera l'angle de ce point.

Answer 5

Si vous prenez la croix-produit de deux vecteurs à partir d'un coin alors le signe du résultat vous dira si elle est dans le sens horaire ou anti-horaire.

Answer 6

Il est facile. Tout d'abord, nous trions les coordonnées afin que nous sachions dans quel ordre nous les avons, nous les choisissons simplement:

Trier d'abord par les lat puis par lng, le plus grand premier. Ensuite, nous échangeons les deux derniers:

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

(Les points négatifs dans la fonction clé sont là pour que les grandes valeurs de tri avant des valeurs plus petites par tri, nous mettons au nord avant le sud, puis l'est avant l'ouest;. Pour obtenir l'ordre désiré on échange tout simplement les deux derniers (sud) valeurs. )

Answer 7

Alors, vous avez 4 points.

Vous commencez toujours avec le point NW.

Vous savez que les points sont classés, mais pas dans quelle direction.

Il est un test simple des deux premiers points si la liste est dans le sens horaire ou anti-horaire.

if (pt1.y! = Pt2.y) puis direction = dans le sens horaire.

Si vous constatez que les points sont dans le sens horaire, simple inverser les 3 derniers points dans la liste.

.

pointe dans le sens antihoraire: (0,1), (0,0), (1,0), (1,1)

pointe dans le sens horaire: (0,1), (1,1), (1,0), (0,0)

Vous pouvez voir si vous inversez pts2-4 votre liste dans le sens horaire devient anti-horaire.

EDIT:. J'ai eu mes points de départ de la NE, FixT