17. Отсечение многоугольников. Алгоритм Сазерленда Ходжмена.

Возможные варианты взаимного расположения.

1. обе вершины отрезка SP видимы, отрезок целиком видим. В результат заносятся точки S и P
2. Обе вершины невидимы, отрезок целиком невидим. В результат заносится 0 точек
3. S невидима, P видима, отрезок частично видим. В результат заносится точка пересечения (надо найти) и P.
4. Наоборот. S и точка пересечения.

Алгоритм

1. определить видимость точки (вершины рёбер)
   а) использовать скалярное произведение PjAi(вектор из вершины в точки) * n(внутр нормаль), >=0 точка видима, <0 невидима(как в Кирусе-Беке)

   б) использовать пробную функцию (на основе уравнения прямой/совпадающей с ребром многоугольника) F =ax + by + c знак функции для исследуемой функции надо сравнить со знаком пробной функции точки, положение которой известно

   в) использование векторного произведения AiPj(из вершины в точку) * AiAi+1(вектор совпадающ с ребром), >=0 точка Pj видима(есди равно точка на границе и она видима) контур обходится по часовой стрелке

2. находить точки пересечения(убедиться в ее наличии)
   искать точку пересечения ребра многоугольника с прямой == стороной отсекателя(когда видимость концов ребра различная)

В данном алгоритме рассматривается конкретный вариант нахождения: ищется точка пересечения прямой, проходящей через ребро отсекателя, с ребром отсекаемого многоугольника. Поскольку отрезки имеют произвольное расположение, удобно использовать параметрическую форму записи: P(t) = P1 + (P2-P1)t, где 0<=t<=1 – ребро многоугольника, и Q(s) = Q1 + (Q2-Q1)s – ребро отсекателя.(прямая s без ограничений) P(t)=Q(s): Предварительно нужно убедиться в непараллельности прямых – точка пересечения должна существовать. Это определяется с помощью видимости концов ребра многоугольника – если видимость разная, то точка пересечения есть. Начальная вершина очередного ребра является одновременно и конечной вершиной для предыдущего ребра. Эта вершина анализируется (и заносится в результат если видима) на предыдущем шаге.

Данный алгоритм имеет недостаток – можно столкнуться с ситуацией построения «ложных ребер» (I2I3).

Мы работаем с массивом вершин, вершины обходятся последовательно – ложным будет ребро, которое обходится два раза.

Алгоритм

def sutherland_hodgman(clip, pol, norm):
    # дублируем начальную вершину отсекателя в конец
    clip.append(clip[0])

    s = None
    f = None
    # цикл по вершинам отсекателя
    for i in range(len(clip) - 1):
        new = []  # новый массив вершин
        for j in range(len(pol)):    # цикл по вершинам многоугольника
            if j == 0:
                f = pol[j]
            else:
                t = is_intersection([s, pol[j]], [clip[i], clip[i + 1]], norm)
                if t:
                    new.append(t)

            s = pol[j]
            if is_visiable(s,  clip[i], clip[i + 1], norm):
                    new.append(s)

        if len(new) != 0:
            t = is_intersection([s, f], [clip[i], clip[i + 1]], norm)
            if t:
                new.append(t)

        pol = copy.deepcopy(new)

    if len(pol) == 0:
        return False
    else:
        return QPolygonF(pol)