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

35
demandé sur Helena 2013-05-18 18:43:13

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)

54
répondu P.R. 2016-07-08 12:17:03

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 utiliser and .
3
répondu Ulrich Eckhardt 2013-05-18 17:47:34

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.

0
répondu DCPY 2017-05-23 11:47:26