🧭
偏角ソートのテンプレート（Python 実装）
はじめに
偏角ソートを Python で実装した記事が見当たらなかったため、テンプレートを用意しました。
このテンプレートは原点から見た
実装にあたっては ABC 442 E - Laser Takahashi 解説 を参考にさせていただきました。詳しい実装方針についてもこちらで解説されています。
もしコードや説明に誤りがあればコメントにてご指摘ください。
偏角ソートの定義
この記事でいう偏角ソートとは、次の定義に従ったソートアルゴリズムを指します。
- 原点
(0, 0) (1, 0) - 本来偏角は複素数平面上の点に対して定義される語だが、本記事では通例にならってこの語を用いる
- 偏角が小さいほうから順に並べる
- 偏角が等しい場合、原点との距離が小さいほうから順に並べる
- 原点の偏角は未定義だが、実装上ソート対象に含まれる場合は最小の要素として扱われる
- 原点は予めソート対象から取り除くことを推奨する
テンプレート
def half(p):
"""点 p が上半平面 (y > 0 または +x 軸上) に属する場合は 0 を, さもなくば 1 を返す"""
x, y = p
if y > 0 or (y == 0 and x >= 0):
return 0
else:
return 1
def cross(a, b):
"""原点から見たベクトル a, b の外積 (符号付き面積) の値を返す"""
ax, ay = a
bx, by = b
return ax * by - ay * bx
def norm2(p):
"""点 p の原点からの距離の二乗を返す"""
x, y = p
return x * x + y * y
def angle_cmp(a, b):
"""点 a, b の偏角と距離に基づく比較関数"""
ha = half(a)
hb = half(b)
if ha < hb:
return -1
elif ha > hb:
return 1
c = cross(a, b)
if c > 0:
return -1
elif c < 0:
return 1
da = norm2(a)
db = norm2(b)
if da < db:
return -1
elif da > db:
return 1
return 0
def is_same_dir(a, b):
"""点 a, b が原点でなく, かつ原点を始点とする同一半直線上にある場合は True を, さもなくば False を返す"""
if (a[0] == 0 and a[1] == 0) or (b[0] == 0 and b[1] == 0):
return False
return half(a) == half(b) and cross(a, b) == 0
使い方
functools ライブラリの cmp_to_key 関数を用いて比較関数（本テンプレートの angle_cmp）を評価関数に変換し、それを sort メソッドや sorted 関数の key 属性に渡してソートします。
if __name__ == "__main__":
import random
from functools import cmp_to_key
points = [
(0, 0), # 動作確認のため原点を含めているが, 実用上は原点を含めないことを推奨
(1, 0),
(1, 1),
(2, 2),
(0, 1),
(-1, 1),
(-1, 0),
(-1, -1),
(0, -1),
(1, -1),
]
# points をシャッフルする
random.shuffle(points)
print(points)
# => [(2, 2), (1, -1), (1, 1), (1, 0), (-1, 1), (0, 0), (0, 1), (-1, -1), (-1, 0), (0, -1)]
# points に対して偏角ソートを行った結果を得る (sorted 関数)
sorted_points = sorted(points, key=cmp_to_key(angle_cmp))
print(sorted_points)
# => [(0, 0), (1, 0), (1, 1), (2, 2), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
# points に対して inplace に偏角ソートを行う (sort メソッド)
points.sort(key=cmp_to_key(angle_cmp))
print(points)
# => [(0, 0), (1, 0), (1, 1), (2, 2), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
# 原点から見た角度が等しいか否か (同一半直線上にあるかどうか) を判定する
print(is_same_dir((1, 2), (2, 4))) # => True
print(is_same_dir((1, 2), (-1, -2))) # => False
# is_same_dir の引数に (0, 0) が含まれる場合は常に False を返す
print(is_same_dir((1, 0), (0, 0))) # => False
print(is_same_dir((0, 0), (1, 0))) # => False
Discussion