Вопросы к 17 - chrislvt/CG GitHub Wiki
Какую задачу решает алгоритм?
Последовательное отсечение многоугольника выпуклым (только) отсекателем.
Отверстия могут быть в отсекаемом многоугольнике?
Нет, не могут.
Если многоугольники не пересекаются, поиск результата тем же путём производится, или требуется отдельное решение? (Аналогия с алгоритмом Вейлера-Азертона)
Аналогичную задачу Вейлером-Азертоном мы не решим, потому что там работа со списками основана на работе с точками пересечений (от одного многоугольника переходим к другому).
В нашем алгоритме:
В каких случаях многоугольники не пересекаются? Как они могут распологаться друг относительно друга?
-
Быть внешними по отношению к друг другу. (результат нулевой)
-
Многоугольник полностью внутри (не пересекая рёбра отсекателя). (результат - все вершины видимы)
-
Многоугольник полность охватывает отсекатель (отсекатель внутри и не пересекает рёбра многоугольника). (результат - будут видимы (?))
Пересечение каких геом. объектов вы ищете?
Отрезка, (то есть ребра многоугольника), с прямой, пересекающей этот отрезок (прямая проходит через ребро отсекателя).
Сколько списков у алгоритма?
1 список
В чём причина ложных рёбер?
Список у нас один. Соответственно в него же повторно и попадают новые многоугольники.
Что заносим в список?
Точки пересечения и вершины.
Какой математикой пользуемся? Как решаем вопросы с видимостью?
Из математики у нас скалярные и векторные произведения, а так же пробная функция.
Способ 1
Видимость точки относительно границы определяется с помощью скалярного произведения вектора внутренней нормали к границе на вектор, соединяющий произвольную точку границы с исследуемой точкой.
Способ 2
Использование пробной функции, получаемой из уравнения прямой, проходящей через ребро отсекателя, Ax + By + C: подставляя координаты исследуемой точки в пробную функцию, определяем знак пробной функции. Знак пробной функции необходимо сравнить со знаком пробной функции точки, положение которой нам известно.
Способ 3
Вводим вектор из начала ребра отсекателя в исследуемую точку. Вычислим векторное произведение директрисы ребра отсекателя (вектор от первой вершины ребра ко второй) и вектора, соединяющего первую вершину ребра с исследуемой точкой. Определить его знак:
Знак (+) или 0 точка видима. Знак (–) точка невидима.