Python: verificando si el punto está dentro de un polígono

scripting polygon

Question

Tengo una clase que describe un punto (tiene 2 coordenadas xey) y una clase que describe un polígono que tiene una lista de puntos que corresponden a esquinas (autocoronas). Necesito verificar si un punto está en un polígono.

Aquí está la función que se supone que verifica si el punto en el polígono. Estoy usando el método Ray Casting

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

Ejecuto una prueba con la siguiente forma y punto:

PG1 = (0,0), (0,2), (2,2), (2,0)
point = (1,1)

La secuencia de comandos felizmente devuelve falso aunque el punto dentro de la línea. No puedo encontrar el error

Answer 1

Me gustaría sugerir algunos otros cambios allí:

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

Notas:

• Un polígono con 5 esquinas también tiene 5 líneas de delimitación, no 6, su ciclo está desactivado.
• El uso de una expresión de generador por separado deja en claro que está revisando cada línea por turno.
• Se agregó la verificación de un número vacío de líneas. Sin embargo, la forma de tratar líneas y polígonos de longitud cero con una sola esquina todavía está abierta.
• También consideraría hacer que las líneas () funcionen como un miembro normal en lugar de una utilidad anidada.
• En lugar de las muchas estructuras anidadas si, también puede verificar la inversa y luego continue o usar and .

Answer 2

Pasos:

• Iterato sobre todos los segmentos en el polígono
• Comprueba si se cruzan con un rayo que va en dirección creciente x

Usando la función 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

Tenga en cuenta que el parámetro inf debe ser el punto máximo en el eje x en su figura.

Answer 3

Sugeriría usar la clase 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))

(También hay una función contains_points si desea probar varios puntos)