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

Для решения поставленной задачи отсечения многоугольника выпуклым отсекателем недостаточно знать алгоритм отсечения отрезков Кируса-Бека, так как в решении задачи нам требуется «отсечь» часть плоскости, ограниченной заданной ломаной линией. Таким образом, при решении задачи от нас потребуется найти замкнутую ломанную линию, которая будет состоять не только из участков рёбер заданного исходного многоугольника, но и будет содержать в себе в качестве результата участки рёбер отсекателя. Господами Сазерлендом и Ходжменом было предложено решать данную задачу последовательно, то есть выполнять отсечение многоугольника последовательно каждой границей отсекателя и результат, полученный на очередном шаге, является исходным многоугольником для выполнения отсечения следующей границей отсекателя. При решении задачи мы должны последовательно определять видимость рассматриваемых вершин многоугольника и определять точки пересечения его рёбер с границами отсекателя.

Опишем алгоритм на конкретном примере:

В качестве первой рассматриваемой границы отсекателя возьмём границу C1-C2. Вершина A1 невидима относительно левой границы отсекателя, поэтому в результат она занесена не будет. Вершина A2 видима относительно левой границы отсекателя. Видимость вершины A1 и A2 разная, а значит, ребро многоугольника пересекает рассматриваемую границу отсекателя. В таком случае нужно определить точку пересечения текущего ребра с границей и занести найденную точку в результат. Анализируя видимость следующих вершин (A3, A4, A5, A6, A7), убеждаемся, что все они видимы относительно текущей границы отсекателя, и все они попадают в результат. По завершению текущего шага потребуется сформировать замыкающее ребро многоугольника – A7-A1. Анализируя видимость этих вершин, будет определено, что ребро многоугольника пересекает текущую границу отсекателя. Поэтому будет найдена точка пересечения, которую мы и занесём в результат. Таким образом, по окончанию выполнения описанного выше шага будем иметь следующий результат:

Рассмотрим следующий шаг (граница отсекателя C2-C3). Вершина A1 невидима относительно текущей границы отсекателя, следовательно, в результат она не заносится. Вершина A2 также невидима. Вершина A3 видима. Видимость вершин ребра A2-A3 разная, следовательно, требуется найти точку пересечения. В результат будут занесены найденная точка пересечения рассматриваемого ребра с границей отсекателя и вершина A3. Следующие рассматриваемые вершины (A4, A5, A6, A7, A8) видимы и требуется определить замыкающее ребро: вершина A8 видима, A1 невидима, следовательно требуется найти точку пересечения данного ребра с верхней границей отсекателя и внести в результат вершину A8 и найденную точку пересечения.

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

Рассмотрим следующий шаг (граница отсекателя C3-C4). Вершина A1 видима. Вершина A2 видима. Вершина A3 невидима. Имеем разную видимость концов ребра, находим точку пересечения и заносим её в результат. Для ребра A3-A4 ситуация аналогичная. Находим точку пересечения этого ребра с границей отсекателя и заносим её в результат. Вершины A4, A5, A6, A7, A8 видимы, заносим их в результат.

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

Рассмотрим следующий шаг (граница отсекателя C1-C4). Вершина A1 видима. Вершина A2 видима. Вершина A3, A4, A5 видимы. Вершина A6 невидима, следовательно, находим точку пересечения рёбер A5-A6 и A6-A7 с рассматриваемой границей отсекателя и точки пересечения занесём в результат. Оставшиеся рёбра будут видимыми относительно рассматриваемой границы отсекателя.

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

Таким образом, для реализации алгоритма нужно уметь решать следующие задачи: определение видимости вершин отсекаемого многоугольника относительно отсекателя и нахождение точек пересечения рёбер многоугольника со сторонами отсекателя.

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

Определение видимости точки относительно стороны отсекателя

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

Также возможен ещё один способ определения видимости точки посредством использования пробной функции, получаемой из уравнения прямой, проходящей через ребро отсекателя. При этом уравнение прямой: Ax+By+C. Подставляя координаты исследуемой точки в пробную функцию, мы определяем её знак. Полученный знак сравнивается со знаком пробной функции точки, положение которой нам известно.

Также имеется возможность использовать способ, основанный на векторном произведении. Допустим, что у нас есть некоторый отсекатель, изображённый на следующем рисунке:

Для решения поставленной задачи требуется вычислить векторное произведение векторов C_i A и C_i C_(i+1).

Далее достаточно просто проанализировать знак полученного произведения:

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

Если полученное значение нулевое, то точка находится на границе отсекателя, а, следовательно, видима.

Если знак отрицателен, то точка невидима относительно текущей границы отсекателя.

Определение точки пересечения ребра отсекаемого многоугольника с границей отсекателя

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

P(t)=P_1+(P_2-P_1 )t,0≤t≤1 – ребро отсекаемого многоугольника

