15.4. РАЗРЕЗАНИЕ ПРОИЗВОЛЬНОГО МНОГОУГОЛЬНИКА ПРОИЗВОЛЬНОЙ ПРЯМОЙ
При воспроизведении изображения многоугольника, который может не быть выпуклым на участке окна наблюдения, представляющего собой правильный прямоугольник, можно либо рассмотреть разрезание каждой из сторон многоугольника окном (с помощью алгоритма 15.2), либо разрезание всего многоугольника каждой из сторон окна. Для решения последней задачи предназначен алгоритм 15.3. Его можно также использовать в качестве базового алгоритма для определения пересечения двух произвольных многоугольников.
Этот алгоритм предусматривает вычисление 
для всех вершин с помощью уравнений (15.2). (Поскольку в процессе работы алгоритма пары вершин обрабатываются последовательно, новое значение 
равно предыдущему значению 
, следовательно, 
для каждой вершины должно вычисляться только один раз.) Предполагается, что направление прямой соответствует допущению 14.1 и видны те точки, которые не загораживают прямую (см. определение 14.2). Таким образом, если значение 
положительно, то соответствующая вершина видна. На шаге 3 сравниваются знаки 
, если хотя бы одно из этих значений положительно, алгоритм переходит к выполнению шагов 4—7. На шаге 5 определяется пересечение стороны многоугольника с прямой.
Теоретически невозможно, чтобы на шаге 5 оказалось, что значение 
равно 0, поскольку это означает параллельность отрезка и прямой, т. е. одинаковость знаков 
, следовательно, возникновение противоречия В табл. 152 дана сводка шагов алгоритма, выполняемых в зависимости от соотношения знаков 
Если обе точки лежат на прямой, алгоритм классифицирует отрезок как невидимый. Фактически, воспроизводимый многоугольник оказывается разомкнутым там, где прямая пересекает его, как показано на рис. 15.3. При решении некоторых прикладных задач такое положение может быть нежелательным, однако описываемый алгоритм нетрудно изменить таким образом, что точки пересечения будут соединяться прямыми (см. задачу 15.4).
Таблица 15.2. (см. скан) Положение многоугольника относительно прямой
Рис. 15 3. Пример многоугольника, разрезанного прямой. Каждая вершина многоугольника помечена знаком величины 
вычисленной для этой вершины
Алгоритм 15.3. Разрезание произвольного прямоугольника произвольной прямой
Обозначения. В качестве исходных данных алгоритму задаются коэффициенты уравнения прямой 
и, кроме того, задаются координаты вершин многоугольника 
. В результате должно быть воспроизведено порезанное изображение многоугольника, который не загораживается прямой 
— коэффициенты прямой, определяемой стороной многоугольника, которые вычисляются на шаге 5 Однородные координаты точки пересечения определяются методом, изложенным в подразд. 14.3.2.
(см. скан)
