直线裁剪

2025年3月17日 | 阅读 7 分钟

它通过使用线段裁剪算法执行。线段裁剪算法是

Cohen Sutherland 线段裁剪算法
中点细分线段裁剪算法
梁-Barsky 线段裁剪算法

Cohen Sutherland 线段裁剪算法

在算法中，首先，它检测线段是否位于屏幕内部或外部。所有线段都属于以下类别之一

Visible
不可见
裁剪情况

1. 可见：如果线段位于窗口内，即线段的两个端点都位于窗口内。线段可见，将按原样显示。

2. 不可见：如果线段位于窗口外，它将不可见并被拒绝。此类线段将不会显示。如果满足以下任何一个不等式，则认为该线段不可见。设 A (x₁,y₂) 和 B (x₂,y₂) 是线段的端点。

x_min,x_max是窗口的坐标。

y_min,y_max也是窗口的坐标。
x₁>x_max
x₂>x_max
y₁>y_max
y₂>y_max
x₁<x_min
x₂<x_min
y₁<y_min
y₂<y_min

3. 裁剪情况：如果线段既不可见也不是不可见的情况。它被认为是裁剪情况。首先，根据下面给出的九个区域找到线段的类别。所有九个区域都被分配了代码。每个代码是 4 位。如果线段的两个端点都有尾部位为零，则认为该线段可见。

中心区域的代码为 0000，即区域 5 被认为是一个矩形窗口。

下图显示了各种类型的线段

线段 AB 是可见情况
线段 OP 是不可见情况
线段 PQ 是一条不可见的线段
线段 IJ 是裁剪候选者
线段 MN 是裁剪候选者
线段 CD 是裁剪候选者

Cohen Sutherland 线段裁剪的优点

它非常快速地计算端点，并快速拒绝和接受线段。
它可以裁剪比屏幕尺寸大得多的图片。

Cohen Sutherland 线段裁剪算法

步骤 1：计算线段两个端点的位置

步骤 2：对这两个端点执行 OR 运算

步骤 3：如果 OR 运算给出 0000
那么
线段被认为是可见的
否则
对两个端点执行 AND 运算
如果 AND ≠ 0000
那么线段是不可见的
else
And=0000
线段被认为是裁剪情况。

步骤 4：如果线段是裁剪情况，找到与窗口边界的交点
m=(y₂-y₁ )(x₂-x₁)

(a) 如果位 1 为“1”，则线段与矩形窗口的左边界相交
y₃=y₁+m(x-X₁)
其中 X = X_wmin
其中 X_wmin是窗口的 X 坐标的最小值

(b) 如果位 2 为“1”，则线段与右边界相交
y₃=y₁+m(X-X₁)
其中 X = X_wmax
其中 X 更多是窗口的 X 坐标的最大值

(c) 如果位 3 为“1”，则线段与底边界相交
X₃=X₁+(y-y₁)/m
其中 y = y_wmin
y_wmin是窗口的 Y 坐标的最小值

(d) 如果位 4 为“1”，则线段与顶边界相交
X_3=X1+(y-y₁)/m
其中 y = y_wmax
y_wmax是窗口的 Y 坐标的最大值

Cohen-Sutherland 线段裁剪算法示例

设 R 为矩形窗口，其左下角位于 L (-3, 1)，右上角位于 R (2, 6)。找到图中端点的区域代码

点 (x, y) 的区域代码是根据方案设置的
位 1 = sign (y-y_max)=sign (y-6) 位 3 = sign (x-x_max)= sign (x-2)
位 2 = sign (y_min-y)=sign(1-y) 位 4 = sign (x_min-x)=sign(-3-x)

其中

所以

A (-4, 2)→ 0001 F (1, 2)→ 0000
B (-1, 7) → 1000 G (1, -2) →0100
C (-1, 5)→ 0000 H (3, 3) → 0100
D (3, 8) → 1010 I (-4, 7) → 1001
E (-2, 3) → 0000 J (-2, 10) → 1000

我们通过测试问题中找到的区域代码，将线段放入适当的类别中。

类别 1（可见）： EF 因为两个端点的区域代码都是 0000。

类别 2（不可见）： IJ 因为 (1001) AND (1000) =1000（不是 0000）。

类别 3（裁剪候选）： AB 因为 (0001) AND (1000) = 0000，CD 因为 (0000) AND (1010) =0000，以及 GH。因为 (0100) AND (0010) =0000。

裁剪候选者是 AB， CD，和 GH。

在裁剪 AB 中，A 的代码是 0001。为了将 1 推到 0，我们裁剪与边界线 x_min=-3 的交点。得到的交点是 I₁ (-3,3 Line Clipping )。我们裁剪（不显示）AI₁ 和 I₁ B。I₁ 的代码是 1001。 I₁ B 的裁剪类别是 3，因为 (0000) AND (1000) 是 (0000)。现在 B 在窗口外（即它的代码是 1000），因此我们通过裁剪与线 y_max=6 的交点将 1 推到 0。得到的交点是 l₂ (-1 Line Clipping ,6)。因此 I₂ B 被裁剪。I₂ 的代码是 0000。剩余的线段 I₁ I₂ 被显示，因为两个端点都位于窗口内（即它们的代码是 0000）。

