直线裁剪算法


一、前言

Sutherland-Cohen算法

它叫,“苏泽兰抠恨算法” ​ :smile:

用矩形框裁剪直线。

整体思想

  • 首先,判断直线是否完全在裁剪矩形内,或者完全在矩形框外。

  • 若不能得出以上两种结论,则计算出线段与矩形边界的交点。交点把直线分成两段(若两个交点,则先看其中一个交点),把完全在窗口外的舍去,然后再对另一条再做判断。

P.S 具体实现中,并非是将窗口外的舍去,其本质也就是找出新的两个线段端点(被切割部分),然后再将其画出罢了。

二、实现效果

三、分区编码

先说说判断端点位置用的分区编码

将屏幕分成九个区域,用四位0、1编码为每一个区域编码。

  1. 最中间,是裁剪的矩形框区域,内部为0000.
  2. 其左侧部分,也就是x值小于XL部分,其第四位编码均为1;
  3. 其右侧部分,也就是x值大于XR部分,其第三位编码均为1,
  4. 其上部,也就是y值大于YT部分,其第一位编码均为1;
  5. 其下部,也就是y值小于YB部分,第第二位编码均为1.

如下,(笛卡尔平面坐标系,非屏幕坐标系)

四、具体实现步骤

4.1总体思路

  1. 对直线两端点p1、p2进行编码,

    p1、p2编码分别记为,code1、code2。

    code1={a1、b1、c1、d1}

    code2={a2、b2、c2、d2}

    其中,ai,bi,ci、di的取值范围为{0,1},i={1,2}

  2. 若ai=bi=ci=di=0,此情况为直线在矩形同一外域,则显示整条直线。否则,进行第三步

  3. 对四位编码逐位判断。

    若a1=1或者a2=1,则该点在矩形框的上部,也就是“三、分区编码”中的情况“4”。则求直线与矩形框的纵坐标的y的最小值(屏幕坐标系)将该点坐标移为交点(也就相当于删去交点以上部分)

    若b1=1或者b2=1,则该点在矩形框的下部,也就是“三、分区编码”中的情况“5”。则求直线与矩形框的纵坐标的y的最大值(屏幕坐标系)将该点坐标移为交点(也就相当于删去交点以下部分)

    若c1=1或者c2=1,则该点在矩形框的右部,也就是“三、分区编码”中的情况“3”。则求直线与矩形框的横坐标的x的最大值(屏幕坐标系)将该点坐标移为交点(也就相当于删去交点以右部分)

    若d1=1或者d2=1,则该点在矩形框的左部,也就是“三、分区编码”中的情况“2”。则求直线与矩形框的横坐标的y的最小值(屏幕坐标系)将该点坐标移为交点(也就相当于删去交点以左部分)

    至于”矩形框的上部“,则是在视觉上而言。以上皆是。

  4. 画出直线。(此时会只画出被移动端点后的直线)

4.2 C#代码实现

4.2.1 各参数含义

  • x1, y1, x2, y2:输入直线两端坐标;
  • code1, code2:两端点的编码,各四位。
  • done:是否剪裁完毕的标志,True:剪裁完。
  • display:是否需显示的标志,True:显示直线x1, y1, x2, y2。
  • m:直线之斜率。
  • mark:是否需要进行交换标志。

4.2.1 方法功能描述

1)主算法为clip_a_line。它调用四个子程序,功能分别为:

2)encode(x, y, c):功能为:判断点(x, y)所在的区域,赋予c以相应的编码。

3)accept(c1, c2):功能为:根据两端点的编码c1, c2,判断直线是否在窗口之内。

4)reject(c1, c2):功能为:根据两端点的编码c1, c2,判断直线是否在窗口之外。

5)swap_if_needed(x1, y1, x2, y2, c1, c2);功能为:判断(x1, y1)是否在窗口之外,如否,则将x1, y1, c1值与x2, y2, c2值交换

4.2.3 代码部分

using System;
using System.Drawing;
using System.Windows.Forms;

namespace Cohen_Sutherland
{
    public partial class Form1 : Form
    {
        static Graphics graphics;
        static Bitmap bitmap;
        public Form1()
        {
            InitializeComponent();
            graphics = panel1.CreateGraphics();
            bitmap = new Bitmap(panel1.Width, panel1.Height);
        }

        Pen linepen = new Pen(Color.Red, 2);//原始画线画笔
        Pen linepen1 = new Pen(Color.Green, 2);//裁剪画笔
        Pen Ectanglepen = new Pen(Color.Blue, 2);//矩形画笔
        private void button_DrawrEctangle_Click(object sender, EventArgs e)
        {
            Point p1 = new Point(260, 200);
            Point p2 = new Point(410, 200);
            Point p3 = new Point(410, 350);
            Point p4 = new Point(260, 350);
            Point[] points;
            points = new Point[] { p1, p2, p3, p4 };


            graphics.DrawPolygon(Ectanglepen, points);
            graphics.DrawImage(bitmap, 0, 0, panel1.Width, panel1.Height);
        }

        private void button_DrawLine_Click(object sender, EventArgs e)
        {
            graphics.DrawLine(linepen, 190, 180, 460, 290);
        }
        private void button_Clip_Click(object sender, EventArgs e)
        {
            clip_a_line(190, 180, 460, 290, 260, 200, 410, 350);
        }

        //为p1、p2端点编码
        public void encode(int x, int y, int[] code, int xw_min, int xw_max, int yw_min, int yw_max)
        {
            int i;
            for (i = 0; i < 4; i++)
                code[i] = 0;
            if (x < xw_min)
                code[3] = 1;
            else
            if (x > xw_max)
                code[2] = 1;
            if (y > yw_max)
                code[1] = 1;
            else
            if (y < yw_min)
                code[0] = 1;
        }

