introduction

Au travail, j'avais besoin de créer un algorithme pour déterminer si un point de coordonnée arbitraire existe à l'intérieur ou à l'extérieur du polygone, je vais donc l'écrire sous forme d'article. Dans ce cas, il est utilisé pour informer des informations telles que OK s'il est à l'intérieur et NG s'il est à l'extérieur.

Façon de penser

Il existe plusieurs façons de déterminer si un point de coordonnées est à l'intérieur ou à l'extérieur, mais cette fois, nous utiliserons le produit extérieur des vecteurs.

Exemple

Supposons que vous ayez un polygone, comme le montre la figure ci-dessous. Cette fois, la forme à neuf côtés est prise comme exemple et entourée d'une ligne bleue. Le point rouge est un point arbitraire et détermine si ce point est à l'intérieur ou à l'extérieur du polygone.

la mise en oeuvre

Pour le moment, voici le code de ce polygone.



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


#Déterminez les points de coordonnées aux extrémités du polygone
(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])

#Entrez tout point de coordonnées que vous souhaitez trouver
#(X,Y)>(0,0)
point =np.array([6,3])

#Visualisation des polygones et des coordonnées arbitraires
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()


#Tous les calculs vectoriels
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)
        
#Tous les calculs de produits extérieurs
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)

#Inclure le résultat du produit externe dans la liste
        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)

#Fidèle à l'extérieur s'il y a au moins un positif dans la liste
#Sinon, faux à l'intérieur
if any((x >= 0 for x in list)) == True:
    print('Les points de coordonnées sont à l'extérieur du polygone')
else:
    print('Les points de coordonnées sont à l'intérieur du polygone')

Le code est assez sale, mais pas mal. Qu'est-ce que je fais ① Calculez le vecteur de chaque côté et des points de coordonnées arbitraires (Dans ce cas, le nombre de côtés est de 9, donc le vecteur de 9 côtés est calculé.) ② Calculez également le vecteur de chaque sommet à n'importe quel point de coordonnées ③ Trouvez le produit externe de chacun de ces vecteurs (4) Incluez la valeur du produit extérieur obtenue dans la liste et vérifiez-la.

Résumé

Pour le moment, j'étais capable de juger de l'intérieur ou de l'extérieur, alors j'ai décidé que tout allait bien. À l'avenir, nous l'étendrons à 3 dimensions et porterons des jugements internes et externes. J'espère que cela vous aidera.

référence

Le calcul du vecteur a été effectué en référence à la figure 2 sur le site suivant. https://gihyo.jp/dev/serial/01/as3/0055