Pythonで極角に基づいてデカルト座標点のセットを並べ替えるプログラム

リストpointsに格納された一連のデカルト座標点（直交座標点）を考えます。これらの点を、それぞれの極角（偏角）に基づいて並べ替える必要があります。極角は0から2πの範囲で表されます。もし複数の点が同じ極角を持つ場合は、その点の原点からの距離に基づいて並べ替えます。

例えば、入力が points = [(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)] の場合、

出力は [(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)] となります。

解決のための手順

この問題を解くために、以下の手順に従います。

• 比較用の関数 key() を定義します。この関数は点 x を引数として受け取ります。
• atan := x[1]/x[0] の逆正接（アークタンジェント）を計算します。
• atan >= 0 の場合はペア (atan, x[1]^2 + x[0]^2) を返し、そうでなければ (2*pi + atan, x[0]^2 + x[1]^2) を返します。
• この比較関数 key() を使って points を並べ替えます。

なお、Pythonの math.atan2(y, x) が返す角度の範囲は −π〜π であるため、負の値になった場合は 2π を加算することで、0〜2π の範囲に正規化できます。また、第2要素には原点からの距離の二乗（x² + y²）を使用することで、平方根の計算を避けつつ距離による比較を実現しています。

実装例

理解を深めるために、以下の実装を見てみましょう。

import math
def solve(points):
    def key(x):
        atan = math.atan2(x[1], x[0])
        return (atan, x[1]**2+x[0]**2) if atan >= 0 else (2*math.pi + atan, x[0]**2+x[1]**2)

    return sorted(points, key=key)

points = [(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)]
print(solve(points))

入力

[(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)]

出力

[(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)]