Nickolay.info. Алгоритмы. Алгоритмы Сазерленда-Ходжмена - отсечение многоугольника окном, объединение многоугольников

Первая программа реализует обработку отсечения прямоугольным окном, широко применяемую в самых разных графических построениях. Ниже приводятся полный листинг программы и скриншот. Так как писалось это во времена DOS-графики, сегодня можно запустить разве что из-под DOSBox или другого эмулятора (в конце этой главы даны ссылки на эмуляторы).

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <math.h>
#include <graphics.h>

#define X_BAR 200
#define Y_BAR 150
#define SIDES 15
#define MAXPOINT 100
#define BKCOLOR WHITE

typedef struct {
 float x,y;
} Point;

Point P[MAXPOINT], //Исходный многоугольник
      Q[MAXPOINT], //Копия исходного многоугольника для отрисовки
      W[5],        //Окно
      C[MAXPOINT]; //Рабочий многоугольник для отсечения
int Np,Nq,Nw,x1,y1,x2,y2,nx;

int Round (float x) { return ((x-floor(x)<0.5) ? floor(x) : ceil(x)); }

int Enter (void) { //Вернет 1,если нажата Enter, 0 - если нажата Esc
 int c;
 while (1) {
  fflush (stdin);
  c=getch();
  if (c==13) return 1;
  else if (c==27) return 0;
 }
}

void Message (unsigned char *s) {
 setfillstyle (SOLID_FILL,BKCOLOR);
 bar (x1,y2+2,x2,getmaxy()-2);
 setcolor (BLACK);
 outtextxy (x1,y2+2,s);
}

void Redraw (void) {
 int i;
 setfillstyle (SOLID_FILL,WHITE);
 bar (x1+1,y1+1,x2-1,y2-1);
 setlinestyle (DOTTED_LINE,0,1);
 for (i=0; i<Nq-1; i++) line (Round(Q[i].x),Round(Q[i].y),Round(Q[i+1].x),Round(Q[i+1].y));
 line (Round(Q[0].x),Round(Q[0].y),Round(Q[Nq-1].x),Round(Q[Nq-1].y));
 setlinestyle (SOLID_LINE,0,1);
 setcolor (GREEN);
 rectangle (W[0].x,W[0].y,W[2].x,W[2].y);
 setcolor (BLUE);
 for (i=0; i<Np-1; i++) line (Round(P[i].x),Round(P[i].y),Round(P[i+1].x),Round(P[i+1].y));
 line (Round(P[0].x),Round(P[0].y),Round(P[Np-1].x),Round(P[Np-1].y));
 Message ("Cutting by next side of window"); //Выполнено отсечение стороной окна
 Enter();
}

char InitVga (void) { //Инициализация графического режима 640*480 точек
 int gdriver = VGA, gmode=2;
 initgraph(&gdriver, &gmode, "");
 if (graphresult()!=grOk) return 0;
 return 1;
}

#define LEFT    0x01
#define RIGHT   0x02
#define TOP     0x08
#define BOTTOM  0x04

void Line (Point P1,Point P2, float *a,float *b) {
 *a=(P1.y-P2.y)/(P1.x-P2.x);
 *b=P1.y-*a*P1.x;
}

int Between (float x1, float x, float x2) {
 if ((Round(x)>=Round(x1)) && (Round(x)<=Round(x2)) ||
     (Round(x)<=Round(x1)) && (Round(x)>=Round(x2))) return 1;
 return 0;
}

void Re (void) {
 int i;
 Np=nx;
 for (i=0; i<nx; i++) {P[i]=C[i]; }
 P[Np].x=P[0].x; P[Np].y=P[0].y; Np++;
 Redraw ();
}

