Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"

Этот раздел активно использует материалы и исходники статьи про отсечение отрезка.

Многоугольники особенно важны в растровой графике как средство задания поверхностей.

Будем называть многоугольник, используемый в качестве окна отсечения, отсекателем, а многоугольник, который отсекается, - отсекаемым.

Алгоритм отсечения многоугольника должен в результате отсечения давать один или несколько замкнутых многоугольников (рис. 0.3.20). При этом могут быть добавлены новые ребра, а имеющиеся или сохранены или разделены или даже отброшены. Существенно, чтобы границы окна, которые не ограничивают видимую часть отсекаемого многоугольника, не входили в состав результата отсечения. Если это не выполняется, то возможна излишняя закраска границ окна (см. рис. 0.3.20б).

В принципе эту задачу можно решить с использованием рассмотренных выше алгоритмов отсечения линий, если рассматривать многоугольник просто как набор векторов, а не как сплошные закрашиваемые области. При этом вектора, составляющие многоугольник, просто последовательно отсекаются сторонами окна (рис. 0.3.21).

Если же в результате отсечения должен быть получен замкнутый многоугольник, то формируется вектор, соединяющий последнюю видимую точку с точкой пересечения с окном (рис. 0.3.22а). Проблема возникает при окружении отсекаемым многоугольником угла окна (см. рис. 0.3.22б).

Здесь мы рассмотрим три алгоритма корректно решающие задачу отсечения сплошного многоугольника. Первые два алгоритма быстро работают, но генерируют лишние ребра, как это продемонстрировано на рис. 0.3.20б. Последний алгоритм свободен от указанного недостатка.

В общем, при отсечении многоугольников возникают два типа задач - отображение части изображения попавшей в окно и наоборот, отображение изображения, находящегося вне окна. Все здесь рассматриваемые алгоритмы могут использоваться в обоих случаях.

Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Хогдмана [40], когда весь многоугольник последовательно отсекается каждой границей окна, как это показано на рис. 0.3.23.

При отсечении ребра, соединяющего очередную пару вершин K и L, возможны 4 случая взаимного расположения (рис. 0.3.24):

а) ребро на внутренней стороне границы,

б) ребро выходит из окна наружу,

в) ребро на внешней стороне границы,

г) ребро входит снаружи в окно.

В случае а) в результат добавляется вершина L. В случае б) в результат заносится S - точка пересечения ребра с границей. В случае в) нет вывода. В случае г) выдаются точка пересечения S и конечная точка ребра L.

Для определения взаимного расположения и направленности используется векторное произведение вектора P₁P₂, проведенного из начальной в конечную точку текущего ребра окна, на вектор P₁S из начальной точки текущего ребра окна в очередную вершину S многоугольника (рис. 0.3.25).

Предложена аппаратная реализация этого алгоритма, состоящая из четырех идентичных ступеней отсечения без промежуточной памяти [28].

В алгоритме Сазерленда-Ходгмана в результат могут заноситься границы окна, даже если они и не ограничивают видимую часть отсеченного многоугольника. Это можно устранить дополнительным анализом, либо используя более сложный алгоритм отсечения.

В данном разделе рассматривается простой алгоритм отсечения, который подобно алгоритму Сазерленда-Ходгмана может генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Но этот алгоритм несколько более быстрый и использует те же подпрограммы обработки многоугольного окна отсечения, что и алгоритм Кируса-Бека.

Многоугольник отсекается одним ребром выпуклого окна отсечения. В результате такого отсечения формируется новый многоугольник, который затем отсекается следующим ребром и т.д., пока не будет выполнено отсечение последним ребром окна.

Основная здесь процедура - процедура отсечения отдельным ребром, определяющая взаимное расположение очередной стороны многоугольника и ребра отсекателя и генерирующая соответствующие выходные данные.

Возможны 9 различных случаев расположения ребра окна и отсекаемой стороны, показанных на рис. 0.3.26-0.3.28.

