Отсечение многоугольной областью

1.

Отсечение многоугольной
областью

2.

Содержание
• Отсечение выпуклым многоугольником
• Клиппирование многоугольников
• Алгоритм Сазерленда-Ходжмена

3.

Отсечение выпуклым
многоугольником
Простой анализ с помощью кодов Сазерленда-Коэна в
такой ситуации неприменим.
Здесь нужен надежный и достаточно
эффективный алгоритм нахождения точки пересечения
двух произвольно ориентированных отрезков, а
также алгоритм определения местоположения точки
относительно многоугольника (внутри, снаружи или на
границе).
Рассмотрим задачу о пересечении отрезка с концами
с выпуклым многоугольником, заданным списком ребер.
Ребро может быть задано в виде пары точек
из множества вершин многоугольника

4.

5.

Выпуклость
То обстоятельство, что многоугольник выпуклый,
является очень существенным: это позволяет
использовать достаточно простой алгоритм,
использующий внутренние нормали к его
сторонам.
Под внутренней нормалью понимается вектор,
перпендикулярный стороне и направленный
внутрь многоугольника.
Как и в предыдущем алгоритме, воспользуемся
параметрическим уравнением прямой,
проходящей через концы отрезка:

6.

Определение параметра точки
пересечения
Если при некотором значении параметра
эта прямая пересекается с прямой, проходящей через точки
, то вектор, соединяющий произвольную точку ребра с точкой ,
будет перпендикулярен вектору нормали.
Следовательно, скалярное произведение векторов
и
будет равно нулю.
Отсюда получаем ..

7.

Определение параметра точки
пересечения
Использование этой формулы предполагает, что
, т.е. что отрезок не параллелен стороне многоугольника, но этот случай
рассматривается отдельно.
Найденная точка принадлежит отрезку при условии
Условие принадлежности этой точки ребру многоугольника также можно
выразить через скалярное произведение, так как векторы
и
в этом случае должны быть одинаково направленными, т.е.
.

8.

Определение внутренней точки
Для каждого отрезка возможны три случая взаимного расположения с
многоугольником:
• точек пересечения нет;
• существует одна точка пересечения;
• существуют две точки пересечения.
В каждом из этих вариантов для нахождения пересечения отрезка с
окном необходимо уметь определять принадлежность точки
выпуклому многоугольнику. Из рис. видно, что если для любой
точки , принадлежащей многоугольнику (или его границе), и
произвольной точки ребра
построить вектор
, то выполняется условие
, поскольку угол между векторами не может превышать 90 . Таким
образом, если данное условие выполняется для всех ребер
многоугольника, то точка является внутренней.

9.

Анализ расположения концов
отрезка
Таким образом, алгоритм отсечения отрезка начинается с анализа
расположения концов отрезка по отношению к окну. Если обе точки лежат
внутри окна, то отрезок полностью видимый, и
дальнейший поиск прекращается.
Если только одна из точек лежит внутри окна, то имеет место случай II, и
предстоит найти одну точку пересечения. И, наконец, если обе точки лежат
вне окна, то существуют либо две точки пересечения (отрезок пересекает
две границы окна), либо ни одной (отрезок полностью невидим). Впрочем,
две точки пересечения могут совпадать (если отрезок проходит через
вершину многоугольника), но этот случай в дополнительном анализе не
нуждается.
Далее выполняется цикл по всем ребрам многоугольника с целью нахождения
точек пересечения. Для каждого ребра перед началом поиска пересечения
необходимо проверить, не параллельно ли оно с отрезком. Если это так, то
можно вычислить расстояние от одного из концов отрезка до прямой,
проходящей через ребро . При
отрезок лежит на прямой, и остается
определить взаимное расположение концов отрезка и концов ребра, что
можно сделать простым покоординатным сравнением. При
отрезок не имеет общих точек с данным ребром.

10.

Клиппирование многоугольников
От задачи отсечения отрезков можно перейти к более
сложной: клиппирование произвольных
многоугольников.
Если многоугольник невыпуклый, то в результате
пересечения даже с прямоугольным окном может
получиться несколько не связанных между собой
фигур

11.

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

12.

Алгоритм Сазерленда-Ходжмена
Идея его заключается в последовательном отсечении части
многоугольника прямыми, соответствующими сторонам окна.
Результатом его работы является упорядоченный список вершин,
лежащих в видимой части окна.
На каждом шаге алгоритма образуется некоторая промежуточная фигура,
также представленная упорядоченным списком вершин и ребер.
Пример таких последовательных отсечений показан на рис..
В процессе отсечения последовательно обходится список вершин,
причем каждая очередная точка за исключением первой
рассматривается как конечная точка ребра, начальной точкой
которого является предшествующая точка из списка.
Порядок, в котором рассматриваются стороны окна, не имеет значения. В
процессе обхода формируется список новых вершин многоугольника.

13.

Алгоритм Сазерленда-Ходжмена

14.

Содержание
• https://www.intuit.ru/studies/professional_ski
ll_improvements/1283/courses/70/lecture