文档章节

多边形直线剪裁算法

o
 osc_g8254g7s
发布于 2019/08/19 19:15
字数 631
阅读 12
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

直线与多边形求交算法 Cohen-Sutherland

采用位运算,计算直线与多边形之间关系

使用编码,将多边形窗口区域分为五个部分,根据区域选择抛弃线段

  • 两端点都在视口区域内,区域码相或为 0 , 接受
  • 两端点至少共享一个不可见区域,区域码相与不为 1 , 拒绝
/// <summary>
    /// The Cohen Sutherland line clipping algorithm
    /// </summary>
    public class CohenSutherland
    {
        /// <summary>
        /// Bitfields used to partition the space into 9 regiond
        /// </summary>
        private const byte INSIDE = 0; // 0000
        private const byte LEFT = 1;   // 0001
        private const byte RIGHT = 2;  // 0010
        private const byte BOTTOM = 4; // 0100
        private const byte TOP = 8;    // 1000



 

        /// <summary>
        /// Compute the bit code for a point (x, y) using the clip rectangle
        /// bounded diagonally by (xmin, ymin), and (xmax, ymax)
        /// ASSUME THAT xmax , xmin , ymax and ymin are global constants.
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        private static byte ComputeOutCode(Extents extents, double x, double y)
        {
            // initialised as being inside of clip window
            byte code = INSIDE;

            if (x < extents.Left)           // to the left of clip window
                code |= LEFT;
            else if (x > extents.Right)     // to the right of clip window
                code |= RIGHT;
            if (y < extents.Bottom)         // below the clip window
                code |= BOTTOM;
            else if (y > extents.Top)       // above the clip window
                code |= TOP;

            return code;
        }

        /// <summary>
        /// Cohen–Sutherland clipping algorithm clips a line from
        /// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with
        /// diagonal from (xmin, ymin) to (xmax, ymax).
        /// </summary>
        /// <param name="x0"></param>
        /// <param name="y0""</param>
        /// <param name="x1"></param>
        /// <param name="y1"></param>
        /// <returns>a list of two points in the resulting clipped line, or zero</returns>
        public static List<PointDType> CohenSutherlandLineClip(Extents extents,
                               PointDType p0, PointDType p1)
        {
            double x0 = p0.X;
            double y0 = p0.Y;
            double x1 = p1.X;
            double y1 = p1.Y;

            // compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
            byte outcode0 = CohenSutherland.ComputeOutCode(extents, x0, y0);
            byte outcode1 = CohenSutherland.ComputeOutCode(extents, x1, y1);
            bool accept = false;

            while (true)
            {
                if ((outcode0 | outcode1) == 0)  // 位或为 0, 在矩形内部,接受
                {
                    accept = true;
                    break;
                }
                else if ((outcode0 & outcode1) != 0) // 位与为 1,代表在同一个矩形外部区域中,拒绝
                {
                    break;
                }
                else
                {
                    // failed both tests, so calculate the line segment to clip
                    // from an outside point to an intersection with clip edge
                    double x, y;

                    // At least one endpoint is outside the clip rectangle; pick it.
                    byte outcodeOut = (outcode0 != 0) ? outcode0 : outcode1;

                    // Now find the intersection point;
                    // use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
                    if ((outcodeOut & TOP) != 0)
                    {   // point is above the clip rectangle
                        x = x0 + (x1 - x0) * (extents.Top - y0) / (y1 - y0);
                        y = extents.Top;
                    }
                    else if ((outcodeOut & BOTTOM) != 0)
                    { // point is below the clip rectangle
                        x = x0 + (x1 - x0) * (extents.Bottom - y0) / (y1 - y0);
                        y = extents.Bottom;
                    }
                    else if ((outcodeOut & RIGHT) != 0)
                    {  // point is to the right of clip rectangle
                        y = y0 + (y1 - y0) * (extents.Right - x0) / (x1 - x0);
                        x = extents.Right;
                    }
                    else if ((outcodeOut & LEFT) != 0)
                    {   // point is to the left of clip rectangle
                        y = y0 + (y1 - y0) * (extents.Left - x0) / (x1 - x0);
                        x = extents.Left;
                    }
                    else
                    {
                        x = double.NaN;
                        y = double.NaN;
                    }

                    // Now we move outside point to intersection point to clip
                    // and get ready for next pass.
                    if (outcodeOut == outcode0)
                    {
                        x0 = x;
                        y0 = y;
                        outcode0 = CohenSutherland.ComputeOutCode(extents, x0, y0);
                    }
                    else
                    {
                        x1 = x;
                        y1 = y;
                        outcode1 = CohenSutherland.ComputeOutCode(extents, x1, y1);
                    }
                }
            }

            // return the clipped line
            return (accept) ?
                new List<PointDType>()
            {
            new PointDType(x0,y0),
            new PointDType(x1, y1),
            } : null;
        }
    }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