Q(s)=Q_1+(Q_2-Q_1 )s – граница отсекателя

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

Таким образом, чтобы найти требующуюся точку пересечения будем иметь:

P(t)=Q(s)

То есть получаем систему двух уравнений с двумя неизвестными, решаем его и получаем значение параметра соответствующей точки пересечения. После этого вычисляются x и y координаты точки пересечения.

Расположение рёбер многоугольника относительно внутренней области отсекателя

В данном случае обе вершины невидимы, следовательно, в результат ничего не заносится.

В данном случае начальная вершина невидима, а конечная вершина видима. Потребуется найти точку пересечения и занести в результат найденную и конечную точки.

В данном случае обе вершины видимы, следовательно, обе вершины заносятся в результат, но начальная вершина текущего ребра является конечной вершиной предыдущего ребра – она будет занесена в результат не предыдущем шаге.

В данном случае начальная вершина видима, а конечная – невидима. Начальная вершина будет занесена в результат на предыдущем шаге, а на текущем шаге потребуется определить точку пересечения и занести её в результат.

Недостаток алгоритма

Главным недостатком описываемого алгоритма является появление ложных рёбер, то есть тех рёбер, которых быть не должно. Такие рёбра возникают в том случае, когда в результате отсечения получается несколько не связанных друг с другом многоугольников.

Ложное ребро - ребро, не являющееся границами результирующих многоугольников. Почему оно появляется? - Алгоритм подразумевает что мы создаем один многоугольник, а получается их несколько.

Пример такой ситуации предоставлен ниже:

Алгоритм:

1. Ввод исходных данных: N_p- количество вершин отсекаемого многоугольника, P- массива координат вершин отсекаемого 
многоугольника,  N_c- количество вершин отсекателя, C- массива координат вершин отсекателя. Элементами массивов являются 
записи, каждая из которых содержит два поля – координаты x и y вершины. Для удобства работы алгоритма первая вершина 
отсекателя заносится в массив C дважды: на первое место и ещё раз в конец массива (это сделано потому, что последнее ребро
 отсекателя образуется последней и первой вершинами многоугольника).
2. Цикл по всем рёбрам отсекателя (переменная цикла i изменяется от 1 до N_c).
2.1. Обнуление количества вершин результирующего многоугольника N_q.
2.2. Цикл по всем рёбрам отсекаемого многоугольника (переменная цикла j изменяется от 1 до N_c).
2.2.1. Анализ номера обрабатываемой вершины многоугольника: если j=1 (первая вершина), то её координаты запоминаются в 
переменной F(F=P_1).
Переход к пункту 2.2.7.
2.2.2. Определение факта пересечения ребра многоугольника SP_j и ребра отсекателя C_j C_(j+1).
2.2.3. Если пересечение рёбер многоугольников установлено, то определение координат точки T пересечения этих рёбер, иначе
 переход к пункту 2.2.7.
2.2.4. Увеличение на единицу количества вершин результирующего многоугольника N_q=N_q+1. Занесение в массив координат 
результирующего многоугольника координат найденной точки Q(N_q )=T.
2.2.5. Изменение начальной точки ребра многоугольника: присвоение переменной S значения переменной P_j:S=P_j
2.2.6. Проверка видимости вершины S относительно ребра C_j C_(j+1). Если вершина видима, то занесение её координат в 
массив Q:N_q=N_q+1;Q(N_q )=S.
2.2.7. Конец цикла по переменной j (цикл отсечения рёбер многоугольника по текущей границе отсекателя).
2.3. Проверка ненулевого количества вершин в результирующем массиве: если N_q=0, то переход к пункту 2.10 (многоугольник
 невидим относительно текущей границы отсекателя, следовательно, он невидим относительно всего отсекателя).
2.4. Проверка факта пересечения ребра многоугольника SF с ребром отсекателя C_j C_(j+1).
2.5. Если пересечение рёбер многоугольников установлено, то определение координат точки T пересечения этих рёбер, иначе
 переход к пункту 2.
2.6. Увеличение на единицу количества вершин результирующего многоугольника N_q=N_(q+1). Занесение в массив координат 
результирующего многоугольника координат найденной точки Q(N_q )=T.
2.7. Присвоение полученных значений количества вершин и их координат исходного многоугольника: N_p=N_q,P=Q (полученный 
многоугольника отсекается далее следующей стороной отсекателя).
2.8. Конец цикла по переменной i (цикл отсечения по все границам отсекателя).
2.9. Визуализация полученного многоугольника P.
2.10. Конец алгоритма.

Следующий вопрос: 18. Отсечение многоугольников невыпуклыми областями. Алгоритм Вейлера Азертона.

Предыдущий вопрос: 16. Внутреннее и внешнее отсечение. Определение выпуклости многоугольника; определение нормали; разбиение невыпуклых многоугольников. Триангуляция многоугольников.