【Python】任意の座標点が多角形の内側か外側か判定

#はじめに
仕事で任意の座標点が多角形の内側か外側かどちらに存在するか判定するアルゴリズムを作る必要があったので、記事にします。
今回の場合、内側にあれば、OK、外側にあればNGというような情報を知らせることに用います。

#考え方
座標点が内側 or 外側かを判定する方法はいくつかありますが、今回はベクトルの外積を用います。

##例
以下の図のように、多角形があるとします。
今回は、九角形を例として、青線で囲っています。
赤い点は任意の点として、この点が多角形の内側 or 外側どちらに存在するかを判定します。

##実装
とりあえず、この多角形のコードを示します。

import numpy as np
import copy
import pandas as pd
import matplotlib.pyplot as plt


#多角形の端の座標点を決める
(x,y)>(0,0)
c1 =np.array([2,1])
c2 =np.array([1,3])
c3 =np.array([1,7])
c4 =np.array([3,6])
c5 =np.array([4,8])
c6 =np.array([6,9])
c7 =np.array([9,6])
c8 =np.array([8,3])
c9 =np.array([6,1])

#求めたい任意座標点の入力
#(X,Y)>(0,0)
point =np.array([6,3])

#多角形と任意座標の可視化
x = []
y = []
for i in range(1,10):
    exec('x_num = c{}[0]'.format(i))
    x.append(x_num)
    exec('y_num = c{}[1]'.format(i))
    y.append(y_num)
x.append(c1[0])
y.append(c1[1])
plt.plot(x, y, label="test")
plt.plot(point[0], point[1],marker="o",linestyle='None',markersize=6, color='red')
plt.show()


#全てのベクトル計算
for i in range(1,10):
    if i < 9:
        kakomi = 'vector_c{}c{} = (c{}-c{})'.format(i,i+1,i+1,i)
        exec(kakomi)
        uchigawa = 'vector_c{}point = (point-c{})'.format(i,i)
        exec(uchigawa)
    if i == 9:
        kakomi2 = 'vector_c{}c1 = (c1-c{})'.format(i,i)
        exec(kakomi2)
        uchigawa2 = 'vector_c{}point = (point-c{})'.format(i,i)
        exec(uchigawa2)
        
#全ての外積計算
for i in range(1,10):
    if i < 9:
        get = 'outer_product_c{}c{}_point = np.cross(vector_c{}c{}, vector_c{}point)'.format(i,i+1,i,i+1,i)
        exec(get)
    if i == 9:
        get2 = 'outer_product_c{}c1_point = np.cross(vector_c{}c1, vector_c{}point)'.format(i,i,i)
        exec(get2)

#外積結果をリストに内包する
        list =[]
for i in range(1,10):
    if i <9:
        s = eval('outer_product_c{}c{}_point'.format(i,i+1))
        list.append(s)
    if i == 9:
        t = eval('outer_product_c{}c1_point'.format(i))
        list.append(t)
print(list)

#リスト内に1つでも正数があれば、Trueで外側
#なければ、Falseで内側
if any((x >= 0 for x in list)) == True:
    print('座標点は多角形の外側')
else:
    print('座標点は多角形の内側')

コードはかなり汚いのですが、悪しからず。
やっていることとして、
①各辺と任意座標点のベクトルを計算する
（今回の場合、辺の数は、9本なので、9つの辺のベクトルを計算します。）
②また各頂点から任意座標点へのベクトルも計算する
③それらのベクトルのそれぞれの外積を求める
④求めた外積の値をlistに内包し、確認する。

#総括
ひとまず、内側 or 外側の判断はできたのでよしとしました。
今後は、3次元に拡張して内外判定を行います。
少しでも皆様の参考になれば幸いです。

#参考
下記サイトにおける図2を参考に、ベクトル計算を行いました。
https://gihyo.jp/dev/serial/01/as3/0055