偏角ソート
$ x軸の正方向と、原点と座標$ (x_0,y_0)を結ぶ線分がなす角（偏角）の大きさでソートする。
考え方
$ 2点の偏角の大きさが比較できれば十分。その比較関数をcmp_to_keyでソートのkeyに渡せばソートができる。
$ p(p_x,p_y),q(q_x,q_y)を比較する。$ pの偏角を$ \thetaとする。
$ qの偏角による外積の正負・比較関数が返すべき値の変化を見てみると以下のようになる。 https://scrapbox.io/files/676a653d352927020f090465.jpg
図の赤の範囲$ [0,\theta)で、外積は負、返すべき値は$ 1
図の紫の範囲$ [\theta,\theta\rbrackで外積は$ 0、返すべき値は$ 0
図の青の範囲$ (\theta,\theta+\pi)で外積は正、返すべき値は$ -1
図の緑の範囲$ [\theta+\pi,\theta+\pi\rbrackで外積は$ 0、返すべき値は$ -1
図の桃の範囲$ (\theta+\pi,2\pi)の範囲で外積は負、返すべき値は$ -1
赤・紫・青は使えそうだが、緑と桃は壊れている。
$ pと$ qの偏角の差が$ \pi以上にならないように、先に領域を分割するとうまくいく。
$ 2点が$ [0,\pi),$ [\pi,2\pi)のどちらの領域に属しているかそれぞれ判定する。
領域が異なるなら、その時点で大小関係が定まる。
領域が同じとき、偏角の差は$ \pi未満なので、外積で大小関係が判定できる。
領域の判定は$ (p_y,p_x)と$ (0,0)を辞書順で比較するだけでできる。
code: sort_by_arg.py
from random import sample
P = [(1, 0),
(1, 1),
(0, 1),
(-1, 1),
(-1, 0),
(-1, -1),
(0, -1),
(1, -1)]
Q = sample(P, len(P))
from functools import cmp_to_key
def arg_cmp(p, q):
px, py = p
qx, qy = q
area_p = (0, 0) >= (py, px)
area_q = (0, 0) >= (qy, qx)
if area_p < area_q:
return -1
elif area_p > area_q:
return 1
cp = px * qy - py * qx
if cp > 0:
return -1
elif cp < 0:
return 1
else:
return 0
Q.sort(key=cmp_to_key(arg_cmp))
print(Q)