Python: vérifier si le point est à l'intérieur d'un polygone
j'ai une classe décrivant un Point (A 2 coordonnées x et y) et une classe décrivant un polygone qui a une liste de Points qui correspondent à des coins (self.coin) Je dois vérifier si un Point est dans un polygone
Voici la fonction qui est censée vérifier si le point dans le polygone. J'utilise la méthode de moulage par rayons
def in_me(self, point):
result = False
n = len(self.corners)
p1x = int(self.corners[0].x)
p1y = int(self.corners[0].y)
for i in range(n+1):
p2x = int(self.corners[i % n].x)
p2y = int(self.corners[i % n].y)
if point.y > min(p1y,p2y):
if point.x <= max(p1x,p2x):
if p1y != p2y:
xinters = (point.y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
print xinters
if p1x == p2x or point.x <= xinters:
result = not result
p1x,p1y = p2x,p2y
return result
j'effectue un essai avec la forme et le point suivants:
PG1 = (0,0), (0,2), (2,2), (2,0)
point = (1,1)
Le script retourne heureusement False même si le point il dans la ligne. Je ne trouve pas l'erreur
3 réponses
je suggère d'utiliser la classe Path
de matplotlib
import matplotlib.path as mplPath
import numpy as np
poly = [190, 50, 500, 310]
bbPath = mplPath.Path(np.array([[poly[0], poly[1]],
[poly[1], poly[2]],
[poly[2], poly[3]],
[poly[3], poly[0]]]))
bbPath.contains_point((200, 100))
(il y a aussi une fonction contains_points
si vous voulez tester plusieurs points)
j'aimerais suggérer quelques autres changements:
def contains(self, point):
if not self.corners:
return False
def lines():
p0 = self.corners[-1]
for p1 in self.corners:
yield p0, p1
p0 = p1
for p1, p2 in lines():
... # perform actual checks here
Notes:
- un polygone avec 5 coins a aussi 5 lignes de limite, pas 6, votre boucle est une Hors.
- en utilisant une expression de générateur séparée indique clairement que vous vérifiez chaque ligne à tour de rôle.
- vérification d'un nombre de lignes vides a été ajouté. Cependant, comment traiter les lignes de longueur zéro et les polygones avec un seul coin est toujours ouverte.
- j'envisagerais aussi de faire fonctionner les lignes() comme un membre normal au lieu d'un utilitaire imbriqué.
- au lieu des nombreuses structures imbriquées, vous pouvez également vérifier l'inverse et ensuite
continue
ou utiliserand
.
Suit:
- itérer sur tous les segments du polygone
- vérifier s'ils se croisent avec un rayon allant dans le sens croissant-x
utilisant la fonction intersect
de This SO Question
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def point_in_polygon(pt, poly, inf):
result = False
for i in range(len(poly.corners)-1):
if intersect((poly.corners[i].x, poly.corners[i].y), ( poly.corners[i+1].x, poly.corners[i+1].y), (pt.x, pt.y), (inf, pt.y)):
result = not result
if intersect((poly.corners[-1].x, poly.corners[-1].y), (poly.corners[0].x, poly.corners[0].y), (pt.x, pt.y), (inf, pt.y)):
result = not result
return result
veuillez noter que le paramètre inf
doit être le point maximum dans l'axe des abscisses de votre figure.