void Hodgmen2 (void) {
 int i,j;
 float a,b,X[MAXPOINT];
 nx=0;
 for (j=0; j<Np-1; j++) { //верхняя
  if (Between (P[j].y,W[0].y,P[j+1].y)) {
   if (P[j].y>W[0].y) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
   C[nx].y=W[0].y;
   if (Round(P[j].x)==Round(P[j+1].x)) C[nx++].x=P[j].x;
   else {
    Line (P[j],P[j+1],&a,&b);
    C[nx++].x=(W[0].y-b)/a;
   }
  }
  else if ((P[j].y<W[0].y) && (P[j+1].y<W[0].y)) continue;
  else {
   C[nx].y=P[j].y; C[nx++].x=P[j].x;
  }
 }
 Re ();
 nx=0;
 for (j=0; j<Np-1; j++) { //правая
  if (Between (P[j].x,W[1].x,P[j+1].x)) {
   if (P[j].x<W[1].x) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
   C[nx].x=W[1].x;
   if (Round(P[j].y)==Round(P[j+1].y)) C[nx++].y=P[j].y;
   else {
    Line (P[j],P[j+1],&a,&b);
    C[nx++].y=a*W[1].x+b;
   }
  }
  else if ((P[j].x>W[1].x) && (P[j+1].x>W[1].x)) continue;
  else {
   C[nx].y=P[j].y; C[nx++].x=P[j].x;
  }
 }
 Re ();
 nx=0;
 for (j=0; j<Np-1; j++) { //нижняя
  if (Between (P[j].y,W[2].y,P[j+1].y)) {
   if (P[j].y<W[2].y) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
   C[nx].y=W[2].y;
   if (Round(P[j].x)==Round(P[j+1].x)) C[nx++].x=P[j].x;
   else {
    Line (P[j],P[j+1],&a,&b);
    C[nx++].x=(W[2].y-b)/a;
   }
  }
  else if ((P[j].y>W[2].y) && (P[j+1].y>W[2].y)) continue;
  else {
   C[nx].y=P[j].y; C[nx++].x=P[j].x;
  }
 }
 Re ();
 nx=0;
 for (j=0; j<Np-1; j++) { //левая
  if (Between (P[j].x,W[3].x,P[j+1].x)) {
   if (P[j].x>W[3].x) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
   C[nx].x=W[3].x;
   if (Round(P[j].y)==Round(P[j+1].y)) C[nx++].y=P[j].y;
   else {
    Line (P[j],P[j+1],&a,&b);
    C[nx++].y=a*W[3].x+b;
   }
  }
  else if ((P[j].x<W[3].x) && (P[j+1].x<W[3].x)) continue;
  else {
   C[nx].y=P[j].y; C[nx++].x=P[j].x;
  }
 }
 Re ();
}

int main (void) {
 int i,dx,dy;
 unsigned char *s="                                                "
		  "                                                ";
 if (!InitVga()) {
  clrscr();
  printf ("\n Can't open VGA graphics mode!");
            //Не могу инициализировать графику VGA
  return 1;
 }
do {
 x1=10; x2=getmaxx()-10;
 y1=4+textheight("W"); y2=getmaxy()-4-textheight("W");

 setfillstyle (SOLID_FILL,WHITE);
 bar (0,0,getmaxx(),getmaxy());
 setcolor (RED);
 rectangle (x1,y1,x2,y2);
 outtextxy (x1,2,"Cutting! Press ENTER to continue");
                //Отсечение многоугольника прямоугольным окном (ENTER - продолжить)
 W[0].x=(getmaxx()-X_BAR)/2; W[0].y=(getmaxy()-Y_BAR)/2;
 W[1].x=(getmaxx()+X_BAR)/2; W[1].y=(getmaxy()-Y_BAR)/2;
 W[2].x=(getmaxx()+X_BAR)/2; W[2].y=(getmaxy()+Y_BAR)/2;
 W[3].x=(getmaxx()-X_BAR)/2; W[3].y=(getmaxy()+Y_BAR)/2;
 W[4].x=W[0].x; W[4].y=W[0].y;
 Nw=5;

 randomize();
 Np=8+random(SIDES-7); //Число вершин многоугольника
 P[0].x=x1+random (W[0].x-x1); //Первая точка - левее и выше окна
 dx=2*(x2-P[0].x)/Np; //Шаг по x для остальных точек
 for (i=1; i<=Np/2; i++) P[i].x=P[i-1].x+dx; //Идем вперед по оси x
 for (i=Np/2+1; i<Np; i++) P[i].x=P[i-1].x-dx; //Возвращаемся назад
 P[0].y=y1+random (W[0].y-y1);
 dy=(W[0].y+W[2].y)/2;
 for (i=1; i<=Np/2; i++) P[i].y=y1+random(dy-y1);
 for (i=Np/2+1; i<Np; i++) P[i].y=y2-random (y2-dy);
 P[Np].x=P[0].x;  P[Np].y=P[0].y; Np++;
 Nq=Np;
 for (i=0; i<Nq; i++) { Q[i].x=P[i].x; Q[i].y=P[i].y; }

 setcolor (BLUE);
 for (i=0; i<Np-1; i++) line (P[i].x,P[i].y,P[i+1].x,P[i+1].y);
 line (P[0].x,P[0].y,P[Np-1].x,P[Np-1].y);
 setcolor (GREEN);
 rectangle (W[0].x,W[0].y,W[2].x,W[2].y);
 sprintf (s,"Window coordinates: from (%5.0f,%5.0f) to (%5.0f,%5.0f)",W[0].x,W[0].y,W[2].x,W[2].y);
            //Координанты окна: от (%5.0f,%5.0f) до (%5.0f,%5.0f)
 Message (s);
 Enter();

 Hodgmen2();
} while (Enter());
closegraph();
return 0;
}

