Introduction

At work, I needed to create an algorithm to determine whether an arbitrary coordinate point exists inside or outside the polygon, so I will write it as an article. In this case, it is used to inform information such as OK if it is inside and NG if it is outside.

Way of thinking

There are several ways to determine if a coordinate point is inside or outside, but this time we will use the vector cross product.

Example

Suppose you have a polygon, as shown in the figure below. This time, the nonagon is taken as an example and surrounded by a blue line. The red dot is an arbitrary point and determines whether this point is inside or outside the polygon.

Implementation

For now, here's the code for this polygon.



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


#Determine the coordinate points at the ends of the polygon
(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])

#Input the desired coordinate point
#(X,Y)>(0,0)
point =np.array([6,3])

#Visualization of polygons and arbitrary coordinates
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()


#All vector calculations
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)
        
#All cross product calculations
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)

#Include cross product results in a list
        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)

#True to the outside if there is at least one positive number in the list
#If not, False inside
if any((x >= 0 for x in list)) == True:
    print('The coordinate points are outside the polygon')
else:
    print('The coordinate points are inside the polygon')

The code is pretty dirty, but not bad. What I'm doing ① Calculate the vector of each side and arbitrary coordinate points (In this case, the number of sides is 9, so the vector of 9 sides is calculated.) ② Also calculate the vector from each vertex to any coordinate point ③ Find the cross product of each of those vectors ④ Include the obtained cross product value in the list and check it.

Summary

For the time being, I was able to judge the inside or outside, so I decided it was okay. In the future, we will expand it to three dimensions and make internal and external judgments. I hope it will be of some help to you.

reference

Vector calculation was performed with reference to Fig. 2 on the following site. https://gihyo.jp/dev/serial/01/as3/0055