对于裁剪 CD，我们从 D 开始，因为它位于窗口外。它的代码是 1010。我们通过裁剪与线 y_max=6 的交点将第一个 1 推到 0。得到的交点 I₃ 是 ( Line Clipping ,6)，它的代码是 0000。因此 I₃ D 被裁剪，而剩余的线段 CI₃ 的两个端点都编码为 0000，因此它被显示。

对于裁剪 GH，我们可以从 G 或 H 开始，因为它们都在窗口外。G 的代码是 0100，我们通过裁剪与线 y_min=1 的交点将 1 推到 0。得到的交点是 I₄ (2 Line Clipping ,1)，它的代码是 0010。我们裁剪 GI₄ 并处理 I₄ H。线段 I₄ H 不显示，因为 (0010) AND (0010) =0010。

使用 Cohen Sutherland 算法执行线段裁剪的程序

#include <iostream.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>
class data
{
	int gd, gmode, x, y, xmin,ymin,ymax,xmax;
	int a1,a2;
	float x1, y1,x2,y2,x3,y3;
	int xs, ys, xe, ye;
	float maxx,maxy;
	public:
		void getdata ();
		void find ();
		void clip ();
		void display (float, float,float,float);
		void checkonof (int);
		void showbit (int);
};
void data :: getdata ()
{
	cout<<"Enter the minimum and maximum coordinate of window (x, y) ";
           cin >>xmin>>ymin>>xmax>>ymax;
           cout<<"Enter the end points of the line to be clipped";
           cin >>xs>>ys>>xe>>ye;
           display (xs, ys, xe,ye);
}
void data :: display (float, xs, float, ys,float xe, float ye)
{
	int gd=DETECT;
	initgraph (&gd,&gmode, "");
	maxx=getmaxx();
	maxy=getmaxy();
	line (maxx/2,0,maxx/2,maxy);
	line (0, maxy/2,maxx,maxy/2);
	rectangle (maxx/2+xmin,maxy/2-ymax,maxx/2+xmax,maxy/2-ymin);
	line (maxx/2+xs,maxy/2-ys,maxx/2+xe,maxy/2-ye);
	getch();
}
void data :: find ()
{
	a1=0;
	a2=0;
	if ((ys-ymax)>0)
               a1+=8;
	if ((ymin-ys)>0)
	    a1+=4;
	if ((xs-xmax)>0)
	     a1+=2;
            if ((xmin-xs)>0)
	     a1+=1;
	 if ((ye-ymax)>0)
	    a2+=8;
           if ((ymin-ye)>0)
              a2+=4;
          if ((xe-xmax)>0)
               a2+=2;
          if ((xmin-xe)>0)
                a2+=1;
         cout<<"\nThe area code of Ist point is ";
                 showbit (a1);
         getch ();
         cout <<"\nThe area code of 2nd point is ";
         showbit (a2);
         getch ();
}
void data :: showbit (int n)
{
        int i,k, and;
        for (i=3;i>=0;i--)
        {
              and =1<<i;
	   k = n?
	   k ==0?cout<<"0": cout<<"1\"";         
          }
}
void data ::clip()
{
         int j=a1&a2;
         if (j==0)
         {
              cout<<"\nLine is perfect candidate for clipping";
              if (a1==0)
	   {
                    else
             {
                   checkonof(a1);
                   x2=x1;y2=y1;
             }
             if (a2=0)
            {
                 x3=xe; y3=ye;
            }
           else
           {
                   checkonof (a2);
                   x3=x1; y3=y1;
            }
            xs=x2; ys=y2;xe=x3;ye=y3;
            cout << endl;
            display (xs,ys,xe,ye);
            cout<<"Line after clipping";
            getch ()
          }
       else if ((a1==0) && (a2=0))
       {
               cout <<"\n Line is in the visible region";
               getch ();
       }
}
void data :: checkonof (int i)
{
      int j, k,l,m;
      1=i&1;
      x1=0;y1=0;
       if (1==1)
      {
             x1=xmin;
             y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys);
      }
      j=i&8;
   if (j>0)
   {
             y1=ymax;
	  x1=xs+(y1-ys)/(ye-ys))*(xe-xs);
    }
    k=i & 4;
    if (k==1)
    {
           y1=ymin;
           x1=xs+((y1-ys)/(ye-ys))*(xe-xs);
    }
    m= i&2;
     if (m==1)
     {
            x1=xmax;
            y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys);
      }
      main ()
      {
             data s;
             clrscr();
             s.getdata();
             s.find();
             getch();
             closegraph ();
             return ();
    }

输出