Python: проверка наличия точки внутри многоугольника

Question

У меня есть класс, описывающий точку (имеет 2 координаты x и y) и класс, описывающий многоугольник, который имеет список точек, соответствующих углам (self.corners) I нужно проверить, находится ли точка в полигоне

Вот функция, которая должна проверять, находится ли точка в полигоне. Я использую 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 

Я бегу тест с последующей формой и точкой:

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

Сценарий счастливо возвращает значение False, даже если точка его в линии. Я не могу найти ошибку

Answer 1

Я хотел бы предложить некоторые изменения есть:

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 

Примечания:

• многоугольник с 5 углами также имеет 5 ограничительные линии, а не 6 , ваша петля одна.
• Использование отдельного выражения генератора ясно показывает, что вы проверяете каждую строку по очереди.
• Была добавлена ​​проверка на наличие пустого количества строк. Однако, как обрабатывать линии нулевой длины и многоугольники с одним углом, по-прежнему открыты.
• Я также считаю, что функция lines() является нормальным членом вместо вложенной утилиты.
• Вместо множества вложенных структур, вы также можете проверить обратное, а затем continue или использовать and.

Answer 2

Я предложил бы использовать Path класс от 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)) 

(Существует также contains_points функция, если вы хотите проверить несколько точек)

Answer 3

Шаги:

• Итерация по всем сегментам в многоугольнике
• Проверить пересекаются ли они с луч, идущий в увеличении-х направлении

Использование функции intersect из 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 

Пожалуйста, обратите внимание, что параметр inf должен быть точкой максимума в оси х в твоя фигура.