На них V₀ и V₁ - начальная и конечная точки отсекаемой стороны многоугольника, соответственно; Nr - нормаль к ребру окна отсечения, направленная внутрь окна.

Из этих рисунков очевидны правила генерации выходных данных, зависящие от варианта взаимного расположения:

1) Нет выходных данных.

2) В выходные данные заносится конечная точка.

3) Рассчитывается пересечение и в выходные данные заносятся точка пересечения и конечная точка.

4) Нет выходных данных.

5) В выходные данные заносится конечная точка.

6) В выходные данные заносится конечная точка.

7) Рассчитывается пересечение и в выходные данные заносится только точка пересечения.

8) В выходные данные заносится конечная точка.

9) В выходные данные заносится конечная точка.

Для определения взаимного расположения, подобно алгоритму отсечения Кируса-Бека, используется скалярное произведение Q вектора нормали на вектор, проведенный из начала ребра в анализируемую точку. Пояснение см. на рис. 8.10.

Таким образом, для определения взаимного расположения начальной V₀ и конечной V₁ точек отсекаемой стороны и ребра отсечения с вектором его начала R, надо вычислить:

Расчет пересечения, если он требуется, производится аналогично алгоритму Кируса-Бека с использованием параметрического представления линии:

Вначале находится значение параметра t для точки пересечения по формуле (см. описание алгоритма Кируса-Бека):

где Qn - скалярное произведение вектора нормали к ребру окна на вектор из начала ребра в начальную точку стороны, уже вычисленное при определении расположения начальной точки, а Pn    =   (V₁ - V₀)·  Nr - скалярное произведение вектора нормали к ребру окна на вектор из начальной в конечную точки отсекаемой стороны.

Легко выразить это произведение через уже вычисленные величины Qn и Qk:

Таким образом, точке пересечения соответствует значение параметра t, равное:

Значения координат пересечения находятся из:

Описанный алгоритм реализован в процедуре V_Plclip, приведенной в Приложении 8.

В предыдущих разделах были рассмотрены два алгоритма отсечения многоугольника, последовательно отсекающие произвольный (как выпуклый, так и невыпуклый) многоугольник каждой из сторон выпуклого окна. Зачастую же требуется отсечение по невыпуклому окну. Кроме того оба рассмотренных алгоритма могут генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Далее рассматриваемый алгоритм Вейлера-Азертона [41,,] свободен от указанных недостатков ценой заметно большей сложности и меньшей скорости работы.

Предполагается, что каждый из многоугольников задан списком вершин, причем таким образом, что при движении по списку вершин в порядке их задания внутренняя область многоугольника находится справа от границы.

В случае пересечения границ и отсекаемого многоугольника и окна возникают точки двух типов:

· входные точки, когда ориентированное ребро отсекаемого многоугольника входит в окно,

· выходные точки, когда ребро отсекаемого многоугольника идет с внутренней на внешнюю стороны окна.

Общая схема алгоритма Вейлера-Азертона для определения части отсекаемого многоугольника, попавшей в окно, следующая:

1. Строятся списки вершин отсекаемого многоугольника и окна.

2. Отыскиваются все точки пересечения. При этом расчете касания не считаются пересечением, т.е. когда вершина или ребро отсекаемого многоугольника инцидентна или совпадает со стороной окна (рис. 0.3.29 и 0.3.30).

3. Списки координат вершин отсекаемого многоугольника и окна дополняются новыми вершинами - координатами точек пересечения. Причем если точка пересечения Pk находится на ребре, соединяющем вершины Vi, Vj, то последовательность точек Vi, Vj превращается в последовательность Vi, Pk, Vj. При этом устанавливаются двухсторонние связи между одноименными точками пересечения в списках вершин отсекаемого многоугольника и окна.
   Входные и выходные точки пересечения образуют отдельные подсписки входных и выходных точек в списках вершин.

