В данном разделе рассматривается простой алгоритм отсечения, который подобно алгоритму Сазерленда-Ходгмана может генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Но этот алгоритм несколько более быстрый и использует те же подпрограммы обработки многоугольного окна отсечения, что и алгоритм Кируса-Бека. Многоугольник отсекается одним ребром выпуклого окна отсечения. В результате такого отсечения формируется новый многоугольник, который затем отсекается следующим ребром и т.д., пока не будет выполнено отсечение последним ребром окна. Основная здесь процедура - процедура отсечения отдельным ребром, определяющая взаимное расположение очередной стороны многоугольника и ребра отсекателя и генерирующая соответствующие выходные данные. Возможны 9 различных случаев расположения ребра окна и отсекаемой стороны, показанных на рис. 0.3.26-0.3.28. Рис. 0.3.24: Начальная точка вне ребра окна отсечения На них V0 и V1 - начальная и конечная точки отсекаемой стороны многоугольника, соответственно; Nr - нормаль к ребру окна отсечения, направленная внутрь окна. Рис. 0.3.25: Начальная точка на ребре окна отсечения Из этих рисунков очевидны правила генерации выходных данных, зависящие от варианта взаимного расположения: Нет выходных данных. В выходные данные заносится конечная точка. Рассчитывается пересечение и в выходные данные заносятся точка пересечения и конечная точка. Нет выходных данных. В выходные данные заносится конечная точка. В выходные данные заносится конечная точка. Рассчитывается пересечение и в выходные данные заносится только точка пересечения. В выходные данные заносится конечная точка. В выходные данные заносится конечная точка. Рис. 0.3.26: Начальная точка внутри окна отсечения Для определения взаимного расположения, подобно алгоритму отсечения Кируса-Бека, используется скалярное произведение Q вектора нормали на вектор, проведенный из начала ребра в анализируемую точку. Пояснение см. на рис. 8.10. Рис. 8.10. Анализ расположения точки относительно ребра окна отсечения. Таким образом, для определения взаимного расположения начальной V0 и конечной V1 точек отсекаемой стороны и ребра отсечения с вектором его начала R, надо вычислить: Qn    =   (  V0   -  R  )  ·  Nr       и Qk    =   (  V1   -  R  )  ·  Nr. Расчет пересечения, если он требуется, производится аналогично алгоритму Кируса-Бека с использованием параметрического представления линии: V(t)    =   V0   +  (  V1   -  V0  )  ·  t. Вначале находится значение параметра t для точки пересечения по формуле (см. описание алгоритма Кируса-Бека): t    =   -Qn  /  Pn, где Qn - скалярное произведение вектора нормали к ребру окна на вектор из начала ребра в начальную точку стороны, уже вычисленное при определении расположения начальной точки, Pn    =   (V1 - V0)·  Nr - скалярное произведение вектора нормали к ребру окна на вектор из начальной в конечную точки отсекаемой стороны. Легко выразить это произведение через уже вычисленные величины Qn и Qk: Pn = (V1 - V0)·  Nr = (V1 - V0 - R + R)·  Nr = (V1 - R)·  Nr   -  (V0 - R)·  Nr = Qk - Qn. Таким образом, точке пересечения соответствует значение параметра t, равное: t    =   Qn  /  (  Qn   -  Qk  ). Значения координат пересечения находятся из: Xp    =   X0   +  (X1  -  X0)·  t;      Yp    =   Y0   +  (Y1  -  Y0)·  t. Описанный алгоритм реализован в процедуре V_Plclip, приведенной в Приложении 8.  8  Комментарии к статье  8 8  Обсудить в чате