图形学基础(一)光栅图形学_下:剪裁

c++,MFC,VS2017 准备(矩形,线段,多边形) void CclipView::OnDraw(CDC* pDC){ } void CclipView::OnLButtonDblClk(UINT nFlags, CPoint point)//线段{ } void CclipView::OnRButtonDblClk......

osc_ylezri59
04/15
8
0
图形学基础(一)光栅图形学_下:剪裁

c++,MFC,VS2017 准备(矩形,线段,多边形) void CclipView::OnDraw(CDC* pDC){ } void CclipView::OnLButtonDblClk(UINT nFlags, CPoint point)//线段{ } void CclipView::OnRButtonDblClk......

osc_a8r2ub9u
04/15
10
0
Cyrus-Beck图像裁剪算法归纳

此算法能使用任意多边形对一条直线段进行裁剪。 类GLdoublePoint: 公有—GLdouble x ,y; 类line: 公有—GLdoublePoint first,second; linelist: line型数据组成的链表,用于描述多边形...

小青_1989
2016/03/02
1
0
Sutherland-Hodgman算法(多边形裁剪)

Sutherland-Hodgman算法 Sutherland-Hodgman算法也叫逐边裁剪法,该算法是萨瑟兰德(I.E.Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。 一,基本...

长平狐
2013/12/25
3K
0
计算几何算法概览

计算几何算法概览 一、引言   计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为...

山哥
2014/04/10
254
1

没有更多内容

加载失败,请刷新页面

加载更多

VB语言基础重要知识点12

我们课程,我们做一些针对于考试的简要讲解。 一、有关考试的几个问题 首先,提问:考试最重要的是什么? 答案其实很简单:得分!!!!! 想要得分,就要做到基本的保存。 保存哪些文件呢?...

刘金玉编程
2019/10/30
5
0
全网最全JAVA、Python电子书!限时领取,过时不候!

给大家整理了最全的入门+进阶书籍!!! 免费领取,无套路! 加微信发送“电子书” 秒通过,秒发资源! 本文分享自微信公众号 - Python进击者(JAVAandPythonJun)。 如有侵权,请联系 supp...

kuls
01/16
18
0
原创356--免费还是付费

最近得有一个星期,被一个录屏软件(record it)烦到了,本来免费版可以无限制录制,只能720p,GIF不支持,高清不支持,没有剪辑功能。 之前调研了好几种,用起来还是这个方便,就一直用了。...

八音弦
04/24
14
0
数字IC技术讨论群,设计和验证、前端和后端,总有你感兴趣的话题。快满了,需要的抓紧加入。

本文分享自微信公众号 - 白山头讲IC(gray_mount)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

白山头
04/29
5
0
how to install mongodb in centos7

[root@xtwj88 ~]# cat /etc/yum.repos.d/mongodb-org-4.2.repo [mongodb-org-4.2]name=MongoDB Repositorybaseurl=https://repo.mongodb.org/yum/redhat/$releasever/mongodb-org/4.2/x86......

qwfys
58分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部