Можно разработать алгоритм отсечения многоугольников, взяв за основу алгоритм отсечения отрезков и применив его последовательно ко всем ребрам многоугольника. Но при этом нужно не забывать, что многоугольник представляет собой единый объект и что при его отсечении может быть сформировано несколько новых объектов-многоугольников.
Рассмотрим представленный на рис. 7.10, а многоугольник общего вида-"вогнутый" (concave) многоугольник. Если применить к нему отсечение прямоугольной рамкой, то получим три новых многоугольника (рис. 7.10,6). Но, к сожалению, реализовать модуль отсечения, который был бы способен из одного объекта сформировать несколько, довольно сложно. Поэтому чаще всего результат отсечения, подобный показанному на рис. 7.10,6, представляется в программе как единый многоугольник, для чего в модуле отсечения выполняется объединение фрагментов в единый объект (рис. 7.11). В таком многоугольнике некоторые ребра накладываются друг на друга, что иногда служит источником проблем при решении других задач.
При отсечении одного выпуклого (convex) многоугольника другим выпуклым многоугольником, в частности прямоугольной рамкой зоны видимости, принципиально не может образоваться больше одного многоугольника, причем тоже выпуклого (см. упр. 7.3). Таким образом, в этом случае проблема "размножения" не возникает, и в большинстве графических систем либо разрешается формировать только выпуклые многоугольники, либо имеются средства рассечения (tessellation) многоугольника общего вида на выпуклые (рис. 7.12)3.
Для отсечения многоугольников прямоугольной рамкой можно использовать оба описанных выше алгоритма отсечения отрезков, применяя их в цикле по отношению к ребрам анализируемого многоугольника. В системах с конвейерной архитектурой более эффективным является другой подход, предложенный Сазерлендом (Sutherland) и Ходжменом (Hodgeman).
В графической системе OpenGL функция рассечения многоугольников входит в состав библиотеки GLU.
298 Глава 7. Алгоритмы формирования изображения