        //主函数,总控
        public void clip_a_line(int x1, int y1, int x2, int y2, int xw_min, int yw_min, int xw_max, int yw_max)
        {
            int[] code1 = new int[4];//p1端点的编码
            int[] code2 = new int[4];//p2端点的编码
            int done;
            int display;
            float m;//直线斜率
            int x11, x22, y11, y22, mark;
            done = 0;     // done为是否剪裁完毕的标志变量
            display = 0;      // display为是否显示直线的标志变量
            while (done == 0)
            {
                x11 = x1;
                x22 = x2;
                y11 = y1;
                y22 = y2;
                encode(x1, y1, code1, xw_min, xw_max, yw_min, yw_max);    // 为起点编码
                encode(x2, y2, code2, xw_min, xw_max, yw_min, yw_max);    // 为终点编码
                if (accept(code1, code2) == 1)         // 判断直线两端点是否都在剪裁框内,是则剪裁完毕,显示直线
                {
                    done = 1;
                    display = 1;
                    break;
                }
                else if (reject(code1, code2) == 1)  // 判断直线两端点是否在剪裁框的同一外域,是则剪裁完毕,显示直线
                {
                    done = 1;
                    break;
                }
                //mark是否交换p1、p2的标志等于1则交换
                //swap_if_needed方法只是判断出是否需要交换、并返回是否需要交换的标志mark
                mark = swap_if_needed(code1, code2); // mark的意义是:swap_if_needed中是否交换过code1[4]和code2[4]
                if (mark == 1)                     // 若交换过,mark = swap_if_needed = 1,否则mark = swap_if_needed = 0
                {
                    x1 = x22;                 // 若mark = 1,交换两端点坐标
                    x2 = x11;
                    y1 = y22;
                    y2 = y11;
                }
                if (x1 == x2)                      // 斜率不存在的情况。即,x1=x2,则令斜率为 -1
                    m = -1;
                else
                    m = (float)(y2 - y1) / (float)(x2 - x1);// 计算斜率

                // 根据起点p1编码的每一位,对直线进行剪裁,实际上是移动起点的坐标
                //【注意】:处于屏幕坐标系下
                if (code1[0] == 1) //判断编码第一位,为1,则该点在视觉上处于“上侧”,屏幕坐标系上则p1纵坐标小于矩形纵坐标最小值。            
                {
                    if (x1 != x2)
                        x1 += (int)((yw_min - y1) / m);//x1移动到直线与yw_min交点处。
                    y1 = yw_min;//将p1的y1移为矩形纵坐标最小值。
                }
                else
                if (code1[1] == 1)
                {
                    if (x1 != x2)
                        x1 -= (int)((y1 - yw_max) / m);
                    y1 = yw_max;
                }
                else
                if (code1[2] == 1)
                {
                    y1 -= (int)((x1 - xw_max) * m);
                    x1 = xw_max;
                }
                else
                if (code1[3] == 1)
                {
                    y1 += (int)((xw_min - x1) * m);
                    x1 = xw_min;
                }
            }
            if (display == 1)
            {// 若显示直线标志为1,则画出直线
                graphics.Clear(Color.White);//清空屏幕
                //画出裁剪矩形
                Point p1 = new Point(xw_min, yw_min);
                Point p2 = new Point(xw_max, yw_min);
                Point p3 = new Point(xw_max, yw_max);
                Point p4 = new Point(xw_min, yw_max);
                Point[] points;
                points = new Point[] { p1, p2, p3, p4 };
                graphics.DrawPolygon(Ectanglepen, points);
                //画出直线
                graphics.DrawLine(linepen1, x1, y1, x2, y2);
            }
        }

        //判断p1、p2是否都在矩形内部
        public int accept(int[] code1, int[] code2)
        {
            int i, flag;
            flag = 1;
            for (i = 0; i < 4; i++)
                if ((code1[i] == 1) || (code2[i] == 1))
                {
                    flag = 0;
                    break;
                }
            return (flag);
        }

        //判断p1、p2是否都在矩形外部
        public int reject(int[] code1, int[] code2)
        {
            int i, flag;
            flag = 0;//否
            for (i = 0; i < 4; i++)
                if ((code1[i] == 1) && (code2[i] == 1))
                {
                    flag = 1;//是
                    break;
                }
            return (flag);
        }

        //p1、p2是否需要被交换
        public int swap_if_needed(int[] code1, int[] code2)
        {
            int i, flag1, flag2, tmp;
            flag1 = 1;
            for (i = 0; i < 4; i++)
                if (code1[i] == 1)
                {
                    flag1 = 0;//code1中存在1,即在点外部。不需要交换
                    break;
                }
            flag2 = 1;
            for (i = 0; i < 4; i++)
                if (code2[i] == 1)
                {
                    flag2 = 0;//code2中存在1,即点在外部。不需要交换
                    break;
                }
            if ((flag1 == 0) && (flag2 == 0))//说明两个编码中的含有1,则不能交换
                return (0);
            if ((flag1 == 1) && (flag2 == 0))//此时code1需要被交换,code2不需要被交换,
            {                                 //将二者编码进行交换。
                for (i = 0; i < 4; i++)
                {
                    tmp = code1[i];
                    code1[i] = code2[i];
                    code2[i] = tmp;
                }
                return (1);                   //返回需要交换坐标的信号,在总控方法中对坐标进行交换
            }
            return (0);                        //返回不需要交换坐标的信号。
        }


    }
}

五、流程图

5.1clip_a_line(总控方法)


5.2 encode方法


5.3 reject方法


5.4 accept方法


5.5 swap_if_needed方法


Over~


文章作者: 李世昱
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 李世昱 !
评论
  目录