4. Определение части обрабатываемого многоугольника, попавшей в окно выполняется следующим образом:
   Если не исчерпан список входных точек пересечения, то выбираем очередную входную точку.
   Двигаемся по вершинам отсекаемого многоугольника пока не обнаружится следующая точка пересечения; все пройденные точки, не включая прервавшую просмотр, заносим в результат; используя двухстороннюю связь точек пересечения, переключаемся на просмотр списка вершин окна.
   Двигаемся по вершинам окна до обнаружения следующей точки пересечения; все пройденные точки, не включая последнюю, прервавшую просмотр, заносим в результат.
   Используя двухстороннюю связь точек пересечения, переключаемся на список вершин обрабатываемого многоугольника.
   Эти действия повторяем пока не будет достигнута исходная вершина - очередная часть отсекаемого многоугольника, попавшая в окно, замкнулась. Переходим на выбор следующей входной точки в списке отсекаемого многоугольника.

Модификация этого алгоритма для определения части отсекаемого многоугольника, находящейся вне окна, заключается в следующем:

· исходная точка пересечения пересечения берется из списка выходных точек,

· движение по списку вершин окна выполняется в обратном порядке, т.е. так чтобы внутренняя часть отсекателя была слева.

На рис. 0.3.31 иллюстрируется отсечение многоугольника ABCDEFGHI окном PQRS по алгоритму Вейлера-Азертона.

Начиная с этого алгоритма, при рассмотрении многих дальнейших требуется представления о различных структурах данных и работе с ними. Следующий раздел и посвящен беглому рассмотрению некоторых наиболее важных структур данных.

В данном приложении содержатся процедуры V_Plclip, реализующие простой алгоритм отсечения произвольного многоугольника по выпуклому многоугольному окну отсечения и тестовая программа проверки их работы.

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

/*=================================================== V_PLCLIP
 * Файл V_PLCLIP.C - процедуры простого алгоритма отсечния
 *                   многоугольника
 * Последняя редакция:
 * 25.12.93  17:25
 */

#include <graphics.h>
#include "V_WINDOW.C"   /* Глобалы и проц работы с окнами */

/* Включаемый файл V_WINDOW.C содержит
 * подрограммы и глобалы для окон:
 *
 * V_SetPclip - установить размеры многоугольного окна
 *              отсечения
 * V_GetPclip - опросить параметры многоугольного окна
 *              отсечения
 * V_SetRclip - установить размеры прямоугольного окна
 *              отсечения
 * V_GetRclip - опросить   размеры прямоугольного окна
 *              отсечения
 *
 * Глобальные скаляры для алгоритмов отсечения по
 * прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм,
 * Лианга-Барски
 *
 * static float Wxlef= 100.0, -- Координаты левого нижнего и
 *              Wybot= 100.0, -- правого верхнего углов окна
 *              Wxrig= 300.0, -- отсечения
 *              Wytop= 200.0;
 *
 * Глобальные скаляры для алгоритма Кируса-Бека
 * отсечения по многоугольному окну
 *
 * Координаты прямоугольного окна
 * static float Wxrect[4]= {100.0, 100.0, 300.0, 300.0 };
 * static float Wyrect[4]= {100.0, 200.0, 200.0, 100.0 };
 *
 * Перепендикуляры к сторонам прямоугольного окна
 * static float WxNrec[4]= {1.0,  0.0, -1.0, 0.0 };
 * static float WyNrec[4]= {0.0, -1.0,  0.0, 1.0 };
 *
 * Данные для многоугольного окна
 * static int   Windn=4;          -- Кол-во вершин у окна
 * static float *Windx=  Wxrect,  -- Координаты вершин окна
 *              *Windy=  Wyrect;
 * static float *Wnormx= WxNrec,  -- Координаты нормалей
 *              *Wnormy= WyNrec;
 */

/*-------------------------------------------------- Pl_clip0
 * Служебная процедура, отсекает многоугольник
 * относительно одного ребра окна
 *
 * Отсечение выполняется в цикле по сторонам многоугольника
 * При первом входе в цикл только вычисляются величины для
 * начальной точки: координаты, скалярное произведение,
 * определяющее ее расположение относительно ребра окна, и
 * код расположения.
 * При последующих входах в цикл эти значения вычисляются
 * для очередной вершины.
 * По значениям кодов расположения вершин для стороны
 * многоугольника определяется как она расположена
 * относительно ребра и вычисляются координаты результирующего
 * многоугольника.
 */

