Этот раздел активно использует материалы и исходники раздела про отсечение отрезка. Многоугольники особенно важны в растровой графике как средство задания поверхностей. Будем называть многоугольник, используемый в качестве окна отсечения, отсекателем, а многоугольник, который отсекается, - отсекаемым. Алгоритм отсечения многоугольника должен в результате отсечения давать один или несколько замкнутых многоугольников (рис. 0.3.20). При этом могут быть добавлены новые ребра, а имеющиеся или сохранены или разделены или даже отброшены. Существенно, чтобы границы окна, которые не ограничивают видимую часть отсекаемого многоугольника, не входили в состав результата отсечения. Если это не выполняется, то возможна излишняя закраска границ окна (см. рис. 0.3.20б). Рис. 0.3.18: Отсечение окном PQRS многоугольников ABCDEFGHIJ и KLMN В принципе эту задачу можно решить с использованием рассмотренных выше алгоритмов отсечения линий, если рассматривать многоугольник просто как набор векторов, а не как сплошные закрашиваемые области. При этом вектора, составляющие многоугольник, просто последовательно отсекаются сторонами окна (рис. 0.3.21). Рис. 0.3.19: Отсечение окном PQRS многоугольника ABCD, рассматриваемого как набор векторов. Генерируется вывод из двух векторов BsCs и DsAs Если же в результате отсечения должен быть получен замкнутый многоугольник, то формируется вектор, соединяющий последнюю видимую точку с точкой пересечения с окном (рис. 0.3.22а). Проблема возникает при окружении отсекаемым многоугольником угла окна (см. рис. 0.3.22б). Рис. 0.3.20: Отсечение сплошного многоугольника окном Здесь мы рассмотрим три алгоритма корректно решающие задачу отсечения сплошного многоугольника. Первые два алгоритма быстро работают, но генерируют лишние ребра, как это продемонстрировано на рис. 0.3.20б. Последний алгоритм свободен от указанного недостатка. В общем, при отсечении многоугольников возникают два типа задач - отображение части изображения попавшей в окно и наоборот, отображение изображения, находящегося вне окна. Все здесь рассматриваемые алгоритмы могут использоваться в обоих случаях. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  Алгоритм Сазерленда-Ходгмана Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Хогдмана, когда весь многоугольник последовательно отсекается каждой границей окна 8  Простой алгоритм отсечения многоугольника В данном разделе рассматривается простой алгоритм отсечения, который подобно алгоритму Сазерленда-Ходгмана может генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Но этот алгоритм несколько более быстрый и использует те же подпрограммы обработки многоугольного окна отсечения, что и алгоритм Кируса-Бека. 8  Алгоритм отсечения многоугольника Вейлера-Азертона В предыдущих разделах были рассмотрены два алгоритма отсечения многоугольника, последовательно отсекающие произвольный (как выпуклый, так и невыпуклый) многоугольник каждой из сторон выпуклого окна. Зачастую же требуется отсечение по невыпуклому окну. Кроме того оба рассмотренных алгоритма могут генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Далее рассматриваемый алгоритм Вейлера-Азертона свободен от указанных недостатков ценой заметно большей сложности и меньшей скорости работы. 8  Приложение 8. Процедуры отсечения многоугольника В данном приложении содержатся процедуры V_Plclip, реализующие простой алгоритм отсечения произвольного многоугольника по выпуклому многоугольному окну отсечения и тестовая программа проверки их работы. 8  Список литературы

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