Как проверить, находится ли pointsD в строках многоугольника python 2.7 (без импорта)

Question

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

def point_inside_polygon(x, y, poly):
    n = len(poly)
    inside = False

    p1x, p1y = poly[0]
    for i in range(n + 1):
        p2x, p2y = poly[i % n]
        if y > min(p1y, p2y):
            if y <= max(p1y, p2y):
                if x <= max(p1x, p2x):
                    if p1y != p2y:
                        xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x, p1y = p2x, p2y    
    return inside

Ну, я проверил это как с точками, так и с полигоном:

point_inside_polygon(0.3,0.5,[(0.5,0),(1,0.5),(0.5,1),(0,0.5)]) point_inside_polygon(0.3,1,[(0.5,0),(1,0.5),(0.5,1),(0,0.5)])

и, конечно, вывод был правильным:

True,False

Затем я попытался использовать его сам с небольшими изменениями, которые я мог сделать, чтобы он соответствовал моей программе:

class Point2D:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __str__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"
    def __repr__(self):
        return self.__str__()

class Polygon2D:
    def __init__(self, pts):
        self.points = pts       
    def __repr__(self):
        return str(self.points) 
    def is_inside(self, q):
        n = len(self.points)
        inside = False
        p1x, p1y = self.points[0]
        for i in range(n + 1):
            p2x, p2y = self.points[i % n]
            if q.y > min(p1y, p2y):
                if q.y <= max(p1y, p2y):
                    if q.x <= max(p1x, p2x):
                        if p1y != p2y:
                            xinters = (q.y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                        if p1x == p2x or q.x <= xinters:
                            inside = not inside
        p1x, p1y = p2x, p2y
        return inside

И когда я попробовал:

p.is_inside(Point2D(0.3, 0.5))
p.is_inside(Point2D(0.3, 1))

вывод был неверным: ложь, правда.

Помогите?

Answer 1

Отступ вашего p1x, p1y = p2x, p2y в случае с классом это неправильно. Это должно быть в for i in range(n + 1): петля. Теперь он выполняется только перед возвратом.

правильный:

class Point2D:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"

    def __repr__(self):
        return self.__str__()

class Polygon2D:
    def __init__(self, pts):
        self.points = pts       

    def __repr__(self):
        return str(self.points) 

    def is_inside(self, q):
        n = len(self.points)
        inside = False
        p1x, p1y = self.points[0]

        for i in range(n + 1):
            p2x, p2y = self.points[i % n]
            if q.y > min(p1y, p2y):
                if q.y <= max(p1y, p2y):
                    if q.x <= max(p1x, p2x):
                        if p1y != p2y:
                            xinters = (q.y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                        if p1x == p2x or q.x <= xinters:
                            inside = not inside
            p1x, p1y = p2x, p2y
        return inside

дает:

>> True
>> False