8

長方形の座標リストを反時計回りに並べ替えて、北東の角を最初の座標にする必要があります。これらは、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緯度をラップする形状は問題ではありません。

4

7 に答える 7

10

解決策はかなり簡単に思えます：

>>> 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) を括弧で囲むことが重要です。

于 2009-11-10T17:06:03.363 に答える
5

あなたの「長方形」が常に赤道と子午線に平行であると仮定すると（それはあなたの例が意味するものですが、明示的には述べられていません）、つまり、異なる緯度と経度の値のペアが2つしかありません：（lat0、lat1）と（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))

(これは Python コードではないはずです)

于 2009-11-10T17:10:40.593 に答える
3

並べ替えるのではなく、任意の順序で四角形を「再構築」することができます。

元のセットから、最小および最大緯度と最小および最大経度を収集します。次に、任意の順序で長方形を作成します。

北西の角は最高緯度、最低経度です。南西の角は、最小緯度と最小経度です。等。

于 2009-11-10T16:40:18.690 に答える
3

角度を各ポイント (内側のポイントに対して) に関連付けると、移動は簡単になります。

角度を計算するには、形状の中央にあるポイントを見つけます。たとえば、(average_lat, average_lng)中央になります。すると、atan2(lng - average_lng, lat - average_lat)その点の角度になります。

于 2009-11-10T16:40:24.790 に答える
1

コーナーから 2 つのベクトルの外積を取ると、結果の符号によって時計回りか反時計回りかがわかります。

于 2009-11-10T16:36:06.217 に答える
1

簡単です。まず、座標を並べ替えて、それらがどの順序であるかを確認してから、単純にそれらを選択します。

最初に緯度で並べ替え、次に長さで並べ替え、最大のものを先に並べます。次に、最後の 2 つを入れ替えます。

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

(キー関数のマイナスは、大きい値が小さい値の前にソートされるようにするためのものです。ソートにより、北を南の前に配置し、次に東を西の前に配置します。目的の順序を取得するには、最後 (南) の 2 つの値を交換するだけです。)

于 2009-11-10T18:07:06.777 に答える
0

ということで、4点です。

常に NW ポイントから開始します。

ポイントがソートされていることはわかっていますが、どの方向にあるかはわかりません。

リストが時計回りか反時計回りかの最初の 2 つのポイントの簡単なテストです。

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

于 2009-11-10T16:40:08.567 に答える