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

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

*Из названия понятно, что алгоритм работает корректно только с выпуклым отсекателем.

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

Почему для отсечения многоугольников нужен отдельный алгоритм:

Рассмотрим многоугольник и прямоугольный отсекатель:

После применения к каждому из ребер алгоритма отсечения отрезка получим:

Чтобы на выходе получить плоский многоугольник, необходимо дополнить наш результат (голубые линии):

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

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

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

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

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

Возможны четыре случая расположения ребра многоугольника относительно границы отсекателя.

Ребро может быть:

  1. Полностью невидимым относительно границы: Обе вершины невидимы, в результат ничего не заносим

  2. Частично видимым и входит в отсекатель: Начальная вершина ребра невидима, конечная – видима. Найти точку пересечения, занести в результат точку пересечения ребра с прямой, проходящей через границу отсекателя, и конечную точку ребра.

  3. Полностью видимым относительно границы: Обе вершины ребра видимы, обе должны быть занесены в результат. Но начальная вершина текущего ребра является конечной вершиной предыдущего ребра – следовательно, она уже будет занесена в результат на предыдущем шаге.

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

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

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

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

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

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

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

Способ3:

  1. Вводим вектор из начала ребра отсекателя в исследуемую точку.
  2. Вычислим векторное произведение директрисы ребра отсекателя (вектор от первой вершины ребра ко второй) и вектора, соединяющего первую вершину ребра с исследуемой точкой.
  3. Определить его знак:
  • Знак (+) или 0 точка видима.
  • Знак (–) точка невидима.

Определения факта пересечения ребром многоугольника прямой, проходящей через границу отсекателя:

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

Реализация алгоритма из матриалов

Из материалов:

  1. Ввод исходных данных: Np - количества вершин отсекаемого многоугольника, P - массива координат вершин отсекаемого многоугольника, Nc - количества вершин отсекателя, C - массива координат вершин отсекателя.
  2. Цикл по всем ребрам отсекателя.
  • 2.1. Обнуление количества вершин результирующего многоугольника Nq.
  • 2.2. Цикл по всем ребрам отсекаемого многоугольника.
    • 2.2.1. Анализ номера обрабатываемой вершины многоугольника: если j=1 (первая вершина), то ее координаты запоминаются в переменной F (F=P1). Переход к п. 2.2.5.
    • 2.2.2. Определение факта пересечения ребра многоугольника SPj и ребра отсекателя CjCj+1.
    • 2.2.3. Если пересечение ребер многоугольников установлено, то определение координат точки T пересечения этих ребер, иначе переход к п. 2.2.5.
    • 2.2.4. Увеличение на единицу количества вершин результирующего многоугольника Nq= Nq+1. Занесение в массив координат результирующего многоугольника координат найденной точки Q(Nq)=T.
    • 2.2.5. Изменение начальной точки ребра многоугольника: присвоение переменной S значения переменной Pj : S = Pj .
    • 2.2.6. Проверка видимости вершины S относительно ребра CjCj+1. Если вершина видима, то занесение ее координат в массив Q: Nq= Nq+1; Q(Nq)=S.
    • 2.2.7. Конец цикла по переменной j (цикл отсечения ребер многоугольника по текущей границе отсекателя).
  • 2.3. Проверка ненулевого количества вершин в результирующем массиве: если Nq=0, то многоугольник невидим относительно текущей границы отсекателя, следовательно, он невидим относительно всего отсекателя. Завершаем работу алгоритма.
  • 2.4. Проверка факта пересечения ребра многоугольника SF с ребром отсекателя CjCj+1.
  • 2.5.Если пересечение ребер многоугольников установлено, то определение координат точки T пересечения этих ребер, иначе переход к п. 2.7.
  • 2.6.Увеличение на единицу количества вершин результирующего много угольника Nq= Nq+1. Занесение в массив координат результирующего многоугольника координат найденной точки Q(Nq)=T.
  • 2.7. Присвоение полученных значений количества вершин и их координат результирующего многоугольника значениям количества вершин и их координат исходного многоугольника: Np =Nq , P=Q (полученный многоугольник отсекается далее следующей стороной отсекателя).
  • 2.8. Конец цикла отсечения по всем границам отсекателя.
  • 2.9. Визуализация полученного многоугольника P.
  • 2.10. Конец алгоритма.

Можно ли на промежуточных этапах установить невидимость многоугольника?

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

Для данных, приведенных на рис. в файле, покажите результат и объясните его.

Входные данные для алгоритма:

  1. Отсечение границей 01. Зеленым показана прямая, проходящая через границу. Синим показан результат отсечения многоугольника этой границей.

  1. Отсечение результата предыдущего шага (синим) границей 12. Оранжевым показана прямая, проходящая через границу. Зеленым показан результат отсечения многоугольника этой границей. Точки 1 и 9 совпадают и образуют вырожденное ребро.

  1. Отсечение результата прошлого шага (зеленым) границей 23. Красным показана прямая, проходящая через границу. Оранжевым показан результат отсечения этой границей. Точки 1 и 9 совпадают и образуют вырожденное ребро.

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

Пересечение каких геом. объектов вы ищете?

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

Как решается задача, если многоугольники не пересекаются?

Многоугольники не пересекаются если:

1. Если отсекаемый многоугольник полностью видим – целиком содержится внутри отсекателя

входной многоугольник – зеленый, отсекатель – красный

  1. Отсечение границей 01: в результат попадут точки многоугольника 01234, т.к. они видимы относительно текущей границы. Точек пересечения ребер с прямой, содержащей границу 01 нет.
  2. Отсечение границей 12: в результат попадут точки многоугольника 01234, т.к. они видимы относительно текущей границы. Точек пересечения ребер с прямой, содержащей границу 12 нет.
  3. Отсечение границей 23: в результат попадут точки многоугольника 01234, т.к. они видимы относительно текущей границы. Точек пересечения ребер с прямой, содержащей границу 23 нет.
  4. Отсечение границей 30: в результат попадут точки многоугольника 01234, т.к. они видимы относительно текущей границы. Точек пересечения ребер с прямой, содержащей границу 30 нет. Результирующий многоугольник совпадает с исходным.

2. Если отсекаемый многоугольник полностью невидим.

В этом случае входной многоугольник для отсечения очередной границей будет полностью невидим относительно этой границы -> полностью невидим относительно всего отсекателя

  1. Отсечение границе 01. Результат показан синим.

  1. Отсечение границей 12. Входной многоугольник – синий пунктир. В результирующий многоугольник ничего не попадет. В конце тела цикла по границам отсекателя (внешний цикл) проверяем: является ли полученный результат пустым? Да, является. Следовательно пунктирный многоугольник полностью невидим относительно границы
  1. Алгоритм завершается.

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