Einführung

Bei der Arbeit musste ich einen Algorithmus erstellen, um festzustellen, ob ein beliebiger Koordinatenpunkt innerhalb oder außerhalb des Polygons existiert, also werde ich ihn als Artikel schreiben. In diesem Fall werden Informationen wie OK (innen) und NG (außen) angezeigt.

Denkweise

Es gibt verschiedene Möglichkeiten, um festzustellen, ob sich ein Koordinatenpunkt innerhalb oder außerhalb befindet. Dieses Mal verwenden wir jedoch das äußere Produkt der Vektoren.

Beispiel

Angenommen, Sie haben ein Polygon, wie in der folgenden Abbildung gezeigt. Diesmal wird die neunseitige Form als Beispiel genommen und von einer blauen Linie umgeben. Der rote Punkt ist ein beliebiger Punkt und bestimmt, ob dieser Punkt innerhalb oder außerhalb des Polygons liegt.

Implementierung

Hier ist vorerst der Code für dieses Polygon.



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


#Bestimmen Sie die Koordinatenpunkte an den Enden des Polygons
(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])

#Geben Sie einen beliebigen Koordinatenpunkt ein, den Sie suchen möchten
#(X,Y)>(0,0)
point =np.array([6,3])

#Visualisierung von Polygonen und beliebigen Koordinaten
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()


#Alle Vektorberechnungen
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)
        
#Alle äußeren Produktberechnung
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)

#Nehmen Sie das äußere Produktergebnis in die Liste auf
        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)

#Nach außen wahr, wenn mindestens ein Positiv in der Liste enthalten ist
#Wenn nicht, innen falsch
if any((x >= 0 for x in list)) == True:
    print('Koordinatenpunkte liegen außerhalb des Polygons')
else:
    print('Koordinatenpunkte befinden sich innerhalb des Polygons')

Der Code ist ziemlich schmutzig, aber nicht schlecht. Was mache ich ① Berechnen Sie den Vektor jeder Seite und beliebige Koordinatenpunkte (In diesem Fall beträgt die Anzahl der Seiten 9, sodass der Vektor von 9 Seiten berechnet wird.) ② Berechnen Sie auch den Vektor von jedem Scheitelpunkt zu einem beliebigen Koordinatenpunkt ③ Finden Sie das äußere Produkt jedes dieser Vektoren (4) Nehmen Sie den erhaltenen äußeren Produktwert in die Liste auf und überprüfen Sie ihn.

Zusammenfassung

Vorläufig konnte ich das Innere oder das Äußere beurteilen, also entschied ich, dass es in Ordnung war. In Zukunft werden wir es auf drei Dimensionen erweitern und interne und externe Urteile fällen. Ich hoffe, es wird Ihnen helfen.

Referenz

Die Vektorberechnung wurde unter Bezugnahme auf Fig. 2 an der folgenden Stelle durchgeführt. https://gihyo.jp/dev/serial/01/as3/0055