static int Pl_clip0 (N_reb, N_in, X_in, Y_in, X_ou, Y_ou)
int   N_reb, N_in;
float *X_in, *Y_in, *X_ou, *Y_ou;
{
   int  ii, jj;
   int  pozb,      /* Коды расположения начальной точки  */
        pozn,      /* многоугольника и точек тек стороны */
        pozk;      /* 0/1/2 - пред точка вне/на/внутри   */
   float Rx,Ry;    /* Координаты начала ребра окна */
   float Nx, Ny;   /* Нормаль к  ребру окна */
   float xb, yb;   /* Начальная точка многоугольника  */
   float xn, yn;   /* Начальная точка текущей стороны */
   float xk, yk;   /* Конечная  точка текущей стороны */
   float t;        /* Значение параметра точки пересечения */
   float Qb,Qn,Qk; /* Скалярные произведения */
   float *ptx_ou;

/* Запрос параметров ребра окна */
   Rx= Windx[N_reb];  Ry= Windy[N_reb];
   Nx= Wnormx[N_reb]; Ny= Wnormy[N_reb];

/* Цикл отсчения многоугольника ребром окна */
   ii= 0;  ++N_in;  ptx_ou= X_ou;
   while (--N_in >= 0) {
      if (N_in) {
         xk= *X_in++;  yk= *Y_in++;   /* Кон точка стороны  */
         Qk= (xk-Rx)*Nx + (yk-Ry)*Ny; /* Параметр положения */
         pozk= 1;                     /* 1 - точка на гр. */
         if (Qk < 0) --pozk; else     /* 0 - точка вне    */
         if (Qk > 0) ++pozk;          /* 2 - точка внутри */
      } else {
         xk= xb;  yk= yb;  Qk= Qb;  pozk= pozb;
      }
      if (!ii) {
         xb= xn= xk; yb= yn= yk; Qb= Qn= Qk; pozb= pozn= pozk;
         ++ii; continue;
      }
      jj= 0;
      switch (pozn*3 + pozk) {     /* Стар Нов Выход     */
         case 0: goto no_point;    /*  вне-вне нет       */
         case 1: goto endpoint;    /*  вне-на  конечная  */
         case 2: goto intersec;    /*  вне-вну перес,кон */
         case 3: goto no_point;    /*  на -вне нет       */
         case 4:                   /*  на -на  конечная  */
         case 5: goto endpoint;    /*  на -вну конечная  */
         case 6: goto no_end;      /*  вну-вне пересечен */
         case 7:                   /*  вну-на  конечная  */
         case 8: goto endpoint;    /*  вну-вну конечная  */
      }
no_end: ++jj;
intersec:
      t= Qn/(Qn-Qk);
      *X_ou++= xn + t*(xk-xn);
      *Y_ou++= yn + t*(yk-yn);
      if (!jj) {
endpoint:
         *X_ou++= xk;  *Y_ou++= yk;
      }
no_point:
      xn= xk;  yn= yk;  Qn= Qk;  pozn= pozk;
   }
   return (X_ou - ptx_ou);
}  /* Pl_clip0 */

/*--------------------------------------------------- V_Plclip
 * Простая процедура отсечения многоугольника
 * N_in       - число вершин во входном многоугольнике
 * X_in, Y_in - координаты вершин отсекаемого мног-ка
 *              этот массив будет испорчен
 * Возвращает:
 *  < 0 - ошибки
 * >= 0 - количество вершин в выходном многоугольнике
 * X_ou, Y_ou - координаты вершин отсеченного многоугольника
 */