Многоугольники генерируются повторно, достаточно нажимать ENTER.

 Скриншот (новое окно)

 Архив ZIP с файлами .CPP и .EXE (43 Кб)

Вторая распространенная задача обработки графики - объединение двух многоугольников. Данные для этой программы должны храниться в текущей папке в файле с именем bars.dat, например, таком:

5
50 250
250 50
490 230
460 280
250 410
7
100 100
400 100
420 120
400 400
100 400
80 350
75 300

Формат файла описан в листинге. Требования к программе = те же, что и к первой (DOS-графика).

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <math.h>
#include <values.h>
#include <graphics.h>

#define SIDES 100
#define BKCOLOR WHITE

typedef struct {
 float x,y;
} Point;

int x1,x2,y1,y2,n1,n2,n,nc;
Point P[SIDES],W[SIDES],S[SIDES],C[SIDES];

void Read (FILE *f) {
 int i;
 fscanf (f,"%d",&n1);
 for (i=0; i<n1; i++) {
  fscanf (f,"%f",&P[i].x);
  fscanf (f,"%f",&P[i].y);
 }
 fscanf (f,"%d",&n2);
 for (i=0; i<n2; i++) {
  fscanf (f,"%f",&W[i].x);
  fscanf (f,"%f",&W[i].y);
 }
}

char InitVga (void) { //Инициализация графического режима 640*480 точек
 int gdriver = VGA, gmode=2;
 initgraph(&gdriver, &gmode, "");
 if (graphresult()!=grOk) return 0;
 return 1;
}

int Enter (void) { //Вернет 1,если нажата Enter, 0 - если нажата Esc
 int c;
 while (1) {
  fflush (stdin);
  c=getch();
  if (c==13) return 1;
  else if (c==27) return 0;
 }
}

void Message (unsigned char *s) {
 setfillstyle (SOLID_FILL,BKCOLOR);
 bar (x1,y2+2,x2,getmaxy()-2);
 setcolor (BLACK);
 outtextxy (x1,y2+2,s);
}

int Round (float x) { return ((x-floor(x)<0.5) ? floor(x) : ceil(x)); }

int Between (float x1, float x, float x2) {
 if ((Round(x)>=Round(x1)) && (Round(x)<=Round(x2)) ||
     (Round(x)<=Round(x1)) && (Round(x)>=Round(x2))) return 1;
 return 0;
}

int Cross (Point P1, Point P2, Point W1, Point W2) {
 //Факт пересечения прямых, проходящих через точки (P1,P2) и (W1,W2)
 float r1,r2;
 if (P1.x==P2.x) {
  if (Between (W1.x,P1.x,W2.x)) return 1;
  return 0;
 }
 if (P1.y==P2.y) {
  if (Between (W1.y,P1.y,W2.y)) return 1;
  return 0;
 }
 r1=(W1.x-P1.x)/(P2.x-P1.x)-(W1.y-P1.y)/(P2.y-P1.y);
 r2=(W2.x-P1.x)/(P2.x-P1.x)-(W2.y-P1.y)/(P2.y-P1.y);
 if ((r1<0) && (r2>0) || (r1>0) && (r2<0)) return 1;
 else return 0;
}

