Где закралась ошибка в реализации алгоритма Кируса-Бека?

Question

[Wolko_dav]

Дорого времени всем. Второй день бюсь над этим алгоритмом.

Реализовать получилось, но он не работает.... Ошибка не вижу в упор... Требуется помощь.

mult = lambda a, b: a.x * b.x + a.y * b.y


class Point(object):
    def __init__(self, x, y):
        self.x = float(x)
        self.y = float(y)


class Line(object):
    def __init__(self, begin, end):
        self.begin = begin
        self.end = end

    @property
    def direction(self):
        return Point(self.end.x - self.begin.x, self.end.y - self.begin.y)

    @property
    def normal(self):
        return Point(self.end.y - self.begin.y, self.begin.x - self.end.x)


class Polygon(object):
    def __init__(self, points):
        self.count = len(points)
        self.edges = []
        for i in xrange(self.count-1):
            self.edges.append(Line(points[i], points[i+1]))

        self.edges.append(Line(points[-1], points[1]))
    # Реализаця алгоритма!
    def cyruse_beck(self, l):
        t_begin = 0.0
        t_end = 1.0
        dirL = l.direction
        for edge in self.edges:
            dir_edg = edge.direction
            Q = Point(l.begin.x - dir_edg.x, l.begin.y - dir_edg.y)
            N = edge.normal
            Pn = mult(dirL, N)
            Qn = mult(Q, N)
            if Pn == 0:
                if Qn < 0:
                    return False
            else:
                t = -Qn / Pn
                if Pn < 0:
                    if t < t_begin:
                        return False
                    t_end = min(t_end, t)
                else:
                    if t > t_end:
                        return False
                    t_begin = max(t_begin, t)

        if t_end > t_begin:
            if t_begin > 0:
                l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y)
            if t_end < 1:
                l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y)
        else:
            return False
        return True

Answer 1

[jcmvbkbc]

По коду:

self.edges.append(Line(points[-1], points[1]))

Наверно всё-таки self.edges.append(Line(points[-1], points[0]))

if t_begin > 0:
    l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y)
if t_end < 1:
    l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y)

В это место вы можете прийти с t_begin > 0 и t_end < 1, но t_begin и t_end будут в терминах исходного отрезка. Вы же во второй if попадёте с уже изменённым отрезком.

Думаю, что должно быть так:

mult = lambda a, b: a.x * b.x + a.y * b.y


class Point(object):
    def __init__(self, x, y):
        self.x = float(x)
        self.y = float(y)

    def __str__(self):
        return "(%s, %s)" % (self.x, self.y)


class Line(object):
    def __init__(self, begin, end):
        self.begin = begin
        self.end = end

    def __str__(self):
        return "{%s - %s}" % (self.begin, self.end)

    @property
    def direction(self):
        return Point(self.end.x - self.begin.x, self.end.y - self.begin.y)

    @property
    def normal(self):
        return Point(self.end.y - self.begin.y, self.begin.x - self.end.x)


class Polygon(object):
    def __init__(self, points):
        self.count = len(points)
        self.edges = []
        for i in xrange(self.count-1):
            self.edges.append(Line(points[i], points[i+1]))

        self.edges.append(Line(points[-1], points[0]))
    def cyruse_beck(self, l):
        t_begin = 0.0
        t_end = 1.0
        dirL = l.direction
        for edge in self.edges:
            dir_edg = edge.direction
            Q = Point(l.begin.x - edge.begin.x, l.begin.y - edge.begin.y)
            N = edge.normal
            Pn = mult(dirL, N)
            Qn = mult(Q, N)
            if Pn == 0:
                if Qn < 0:
                    return False
            else:
                t = -Qn / Pn
                if Pn > 0:
                    if t < t_begin:
                        return False
                    t_end = min(t_end, t)
                else:
                    if t > t_end:
                        return False
                    t_begin = max(t_begin, t)

        if t_end > t_begin:
            if t_end < 1:
                l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y)
            if t_begin > 0:
                l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y)
        else:
            return False
        return True

p = Polygon([Point(0, 0), Point(2, 0), Point(2, 2), Point(0, 2)]);
l = Line(Point(-0.5, -0.5), Point(2.5, 2.5))
print(p.cyruse_beck(l))
print("Line: %s" % l)
l = Line(Point(-0.5, -0.5), Point(2.5, -0.5))
print(p.cyruse_beck(l))
l = Line(Point(0, -1), Point(3, 2))
print(p.cyruse_beck(l))
print("Line: %s" % l)

Comments

[Wolko_dav]

@jcmvbkbc эмм, боюсь тут проблемы будут, просто это работа с графикой... Я потом рисую это. Сейчас попробую исправить это. Пример допустим: Многоугольник: 0 0, 2 0, 2 2, 0 2, 0 0 2 2. Он должен после выполнения в l лежать 0 0, 2 0.

[Wolko_dav]

А в итоге в t_end, t_begin = 0, 0. И возвращается False.

[Wolko_dav]

Видать не все ошибки исправил, не работает.

[jcmvbkbc]

Обновил ответ

Answer 2

[xandox]

У тебя нормаль точно в нужную сторону повернута?

Answer 3

[Wolko_dav]

Решено.

mult = lambda a, b: a.x * b.x + a.y * b.y


class Point(object):
    def __init__(self, x, y):
        self.x = float(x)
        self.y = float(y)


class Line(object):
    def __init__(self, begin, end):
        self.begin = begin
        self.end = end

    @property
    def direction(self):
        return Point(self.end.x - self.begin.x, self.end.y - self.begin.y)

    @property
    def normal(self):
        return Point(self.end.y - self.begin.y, self.begin.x - self.end.x)


class Polygon(object):
    def __init__(self, points):
        self.count = len(points)
        self.edges = []
        for i in xrange(self.count-1):
            self.edges.append(Line(points[i], points[i+1]))

        self.edges.append(Line(points[-1], points[0]))
    # Реализаця алгоритма!
    def cyruse_beck(self, l):
        t_begin = 0.0
        t_end = 1.0
        dirL = l.direction
        for edge in self.edges:
            dir_edg = edge.direction
            Q = Point(l.begin.x - dir_edg.x, l.begin.y - dir_edg.y)
            N = edge.normal
            Pn = mult(dirL, N)
            Qn = mult(Q, N)
            if Pn == 0:
                pass
            else:
                t = -Qn / Pn
                if Pn > 0:
                    if t < t_begin:
                        return False
                    t_end = min(t_end, t)
                else:
                    if t > t_end:
                        return False
                    t_begin = max(t_begin, t)

        if t_end > t_begin:
            if t_begin > 0:
                l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y)
            if t_end < 1:
                l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y)
        else:
            return False
        return True

Comments

[jcmvbkbc]

> self.edges.append(Line(points[-1], points[1]))
должно быть
self.edges.append(Line(points[-1], points[0]))

[jcmvbkbc]

if t_begin > 0:
l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y)
if t_end < 1:
l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y)

порядок if неверный

[jcmvbkbc]

Q = Point(l.begin.x - dir_edg.x, l.begin.y - dir_edg.y)

и тут тоже ошибка

[Wolko_dav]

Это почему? Что с конструктором накасячил, понял, забыл тут исправить, а вот про порядок не важно.

[jcmvbkbc]

я вам в своём ответе уже написал почему

[jcmvbkbc]

и тестовый пример там в конце. Ваш код с ним неправильно работает.