int  V_Plclip (N_in, X_in, Y_in, X_ou, Y_ou)
int   N_in;
float *X_in, *Y_in, *X_ou, *Y_ou;
{
   int  ii, N_ou; float *ptr;

   if ((N_ou= N_in) < 3) {N_ou= -1;  goto all; }
   if (Windn < 3) {N_ou= -2;  goto all; }
   for (ii=0; ii<Windn; ++ii) {
      N_ou= Pl_clip0 (ii, N_ou, X_in, Y_in, X_ou, Y_ou);
      ptr= X_in;  X_in= X_ou;  X_ou= ptr;
      ptr= Y_in;  Y_in= Y_ou;  Y_ou= ptr;
   }
   if (!(Windn & 1)) {
      ii= N_ou;
      while (--ii >= 0) {*X_ou++= *X_in++; *Y_ou++= *Y_in++; }
   }
all:
   return N_ou;
}  /* V_Plclip */

/*=================================================== T_PLCLIP
 * ТЕСТ процедуры V_Plclip для отсечения многоугольника
 *
 * При первом входе устанавливается восьмиугольное окно
 * отсечения:
 * X: 150, 100, 100, 150, 250, 300, 300, 250
 * Y: 100, 150, 250, 300, 300, 250, 150, 100
 *
 * И на нем отсекается треугольник:
 * (10,160),(90,220),(170,160)
 *
 * Затем выдается запрос на количество вершин в
 * новом отсекаемом многоугольнике:
 * --- Vertexs in polyline= XX ?
 * При вводе числа > 0 будут запрашиваться координаты вершин
 *                     много-ка и выполняться его отсечение
 * При вводе числа = 0 программа затребует ввод координат
 *                     нового прямоугольного окна отсечения
 * При вводе числа < 0 программа запросит переустановку
 *                     многоугольного окна отсечения:
 *
 * ----Vertexs in clip window= XX ?
 * При вводе числа > 0 будут запрашиваться координаты вершин.
 * При вводе числа = 0 программа затребует ввод координат
 *                     прямоугольного окна.
 * При вводе числа < 0 программа закончится.
 */

#include <graphics.h>
#include "V_PLCLIP.C"

/*--------------------------------------------------- DrawPoly
 * Чертит контур многоугольника
 */
void DrawPoly (col, n, x, y)
int col, n; float *x, *y;
{  int  ii, jj;
   setcolor (col);
   for (ii=0; ii<n; ++ii) {
      if ((jj= ii+1) >= n) jj= 0;
      line (x[ii], y[ii], x[jj], y[jj]);
   }
}  /* DrawPoly */

/*---------------------------------------------------- CLR_STR
 * Зачищает строку выводом в нее пробелов
 */
void CLR_STR (void)
{
printf ("                                                \r");
}

/*------------------------------------------------ PLCLIP_MAIN
 */