Point T;

int CrossPoint (Point P1, Point P2, Point W1, Point W2) {
 //Координаты точки пересечения отрезков (P1,P2) и (W1,W2)
 //записываются во внешнюю точку T. Возвращает 1, если отрезки пересекаются
 float a1,b1,a2,b2;
 if (P1.x==P2.x) {
  a2=(W1.y-W2.y)/(W1.x-W2.x);
  b2=W1.y-a2*W1.x;
  T.x=P1.x;
  T.y=a2*P1.x+b2;
  if (Between (W1.x,T.x,W2.x) && Between (W1.y,T.y,W2.y)) return 1;
  return 0;
 }
 if (W1.x==W2.x) {
  a1=(P1.y-P2.y)/(P1.x-P2.x);
  b1=P1.y-a1*P1.x;
  T.x=W1.x;
  T.y=a1*W1.x+b1;
  if (Between (P1.x,T.x,P2.x) && Between (P1.y,T.y,P2.y)) return 1;
  return 0;
 }
 a1=(P1.y-P2.y)/(P1.x-P2.x);
 b1=P1.y-a1*P1.x;
 a2=(W1.y-W2.y)/(W1.x-W2.x);
 b2=W1.y-a2*W1.x;
 T.x=(b2-b1)/(a1-a2);
 T.y=a1*T.x+b1;
 if (Between (P1.x,T.x,P2.x) && Between (P1.y,T.y,P2.y) &&
     Between (W1.x,T.x,W2.x) && Between (W1.y,T.y,W2.y)) return 1;
 return 0;
}

void Draw(void) {
 int i;
 setcolor (BLUE);
 for (i=0; i<n1-1; i++) line (Round(P[i].x),Round(P[i].y),Round(P[i+1].x),Round(P[i+1].y));
 line (Round(P[0].x),Round(P[0].y),Round(P[n1-1].x),Round(P[n1-1].y));
 setcolor (RED);
 for (i=0; i<n2-1; i++) line (Round(W[i].x),Round(W[i].y),Round(W[i+1].x),Round(W[i+1].y));
 line (Round(W[0].x),Round(W[0].y),Round(W[n2-1].x),Round(W[n2-1].y));
}

float Rast (Point P,Point W) {
 return (sqrt((P.x-W.x)*(P.x-W.x)+(P.y-W.y)*(P.y-W.y)));
}

int Check (void) {
 int i,j;
 for (i=0; i<n-1; i++) {
  for (j=i+1; j<n; j++) {
   if (Round(S[i].x)==Round(S[j].x) && Round(S[i].y)==Round(S[j].y)) {
    n--; return 1;
   }
  }
 }
 return 0;
}

