Pythonでランダムに作成した平面上3頂点列の時計回り/反時計回りを判定する

久しぶりに小ネタ．

• 前回: Python+Scipyでランダムに作成した点から凸包を描く

平面上に3頂点をプロット

• わざと色付けてます

import numpy as np
import matplotlib.pyplot as plt

X = np.random.rand(3, 2)

fig = plt.figure(figsize=(2, 2))
ax = fig.gca()
ax.scatter(x=X[0, 0], y=X[0, 1], color='r')
ax.scatter(x=X[1, 0], y=X[1, 1], color='g')
ax.scatter(x=X[2, 0], y=X[2, 1], color='b')
ax.set_xlim(0., 1.)
ax.set_ylim(0., 1.)

• 適当に0番目の点を固定し，ベクトルを描いた場合は次のようになります
  • v01が0番目の頂点から1番目の頂点のベクトル
  • v02は0番目から2番目

v01 = np.array([X[1, 0] - X[0, 0], X[1, 1] - X[0, 1]])
v02 = np.array([X[2, 0] - X[0, 0], X[2, 1] - X[0, 1]])
fig = plt.figure(figsize=(2, 2))
ax = fig.gca()
ax.scatter(x=X[0, 0], y=X[0, 1], color='r')
ax.scatter(x=X[1, 0], y=X[1, 1], color='g')
ax.scatter(x=X[2, 0], y=X[2, 1], color='b')
ax.arrow(X[0, 0], X[0, 1], v01[0], v01[1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
ax.arrow(X[1, 0], X[1, 1], X[2, 0] - X[1, 0], X[2, 1] - X[1, 1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
ax.arrow(X[2, 0], X[2, 1], -v02[0], -v02[1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
ax.set_xlim(0., 1.)
ax.set_ylim(0., 1.)

時計周り/反時計回りの判定

• 頂点順序を0→1→2と見た時，これが三角形を「時計回り(CW)」するのか「反時計回り(CCW)」するのかを判定する

• 2つのベクトルv01とv02が計算できているので，外積を計算して正負を判定すれば良い

  • 2次元の場合，v01(x) v02(y) - v01(y) v02(x)

• 計算してタイトルに書いてみる

N = 3
for n in range(N):
    X = np.random.rand(3, 2)
    fig = plt.figure(figsize=(2, 2))
    v01 = np.array([X[1, 0] - X[0, 0], X[1, 1] - X[0, 1]])
    v02 = np.array([X[2, 0] - X[0, 0], X[2, 1] - X[0, 1]])
    z = v01[0] * v02[1] - v01[1] * v02[0]
    ax = fig.gca()
    ax.scatter(x=X[0, 0], y=X[0, 1], color='r')
    ax.scatter(x=X[1, 0], y=X[1, 1], color='g')
    ax.scatter(x=X[2, 0], y=X[2, 1], color='b')
    ax.arrow(X[0, 0], X[0, 1], v01[0], v01[1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
    ax.arrow(X[1, 0], X[1, 1], X[2, 0] - X[1, 0], X[2, 1] - X[1, 1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
    ax.arrow(X[2, 0], X[2, 1], -v02[0], -v02[1], length_includes_head=True, head_width=0.03, color='k', zorder=-1)
    ax.set_xlim(0., 1.)
    ax.set_ylim(0., 1.)
    title = "CCW" if z > 0 else "CW"
    ax.set_title(title)

• 結果(例)

参考

• おぼろげな高校数学の知識
• ３点の座標から簡単に角度と回転方向を求める．