void main (void)
{  int   ii, jj,
         fon;           /* Индекс фона  */
   float Wxn,Wyn,       /* Прямоугольный отсекатель */
         Wxk,Wyk;
   int   N_wind= 0;     /* Вводимый отсекатель */
   float X_wind[100],
         Y_wind[100];
   float X_norm[100],
         Y_norm[100];
   int   wnum;          /* Запрошенный отсекатель */
   float *wx,*wy,*wnx,*wny;
   int   N_poly= 0;     /* Отсекаемый многугольник */
   float X_poly[100],
         Y_poly[100];
   int   N_clip= 0;     /* Отсеченный многугольник */
   float X_clip[100],
         Y_clip[100];
   int   entry= 0;      /* 0/1 - нет/был вывод по умолчанию */
   int   gdriver= DETECT, gmode;

   initgraph (&gdriver, &gmode, "");
   fon= 0;                      /* Цвет фона */

   setbkcolor(fon);             /* Очистка экрана */
   cleardevice();

/*--------------- Установить окно отсечения ----------------*/
new_window:
   gotoxy (1,1);
   if (!entry) {
      N_wind= 8;  wx= X_wind;  wy= Y_wind;
      *wx++= 150; *wx++= 100;  *wx++= 100; *wx++= 150;
      *wy++= 100; *wy++= 150;  *wy++= 250; *wy++= 300;

      *wx++= 250; *wx++= 300;  *wx++= 300; *wx++= 250;
      *wy++= 300; *wy++= 250;  *wy++= 150; *wy++= 100;
      goto wr_window;
   }
   if (!N_poly) goto set_rect;

/*---------- Задание многоугольного окна отсечения ---------*/
set_window:
   CLR_STR ();
   printf ("----Vertexs in clip window= %d ? ", N_wind);
   scanf  ("%d", &N_wind);
   if (N_wind < 0) goto all;
   if (!N_wind) goto set_rect;
   for (ii=0; ii<N_wind; ++ii) {
      CLR_STR ();
      printf ("X_wind[%d], Y_wind[%d] ? ", ii, ii);
      scanf  ("%f%f", &X_wind[ii], &Y_wind[ii]);
   }
wr_window:
   jj= V_SetPclip (N_wind, X_wind, Y_wind, X_norm, Y_norm);
   if (jj) {
      printf ("Error=%d in polyline window\n", jj);
      goto set_window;
   } else goto ou_win;

/*---------- Задание прямоугольного окна отсечения ---------*/
set_rect:
   V_GetRclip (&Wxn, &Wyn, &Wxk, &Wyk);
get_rect:
   CLR_STR ();
   printf ("Rect window: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
            Wxn, Wyn, Wxk, Wyk);
   scanf  ("%f%f%f%f", &Wxn, &Wyn, &Wxk, &Wyk);
wr_rect:
   jj= V_SetRclip (Wxn, Wyn, Wxk, Wyk);
   if (jj) {
      printf ("Error=%d in rectangle window\n", jj);
      goto get_rect;
   }

/*--------------- Прорисовка окна отсечения ----------------*/
ou_win:
   wnum= V_GetPclip (&wx, &wy, &wnx, &wny);
   DrawPoly (LIGHTRED, wnum, wx, wy);

/*------- Ввод координат отсекаемого многоугольника --------*/

set_poly:
   gotoxy (1,1);
   if (!entry) { /* При первом входе отрисовка по умолчанию */
      N_poly= 3;
      X_poly[0]=  10;  X_poly[1]=  90;  X_poly[2]= 170;
      Y_poly[0]= 160;  Y_poly[1]= 220;  Y_poly[2]= 160;
   } else {
      CLR_STR ();
      printf ("--- Vertexs in polyline= %d ? ",N_poly);
      scanf  ("%d", &N_poly);
      if (N_poly <= 0) goto new_window;
      for (ii=0; ii<N_poly; ++ii) {
         printf ("                                   \r");
         printf ("X_poly[%d], Y_poly[%d] ? ", ii, ii);
         scanf  ("%f%f", &X_poly[ii], &Y_poly[ii]);
      }
   }
   ++entry;

/*---------- Прорисовка отсекателя и отсекаемого -----------*/
   wnum= V_GetPclip (&wx, &wy, &wnx, &wny);
   DrawPoly (LIGHTRED, wnum, wx, wy);
   DrawPoly (LIGHTGREEN, N_poly, X_poly, Y_poly);


/*----------------------- Отсечение ------------------------*/
   N_clip= V_Plclip(N_poly, X_poly, Y_poly, X_clip, Y_clip);

/*----------------- Прорисовка отсеченного -----------------*/
   DrawPoly (YELLOW, N_clip, X_clip, Y_clip);
   goto set_poly;

all:
   closegraph();
}  /* PLCLIP_MAIN */

[28]

Clark, J.H. A VLSI geometry Processor for Graphics// IEEE Computer, 12(7).

[40]

Sutherland I.E., Hodgman G.W. Reentrant Polygon Clipping//Communications of the ACM, 17(1), pp. 32-42.

[41]

Weiler K., Atherton P,. Hidden Surface Removal Using Polygon Area Sorting// SIGGGRAPH'77 Proceedings, Computer Graphics, Vol. 11, N. 2, pp. 214-222, 1977.