Cohen-SutherLand 裁剪算法

Cohen-SutherLand实现裁剪直线的两个关键函数

 //计算点 x,y的编码
void CCohenSutherLandView::CompOutCode(float x,float y,CRect* rect,OutCode* outCode)
{
 outCode->all = 0;
 outCode->top = outCode->bottom =0;

 if (y < rect->top)
 {
  outCode->top = 1;
  outCode->all += 1;
 }
 else if (y > rect->bottom)
 {
  outCode->bottom = 1;
  outCode->all += 1;
 }

 outCode->right = outCode->left = 0;

 if (x > rect->right)
 {
  outCode->right = 1;
  outCode->all += 1;
 }
 else if(x < rect->left)
 {
  outCode->left = 1;
  outCode->all += 1;
 }
}

//CohenSutherLand线段裁剪算法
void CCohenSutherLandView::CohenSutherLineClip(CDC* pDC,float x0,float y0,float x1,float y1, CRect* rect)
{
 BOOL accept,done;
 OutCode outCode0,outCode1;
 OutCode *outCodeOut;
 float x,y;
 accept = FALSE;
 done = FALSE;
 CompOutCode(x0,y0,rect,&outCode0);
 CompOutCode(x1,y1,rect,&outCode1);
 do
 {
  if (outCode0.all == 0 && outCode1.all == 0) //完全可见
  {
   accept = TRUE;
   done = TRUE;
  }
  else if ((outCode0.all & outCode1.all) != 0) //显然可见
  {
   done = TRUE;
  }
     else   //进行求交测试
  {
   if (outCode0.all != 0)
   {
    outCodeOut = &outCode0; 
   }
   else
   {
    outCodeOut = &outCode1; 
   }

   if (outCodeOut->left)
   {
    y = y0 + (y1 - y0) * (rect->left - x0) / (x1 - x0);   //线段与窗口左边求交
    x = (float)rect->left;
   }
   else if (outCodeOut->top)
   {
    x = x0 + (x1 - x0) * (rect->right - y0) / (y1 - y0);  //线段与窗口上边求交
       y = (float) rect->top; 
   }
   else if (outCodeOut->right)
   {
    y = y0 + (y1 - x0) * (rect->right - x0) / (x1 - x0); //线段与窗口右边求交
    x = (float)rect->right;
   }
   else if (outCodeOut->bottom)
   {
    x = x0 + (x1 - x0) * (rect->bottom - x0) / (y1 - y0); //线段与窗口下边求交
    y = (float)rect->bottom;
   }
   if (outCodeOut ->all == outCode0.all)
   {
    x0 = x;        //以交点为界，将线段位于窗口所在的直线的外侧的部分丢弃                             
    y0 = y;       //剩下的继续
    CompOutCode(x0,y0,rect,&outCode0);
   }
   else
   {
    x1 = x;
    y1 = y;
    CompOutCode(x1,y1,rect,&outCode1);
   }
  }
 } while(!done);

 if (accept) 
 { 
  pDC->MoveTo(int(x0),int(y0));
  pDC->LineTo(int(x1),int(y1));
 }
}
具体原理等，参见《计算机图形学》北京大学出版社  倪明田等  第111页

责任编辑 webmaster

相关链接

字符串匹配算法研究

C编程- 以空间换时间算法集锦

遗传格网障碍算法

蒙特卡罗算法在围棋游戏AI中的...

背包问题的算法集

Gtk+的裁剪

负载均衡的基本算法

算法—用栈实现递归