void Objed(void) {
 //Объединение P из n1 вершин и W из n2 вершин в многоугольник S из n вершин
 int i=0,j=0,Nj[SIDES],nmin,k,kmin;
 Point P1,P2,W1,W2;
 float r,rmin;
 i=0;
 n=0;
NEXT_I:
 S[n].x=P[i].x; S[n].y=P[i].y; n++;
 if (Check()) return;
 nc=0;
 if (i==n1-1) { P2.x=P[0].x; P2.y=P[0].y; }
 else { P2.x=P[i+1].x; P2.y=P[i+1].y; }
 P1.x=P[i].x; P1.y=P[i].y;
 for (j=0; j<n2; j++) {
  if (j==n2-1) { W2.x=W[0].x; W2.y=W[0].y; }
  else { W2.x=W[j+1].x; W2.y=W[j+1].y; }
  W1.x=W[j].x; W1.y=W[j].y;
  if (Cross(P1,P2,W1,W2)) {
   if (CrossPoint(P1,P2,W1,W2)) {
    C[nc].x=T.x; C[nc].y=T.y;
    Nj[nc]=(j==n2-1 ? 0 : j+1);
    nc++;
   }
  }
 }
 if (nc>0) {
  //В массиве C - все координаты точек пересечения ребрами W данного ребра P
  //а в Nj - номера вершин W, для которых есть эти пересечения
  rmin=MAXFLOAT;
  for (k=0; k<nc; k++) { //Ищем ближайшее к началу ребра пересечение
   r=Rast (P1,C[k]);
   if (r<rmin) {
    kmin=k; nmin=Nj[k]; rmin=r;
   }
  }
  S[n].x=C[kmin].x; S[n].y=C[kmin].y; n++;
  if (Check()) return;
  j=nmin;
  //Перейти на многоугольник W и идти дальше по контуру
NEXT_J:
  S[n].x=W[j].x; S[n].y=W[j].y; n++;
  if (Check()) return;
  nc=0;
  if (j==n2-1) { W2.x=W[0].x; W2.y=W[0].y; }
  else { W2.x=W[j+1].x; W2.y=W[j+1].y; }
  W1.x=W[j].x; W1.y=W[j].y;
  for (i=0; i<n1; i++) {
   if (i==n1-1) { P2.x=P[0].x; P2.y=P[0].y; }
   else { P2.x=P[i+1].x; P2.y=P[i+1].y; }
   P1.x=P[i].x; P1.y=P[i].y;
   if (Cross(W1,W2,P1,P2)) {
    if (CrossPoint(W1,W2,P1,P2)) {
     C[nc].x=T.x; C[nc].y=T.y;
     Nj[nc]=(i==n1-1 ? 0 : i+1);
     nc++;
    }
   }
  }
  if (nc==0) {
   j++; if (j==n2) j=0;
   goto NEXT_J;
  }
  else {
   rmin=MAXFLOAT;
   for (k=0; k<nc; k++) { //Ищем ближайшее к началу ребра пересечение
    r=Rast (W1,C[k]);
    if (r<rmin) {
     kmin=k; nmin=Nj[k]; rmin=r;
    }
   }
   S[n].x=C[kmin].x; S[n].y=C[kmin].y; n++;
   if (Check()) return;
   i=nmin;
   //S[n].x=P[i].x; S[n].y=P[i].y; n++;
   goto NEXT_I; //Идем дальше по P
  }
 }
 else { //Нет пересечений - идти дальше по P
  i++; if (i==n1) i=0;
  goto NEXT_I;
 }
}

int main (void) {
 int i;
 FILE *f;

 f=fopen ("bars.dat","rt");
 if (f==NULL) {
  clrscr();
  printf ("\n Не могу открыть файл bars.dat для чтения данных!");
  printf ("\n Файл должен содержать данные для 2 многоугольников в виде");
  printf ("\n n1 PX1 PY1 ... PXn1 PYn1");
  printf ("\n n2 WX1 WY1 ... WXn2 WYn2");
  printf ("\n где N1,N2 - число вершин, PXi,PYi,WXi,WYi их X- и Y- координаты");
  printf ("\n Вершины P,W упорядочены по часовой стрелке, многоугольники без самопересечений");
  printf ("\n Начальная вершина должна принадлежать контуру");
  return 1;
 }
 Read (f); fclose (f);
 if (!InitVga()) {
  clrscr();
  printf ("\n Can't open VGA graphics!");
  return 1;
 }
 x1=10; x2=getmaxx()-10;
 y1=4+textheight("Щ"); y2=getmaxy()-4-textheight("Щ");

 setfillstyle (SOLID_FILL,WHITE);
 bar (0,0,getmaxx(),getmaxy());
 setcolor (RED);
 rectangle (x1,y1,x2,y2);

 Draw ();
 Message("Press ENTER to continue");
 Enter();

 Objed();
 setfillstyle (SOLID_FILL,GREEN);
 setlinestyle (SOLID_LINE,0,3);
 for (i=0; i<n-1; i++) line (Round(S[i].x),Round(S[i].y),Round(S[i+1].x),Round(S[i+1].y));
 line (Round(S[0].x),Round(S[0].y),Round(S[n-1].x),Round(S[n-1].y));

 Message("OK. Press ESC to exit");
 Enter();

 closegraph();
 return 0;
}

После вывода объединения происходит выход из программы по нажатию клавиши.

 Скриншот (новое окно)

 Архив ZIP с файлами .CPP и .EXE (43 Кб)

Рейтинг@Mail.ru

вверх гостевая; E-mail