Вопросы к 17 - p1xelse/CG GitHub Wiki

Какую задачу решает алгоритм?

Последовательное отсечение многоугольника выпуклым (только) отсекателем.

Отверстия могут быть в отсекаемом многоугольнике?

Нет, не могут.

Если многоугольники не пересекаются, поиск результата тем же путём производится, или требуется отдельное решение? (Аналогия с алгоритмом Вейлера-Азертона)

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

В нашем алгоритме:

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

  1. Быть внешними по отношению к друг другу. (результат нулевой)

  2. Многоугольник полностью внутри (не пересекая рёбра отсекателя). (результат - все вершины видимы)

  3. Многоугольник полность охватывает отсекатель (отсекатель внутри и не пересекает рёбра многоугольника). (результат - будут видимы (?))

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

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

Сколько списков у алгоритма?

1 список

В чём причина ложных рёбер?

Список у нас один. Соответственно в него же повторно и попадают новые многоугольники.

Что заносим в список?

Точки пересечения и вершины.

Какой математикой пользуемся? Как решаем вопросы с видимостью?

Из математики у нас скалярные и векторные произведения, а так же пробная функция.

Способ 1

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

Способ 2

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

Способ 3

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

Знак (+) или 0 точка видима. Знак (–) точка невидима.