시계 반대 방향으로 사각형의 좌표 목록을 어떻게 정렬 할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1709283

문제

시계 반대 방향으로 사각형의 좌표 목록을 정렬하고 북동쪽 코너를 첫 번째 좌표로 만들어야합니다. 이것들은 10 진수 형태의 지리적 좌표 (즉, 경도, 위도)입니다.1

예를 들어, 북서쪽 코너부터 시작하여 시계 방향으로 움직이는 사각형의 4 모서리가 있습니다.

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

이 시계 반대 방향으로 정렬하고 북동쪽으로 "앵커"/출발점을 변경해야합니다.

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

나는 목록이 처음에 어떤 순서가 될지 모른다 (즉, 시계 방향 또는 시계 반대 방향). 목록의 첫 번째 좌표가 어떤 코너를 나타내는 지 모르겠습니다.

1이것은 지구의 표면에 매핑 될 때 진정한 사각형이 아니지만, 2 개의 반대 코너가 있기 때문에 가독성을위한 사각형이라고 부릅니다. +180/-180 경도 또는 +90/-90 위도를 랩핑하는 모양은 문제가되지 않습니다.

도움이 되었습니까?

해결책

솔루션은 매우 간단 해 보입니다.

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

원래, algo 입력을 정상화합니다 [0, 2pi] 공간과 그것은 자연스럽게 "시계 반대 방향"으로 분류됩니다. % 연산자와 * 연산자는 동일한 우선 순위를 가지므로 (2 * math.pi) 주변의 괄호는 유효한 결과를 얻는 데 중요합니다.

다른 팁

"직사각형"이 항상 적도 및 자오선과 평행하다고 가정하면 (예 : 예제가 의미하는 바이지만 설명 적으로 명시되지는 않음), 즉 두 쌍의 LAT와 LNG 값이 있습니다 : (lat0, lat1) 및 (lng0, (lng0,) lng1).

4 개의 코너를 따릅니다.

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

(이것은 파이썬 코드가되어서는 안됩니다)

정렬하지 않고 원하는 순서로 사각형을 "재 구축"할 수 있습니다.

원래 세트에서 최소 및 최대 위도 및 최소 및 최대 경도를 수집하십시오. 그런 다음 원하는 순서로 사각형을 구성하십시오.

북서쪽 코너는 최대 위도와 최소 경도입니다. 남서쪽 코너는 최소 위도 및 최소 경도입니다. 등.

각 지점과 각도를 연관 시키면 (내부 지점과 관련하여), 움직이는 것은 사소한 일입니다.

각도를 계산하려면 모양 중간의 점을 찾으십시오. (average_lat, average_lng) 중앙에있을 것입니다. 그 다음에, atan2(lng - average_lng, lat - average_lat) 그 시점의 각도가 될 것입니다.

코너에서 두 벡터의 교차 제품을 가져 오면 결과의 부호는 시계 방향 또는 시계 반대 방향인지 알려줍니다.

쉽습니다. 먼저, 우리는 좌표를 정렬하여 우리가 어떤 순서로 가지고 있는지 알 수 있도록 다음과 같이 선택합니다.

LNG에 의해 먼저 LNG로 먼저 분류하십시오. 그런 다음 마지막 두 가지를 교환합니다.

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)

산출

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

(핵심 함수의 마이너스는 더 큰 값이 작은 값 앞에 분류되도록 존재합니다. 정렬하여 우리는 남쪽 앞에서 북쪽으로, 서쪽 앞에 동쪽으로 두는 것입니다. 원하는 순서를 얻으려면 단순히 두 개의 마지막 (남쪽) 값을 교환합니다.)

따라서 4 점이 있습니다.

당신은 항상 NW 지점으로 시작합니다.

당신은 포인트가 어떤 방향이 아닌지에 분류된다는 것을 알고 있습니다.

목록이 시계 방향이든 시계 방향인지 여부는 처음 두 지점의 간단한 테스트입니다.

if (pt1.y! = pt2.y) 그런 다음 방향 = 시계 방향.

포인트가 시계 방향으로 감지되면 단순한 목록의 마지막 3 점을 반전시킵니다.

그래서.

시계 방향 지점 : (0,1), (0,0), (1,0), (1,1)

시계 방향 지점 : (0,1), (1,1), (1,0), (0,0)

PTS2-4 시계 방향 목록이 시계 반대 방향으로 반대되는지 확인할 수 있습니다.

편집 : NE, Fixt에서 시작했습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top