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

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

Вот функция, которая должна проверять, находится ли точка в полигоне. Я использую метод литья лучей

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)

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

Ответы

Ответ 1

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

Ответ 2

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

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() является нормальным членом вместо вложенной утилиты.
  • Вместо многих вложенных структур if вы также можете проверить обратное, а затем continue или использовать and.

Ответ 3

Шаги:

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

Использование функции intersect из Этот СОСТОЙЧИК

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 должен быть максимальной точкой на оси x на рисунке.