精华内容
下载资源
问答
  • 计算机图形学(简单多边形裁剪算法).doc
    2021-07-29 01:11:41

    计算机图形学(简单多边形裁剪算法)

    简单多边形裁剪算法

    摘要:多边形裁剪算法与线性裁剪算法具有更广泛的实用意义,因此它是目前裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法,它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息,生成结果多边形,该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点。

    关键词:多边形裁剪;交点;前驱;后继;矢量数组

    一、技术主题的基本原理

    简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点,它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪,输出结果多边形。

    二、发展研究现状

    近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 CrossPointIndex{

    int nPredecessorlndex=0//前驱序号

    int nSuccessorIndex=0//后继序号

    }

    说明:CrossPointIndex用于记录交点在多边形中的前驱与后继的序号信息,以及记录同一交点在两个多边形中顶点序号。即若P为多边形S与多边形C的交点,为了表示P在S和C中为同一点,则可用CrossPointIndex记录用nPredecessorIndex记录P在S中的序号、用nSuccessorIndex记录P在C中序号。

    3)线段的数据结构如下:

    Segment{

    int nStartIndex=0

    int nEndIndex=0

    int* pIndexes;

    int nIndexCount;

    }

    说明:Segment表示多边形在另一个多边形内(外)的线段,nStartaIndex为Segment起始顶点的序号,nEndIndex为Segment终止顶点的序号,pIndexes为起始顶点与终止顶点之间的顶点序号集合,nIndexCount为pIndexes中元素个数。

    3、算法设计

    1)第一阶段:

    采用射线法计算并判断S(或C)在C(或S)内,并修改S(或C)顶点Vertex的IsInPolygon的值。

    由于射线可以任意选取,为了方便可以将射线定为从被测点开始射向X轴坐标正方向的水平射线。由于多边形的一条边与射线的交点最为1个,因此可以循环遍历每条边并判断边与射线有无交点,若有交点,计数器加1,。最后得到的计数器的值即多边形与射线的交点个数。若交点个数为奇数,则被测点在多边形内部,若交点个数为偶数,则被测点在多边形外部。对于多边形的任意一条边,为了尽量避免求交点时用到乘除法,将判断该边与射线有无交点的算法可以包含3步:

    判断边的两个顶点是否均在被测点左方或者下方或者上方,若是则无交点,返回假并退出;

    若不满足第一条原则,且满足两个顶点均在被测点右方,则一定有顶点,返回真并退出;

    若以上两条都不满足,求出边与射线的交点,比较交点的X坐标与被测点的X坐标,若前者大于后者则返回真并退出,否则返回假并退出。

    设边的两个顶点坐标分别为(x1,y1)和(x2,y2),则边的直线方程可写为:

    X=m(y-y1)+x1

    其中,m=(x2-x1)/(y2-y1)为直线斜率的倒数。使用该方程时需要两次乘除法,效率较低。为了尽量避免求交点,第三部可以采用二分法将边分成两段,对其中两个端点分别跨过射线两侧的边段重新进行以上第一步和第二步的判断,若以上两步中还没有推出,再继续二分,直到能够被第一步和第二步判断并退出。采用二分法则避免了乘除法,算法中只有除2运算和一些判断,适合于硬件处理,二分法的循环次数一般较少,当被测点位于边上时,循环次数组最多。

    其具体的算法如下:(Point为被测点变量,point1、point2为一条边的两个端点变量)

    If(piont2.y

    {

    P1=point2;

    p2=point1

    }

    Else

    {

    p1=point1;

    p2=point2;

    }

    if(p1.y>point.y||p2.y

    Return false;//无交点

    Else If(p1.x

    Return false ;无交点

    Else if (p1.x>point.x&&p2.x>point.x)Return

    更多相关内容
  • 多边形裁剪算法

    2015-04-19 15:30:10
    多边形裁剪算法,还不错,学到挺多的,共享给大家看看
  • 多边形裁剪算法.rar

    2019-06-17 11:02:57
    此代码为多边形裁剪算法,为光栅图形学算法续,此代码可以直接运行
  • Weiler Atherton 任意多边形裁剪 Sutherland Hodgeman 算法解决了裁剪窗口为凸多边形窗口的问题 但一些应用需要涉及 任意多边形窗口含凹多边形窗口的裁剪 Weiler-Atherton 多边形裁剪算法正是满足这种要 求的算法 一...
  • ##关于此仓库Vatti多边形裁剪算法实现,执行多边形布尔运算的并集,交集,差和XOR。 虽然此存储库可用于学术目的。 到目前为止,工作已经完成 适用于自相交多边形和带Kong的多边形。 适用于主题或剪辑TODO中的...
  • 使用VS 2017实现多边形裁剪算法,此资源包括完整的项目文件,可以直接使用。此代码仅供学习交流使用。
  • SutherlandHodgman多边形裁剪算法 C++ 有详细注释
  • 目录什么是多边形裁剪前置知识算法步骤程序框图代码实现 什么是多边形裁剪 通常来说就是利用多边形来裁剪...Weiler-Atherton多边形裁剪算法 这里着重介绍Weiler-Atherton算法,其余不懂的可以先学会再看。 算法步骤


    源代码: https://github.com/ricar0/Weiler-Atherton-Alogrithm/tree/master

    什么是多边形裁剪

    通常来说就是利用多边形来裁剪多边形的一种方法,一般情况下是利用矩形来裁剪凹凸多边形

    1. 凸多边形
    2. 凹多边形

      上面红色划线部分就是裁剪出的部分

    前置知识

    1. OPENGL基础语法
      基本上就是一些画线和画多边形的操作,难度较低
    2. 求两直线交点
      较为基础的数学知识
    3. 求一个点是否落在多边形内/外
      计算几何知识
    4. Weiler-Atherton多边形裁剪算法

    这里着重介绍Weiler-Atherton算法,其余不懂的可以先学会再看。

    算法步骤

    1. 首先绘制两个相交的多边形
    2. 对于多边形1,我们从一个点出发,将所有经过的点(包含交点)存入新的数组中,对于多边形2也是同理
    3. 对两个新数组中的相同点进行点对映射
    4. 开始对裁剪多边形1进行遍历,从任意点出发,如果改点将从多边形2的内部穿越到外部,我们改变遍历点的对象,从多边形2开始遍历,依次类推…
    5. 直到当前点被遍历过,那么之前肯定形成了一个回路,我们将当前回路绘制出来就是裁剪出的多边形。
    6. 一直重复4和5操作,直到所有点都被遍历

    接下来结合图片解释一下

    在这里插入图片描述
    对于如下这个图,我们利用矩形裁剪凹多边形。
    首先从E点出发,判断E到J是否为出点,发现不是。遍历到J点,判断JF是否是出点,发现是,这时候改变遍历的对象,通过映射关系从K点开始。判断发现KC又是出点,因此再次改变遍历对象,遍历多边形到E,发现J已经被遍历过,这时直接绘制出JKE…

    程序框图

    在这里插入图片描述

    代码实现

    建立窗口以及自动调整大小

    void reshape(int w, int h) {
        glViewport(0, 0, w, h);
        glMatrixMode(GL_PROJECTION);
        glLoadIdentity();
        gluPerspective(60.0, (GLfloat)w / (GLfloat)h, 0.1, 100000.0);
        glMatrixMode(GL_MODELVIEW);
        glLoadIdentity();
        gluLookAt(0, 0, 25, 0, 0, -1, 0, 1, 0);
    }
    int main(int argc,char** argv) {
        glutInit(&argc, const_cast<char**>(argv));
        glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
        // 初始化窗口
        glutInitWindowSize(500, 500);
        glutInitWindowPosition(100, 100);
        glutCreateWindow(argv[0]);
        init();
        glutReshapeFunc(reshape);
        glutDisplayFunc(display);
    
        glutMainLoop();
    }
    
    
    

    建立点和线

    struct Point2d {
        double x, y;
        bool operator < (const Point2d &rhs) const {
            if (x==rhs.x) return y < rhs.y;
            return x < rhs.x;
        }
    };
    struct Line{
        Point2d start;
        Point2d end;
    };
    

    求两条线段交点的模板,如果不存在返回-inf

    inline Point2d Vector(Point2d a, Point2d b) {  //向量ab
        return{ b.x - a.x, b.y - a.y };
    }
    double dis2(Point2d a, Point2d b) {          //两点间的距离的平方
        return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
    }
    double cross(Point2d A, Point2d B, Point2d P) {  //向量的外积
        Point2d AB = Vector(A,B);
        Point2d AP = Vector(A,P);
        return AB.x*AP.y - AB.y*AP.x;
    }
    double dot(Point2d A, Point2d B, Point2d P) {     //向量的内积
        Point2d AB = Vector(A,B);
        Point2d AP = Vector(A,P);
        return AB.x*AP.x + AB.y*AP.y;
    }
    int dir(Point2d A, Point2d B, Point2d P) {    //点与线段方位判定
        if (cross(A, B, P) > 0)  return -1;
        else if (cross(A, B, P)<0) return 1;
        else if (dot(A, B, P) < 0) return -2;
        else if (dot(A, B, P) >= 0)
        {
            if (dis2(A, B) < dis2(A, P)) return 2;
            else return 0;
        }
        return 0;
    }
    double disLine(Point2d A, Point2d B, Point2d P) {   //点P到直线AB的距离
        return fabs(cross(A, B, P)) / sqrt(dis2(A, B));
    }
    Point2d intersection(Line u, Line v) {
        Point2d A1 = u.start;
        Point2d A2 = u.end;
        Point2d B1 = v.start;
        Point2d B2 = v.end;
        if (dir(A1, A2, B1)*dir(A1, A2, B2) <= 0 && dir(B1, B2, A1)*dir(B1, B2, A2) <= 0) {//判断有无交点
            double t = disLine(A1, A2, B1) / (disLine(A1, A2, B1) + disLine(A1, A2, B2));
            Point2d B1B2 = Vector(B1, B2);
            Point2d inter = { B1.x + B1B2.x*t, B1.y + B1B2.y*t };
            return {inter.x, inter.y};
        } else {
            return {-inf, -inf};
        }
    }
    

    求两点距离,用于排序

    double dis(Point2d point1, Point2d point2) {
        return sqrt((point1.x-point2.x)*(point1.x-point2.x) + (point1.y-point2.y)*(point1.y-point2.y));
    }
    

    判断点是否落在多边形内,这里加了个误差0.001

    bool isPointInsidePoly(Point2d P,const vector<Point2d>& polyVertices) {
        std::size_t vertCount = polyVertices.size();
        if (vertCount < 2)
            return false;
        Point2d tmp = P;
        for (int l = 0; l < 2; l++) {
            for (int r = 0; r < 2; r++) {
                P = tmp;
                if (l % 2) P.x += 0.001;
                else P.x -= 0.001;
                if (r % 2) P.y += 0.001;
                else P.y -= 0.001;
                bool inside = false;
                for (unsigned i = 1; i <= vertCount; ++i) {
                    const Point2d &A = polyVertices[i - 1];
                    const Point2d &B = polyVertices[i % vertCount];
                    if ((B.y <= P.y && P.y < A.y) || (A.y <= P.y && P.y < B.y)) {
                        double t = (P.x - B.x) * (A.y - B.y) - (A.x - B.x) * (P.y - B.y);
                        if (A.y < B.y)
                            t = -t;
                        if (t < 0)
                            inside = !inside;
                    }
                }
                if (inside) return inside;
            }
        }
        return false;
    }
    

    求交点以及重新放入数组

    void getIntersections() {//求出所有交点以及按照顺序存放在新数组中
        int len1 = poly1.size();//求出new1
        for (int i = 0; i < len1; i++) {
            new1.push_back(poly1[i]);
            vector<Point2d> tmp;
            for (auto it2 : p2) {
                Point2d p = intersection({{poly1[i].x, poly1[i].y},{poly1[(i+1)%len1].x, poly1[(i+1)%len1].y}}, it2);
                if (p.x != -inf && p.y != -inf) tmp.push_back({p.x, p.y});
            }
            sort(tmp.begin(), tmp.end(), [&](Point2d p1, Point2d p2){
                return dis(p1, poly1[i]) < dis(p2, poly1[i]);
            });
            for (auto it : tmp) new1.push_back(it);
        }
    
        int len2 = poly2.size();//求出new2
        for (int i = 0; i < len2; i++) {
            new2.push_back(poly2[i]);
            vector<Point2d> tmp;
            for (auto it2 : p1) {
                Point2d p = intersection({{poly2[i].x, poly2[i].y},{poly2[(i+1)%len2].x, poly2[(i+1)%len2].y}}, it2);
                if (p.x != -inf && p.y != -inf) tmp.push_back({p.x, p.y});
            }
            sort(tmp.begin(), tmp.end(), [&](Point2d p1, Point2d p2){
                return dis(p1, poly2[i]) < dis(p2, poly2[i]);
            });
            for (auto it : tmp) new2.push_back(it);
        }
        for (int i = 0; i < new1.size(); i++) {//映射关系,给定eps为误差范围
            for (int j = 0; j < new2.size(); j++) {
                if (fabs(new1[i].x-new2[j].x)<eps&&fabs(new1[i].y-new2[j].y)<eps) {
                    pos1[i] = j;
                    pos2[j] = i;
                }
            }
        }
        work();
    }
    

    绘制两个多边形以及初始化操作

    void prework() {
        p1.clear();
        p2.clear();
        new1.clear();
        new2.clear();
        vis1.clear();
        vis2.clear();
        pos1.clear();
        pos2.clear();
    }
    void display() {
        prework();//初始化
        glClear(GL_COLOR_BUFFER_BIT);
        glBegin(GL_LINES);
        glColor3f(1.0, 1.0, 1.0);
        int len1 = poly1.size();//绘制多边形
        for (int i = 0; i < len1; i++) {
            glVertex2f(poly1[i].x, poly1[i].y);
            glVertex2f(poly1[(i+1)%len1].x, poly1[(i+1)%len1].y);
            p1.push_back({{poly1[i].x, poly1[i].y}, {poly1[(i+1)%len1].x, poly1[(i+1)%len1].y}});
        }
        int len2 = poly2.size();
        for (int i = 0; i < len2; i++) {
            glVertex2f(poly2[i].x, poly2[i].y);
            glVertex2f(poly2[(i+1)%len2].x, poly2[(i+1)%len2].y);
            p2.push_back({{poly2[i].x, poly2[i].y}, {poly2[(i+1)%len2].x, poly2[(i+1)%len2].y}});
        }
        getIntersections();
        glEnd();
        glFlush();
    }
    
    

    最核心的代码,遍历两个多边形

    void work() {
        vector<Point2d> now;//当前选择到的点
        int len1 = new1.size();
        int len2 = new2.size();
        for (int i = 0; i < new1.size(); i++) {//new1 第一个新多边形 new2第一个新多边形
            if (vis1[i]) continue;
            int ch = 1, nowpos = i;
            while (1) {
                if (ch == 1) {//遍历第一个多边形
                    if (isPointInsidePoly(new1[nowpos], poly2)) now.push_back(new1[nowpos]);
                    if (vis1[nowpos]) {//如果该点遍历过
                        glBegin(GL_LINES);
                        glColor3f(1, 0, 0);
                        for (int j = 0; j < now.size(); j++) {//绘制交多边形
                            glVertex2f(now[j].x, now[j].y);
                            glVertex2f(now[(j+1)%now.size()].x, now[(j+1)%now.size()].y);
                        }
                        now.clear();
                        glEnd();
                        glFlush();
                        break;
                    }
                    vis1[nowpos] = true;//给当前经历点打上标记
                    if (isPointInsidePoly(new1[nowpos], poly2) && !isPointInsidePoly(new1[(nowpos+1)%len1], poly2)) {//判断是否为出点
                        ch = 2;
                        nowpos = pos1[nowpos];
                        nowpos = (nowpos + 1) % len2;
                    } else {
                        nowpos = (nowpos + 1) % len1;
                    }
                } else {//遍历第二个多边形
                    if (isPointInsidePoly(new2[nowpos], poly1)) now.push_back(new2[nowpos]);
                    if (vis2[nowpos]) {//如果该点遍历过
                        glBegin(GL_LINES);
                        glColor3f(1, 0, 0);
                        for (int j = 0; j < now.size(); j++) {//绘制交多边形
                            glVertex2f(now[j].x, now[j].y);
                            glVertex2f(now[(j+1)%now.size()].x, now[(j+1)%now.size()].y);
                        }
                        now.clear();
                        glEnd();
                        glFlush();
                        break;
                    }
                    vis2[nowpos] = true;//给当前点打上标记
                    if (isPointInsidePoly(new2[nowpos], poly1) && !isPointInsidePoly(new2[(nowpos+1)%len2], poly1)) {//判断是否为出点
                        ch = 1;
                        nowpos = pos2[nowpos];
                        nowpos = (nowpos + 1) % len1;
                    } else {
                        nowpos = (nowpos + 1) % len2;
                    }
                }
            }
        }
    }
    

    这里存入需要绘制的两个多边形,按顺序存

    void init() {
        poly1.clear();
        poly2.clear();
    //    poly1.push_back({-5, -5});
    //    poly1.push_back({-5, 5});
    //    poly1.push_back({5, 5});
    //    poly1.push_back({5, -5});
    //
    //    poly2.push_back({-7, 0});
    //    poly2.push_back({0, 7});
    //    poly2.push_back({7, 0});
    //    poly2.push_back({0, -7});
    
    //    poly1.push_back({0, -6});
    //    poly1.push_back({-3, -3});
    //    poly1.push_back({0, 3});
    //    poly1.push_back({3, 0});
    //
    //    poly2.push_back({0, -3});
    //    poly2.push_back({-3, 3});
    //    poly2.push_back({0, 6});
    //    poly2.push_back({3, 3});
    
    //    poly1.push_back({-8, -6});
    //    poly1.push_back({-8,  6});
    //    poly1.push_back({8, 6});
    //    poly1.push_back({8, -6});
    //
    //    poly2.push_back({-2, 10});
    //    poly2.push_back({12, -6});
    //    poly2.push_back({-2, 2});
    //    poly2.push_back({-12, -6});
    
        poly2.push_back({-6, -3});
        poly2.push_back({-6,  3});
        poly2.push_back({6, 3});
        poly2.push_back({6, -3});
    
        poly1.push_back({-1.98, 0.91});
        poly1.push_back({4, 6});
        poly1.push_back({12, 6});
        poly1.push_back({4, -2});
        poly1.push_back({8, 4.7});
        glClearColor(0.0, 0.3, 0.7, 0.0);
        glShadeModel(GL_SMOOTH);
    }
    
    展开全文
  • 圆对多边形裁剪算法设计与实现Python3.5源码实现
  • 二维图形裁剪算法: 参考博客: https://blog.csdn.net/m0_46359746/article/details/106392352 Liang-Barsky 线段裁剪算法: //Liang-Barsky 线段裁剪算法 class wcPt2D { public: GLfloat x,y; public: /* ...

    二维图形裁剪算法:

    参考博客:

    https://blog.csdn.net/m0_46359746/article/details/106392352

    image-20200930153345235

    Liang-Barsky 线段裁剪算法:

    //Liang-Barsky 线段裁剪算法
    
    class wcPt2D {
    
    public:
    	GLfloat x,y;
    public:
    	/*
    Default Constructor:initalize position 48(0.0,0.0).*/
    	wcPt2D(){
    		x=y=0.0;
    	}
    
    	wcPt2D(GLfloat nx, GLfloat ny): x(nx), y(ny){}
    
    	wcPt2D(const wcPt2D& pCopy){
    		this->x=pCopy.x;
    		this->y=pCopy.y;
    	}
    
    	void setCoords(GLfloat xCoord,GLfloat yCoord){
    		x = xCoord;
    		y = yCoord;
    		return ;
    	}
    
    	wcPt2D& operator= (wcPt2D p2){
    		this->x=p2.getx ();
    		this->y=p2.gety ();
    		return *this;
    	}
    
    
    	GLfloat getx()const{
    		return x;
    	}
    	GLfloat gety ( ) const {
    		return y;
    	}
    };
    
    inline GLint round(const GLfloat a){
    	return GLint(a + 0.5);
    }
    
    GLint clipTest(GLfloat p, GLfloat q, GLfloat * u1, GLfloat *u2){
    	GLfloat r;
    	GLint returnValue=true;
    	if(p<0.0){
    		r=q/p;
    		if(r>*u2){
    			returnValue = false;
    		}else if(r>*u1){
    			*u1=r;
    		}
    	}else{
    		if(p>0.0){
    			r=q/p;
    			if(r<*u1){
    				returnValue=false;
    			}else if(r<*u2){
    				*u2=r;
    			}
    		}else{
    
    			if(q<0.0){
    				returnValue=false;
    			}
    		}
    	}
    	return (returnValue);
    }
    
    
    void lineClipLiangBrask(wcPt2D winMin, wcPt2D winMax, wcPt2D p1, wcPt2D p2){
    	GLfloat u1=0.0, u2=1.0, dx=p2.getx ()-p1.getx (),dy;
    	if(clipTest (-dx, p1.getx ()-winMin.getx (),&u1, &u2)){
    		if(clipTest (dx, winMax.getx ()-p1.getx (),&u1, &u2)){
    			dy=p2.gety ()-p1.gety ();
    			if(clipTest (-dy, p1.gety ()-winMin.gety (), &u1, &u2)){
    				if(clipTest (dy,winMax.gety ()-p1.gety (),&u1, &u2)){
    					if(u2<1.0){
    						p2.setCoords(p1.getx ()+u2*dx,p1.gety ()+u2*dy);
    					}
    					if(u1>0.0){
    						p1.setCoords(p1.getx ()+u1*dx, p1.gety ()+u1*dy);
    					}
    					lineDDA (round(p1.getx ()), round (p1.gety ()),round(p2.getx ()),round(p2.gety ()));
    				}
    			}
    		}
    	}
    
    	return ;
    }
    

    display:

    //	Liang-Barsky线段裁剪算法
    //初始直线
    glColor3f (0.0,0.0,1.0);
    lineBres (0,100,400,300);
    glFlush ();
    
    //可视化边界:
    glColor3f(1.0,0.0,0.0);
    lineBres (100,100,100,300);
    lineBres (100,100,300,100);
    lineBres (300,300,100,300);
    lineBres (300,300,300,100);
    
    
    glColor3f (0.0,1.0,0.0);
    lineClipLiangBrask (wcPt2D(100,100), wcPt2D(300, 300), wcPt2D(0,100),wcPt2D(400, 300));
    glFlush ();
    

    Liang-Barsky 多边形裁剪算法:

    //-----------------------------------------
    //Liang-Barsky 线段裁剪算法
    
    class wcPt2D {
    
    public:
    	GLfloat x,y;
    public:
    	/*
    Default Constructor:initalize position 48(0.0,0.0).*/
    	wcPt2D(){
    		x=y=0.0;
    	}
    
    	wcPt2D(GLfloat nx, GLfloat ny): x(nx), y(ny){}
    
    	wcPt2D(const wcPt2D& pCopy){
    		this->x=pCopy.x;
    		this->y=pCopy.y;
    	}
    
    	void setCoords(GLfloat xCoord,GLfloat yCoord){
    		x = xCoord;
    		y = yCoord;
    		return ;
    	}
    
    	wcPt2D& operator= (wcPt2D p2){
    		this->x=p2.getx ();
    		this->y=p2.gety ();
    		return *this;
    	}
    
    
    	GLfloat getx()const{
    		return x;
    	}
    	GLfloat gety ( ) const {
    		return y;
    	}
    };
    
    inline GLint round(const GLfloat a){
    	return GLint(a + 0.5);
    }
    
    GLint clipTest(GLfloat p, GLfloat q, GLfloat * u1, GLfloat *u2){
    	GLfloat r;
    	GLint returnValue=true;
    	if(p<0.0){
    		r=q/p;
    		if(r>*u2){
    			returnValue = false;
    		}else if(r>*u1){
    			*u1=r;
    		}
    	}else{
    		if(p>0.0){
    			r=q/p;
    			if(r<*u1){
    				returnValue=false;
    			}else if(r<*u2){
    				*u2=r;
    			}
    		}else{
    
    			if(q<0.0){
    				returnValue=false;
    			}
    		}
    	}
    	return (returnValue);
    }
    
    
    void lineClipLiangBrask(wcPt2D winMin, wcPt2D winMax, wcPt2D p1, wcPt2D p2){
    	GLfloat u1=0.0, u2=1.0, dx=p2.getx ()-p1.getx (),dy;
    	if(clipTest (-dx, p1.getx ()-winMin.getx (),&u1, &u2)){
    		if(clipTest (dx, winMax.getx ()-p1.getx (),&u1, &u2)){
    			dy=p2.gety ()-p1.gety ();
    			if(clipTest (-dy, p1.gety ()-winMin.gety (), &u1, &u2)){
    				if(clipTest (dy,winMax.gety ()-p1.gety (),&u1, &u2)){
    					if(u2<1.0){
    						p2.setCoords(p1.getx ()+u2*dx,p1.gety ()+u2*dy);
    					}
    					if(u1>0.0){
    						p1.setCoords(p1.getx ()+u1*dx, p1.gety ()+u1*dy);
    					}
    					lineDDA (round(p1.getx ()), round (p1.gety ()),round(p2.getx ()),round(p2.gety ()));
    					//					return 2;
    				}
    			}
    		}
    	}
    
    	return ;
    }
    
    int lineClipLiangBrask(wcPt2D winMin, wcPt2D winMax, wcPt2D p1, wcPt2D p2, wcPt2D pOut[]){
    	GLfloat u1=0.0, u2=1.0, dx=p2.getx ()-p1.getx (),dy;
    	if(clipTest (-dx, p1.getx ()-winMin.getx (),&u1, &u2)){
    		if(clipTest (dx, winMax.getx ()-p1.getx (),&u1, &u2)){
    			dy=p2.gety ()-p1.gety ();
    			if(clipTest (-dy, p1.gety ()-winMin.gety (), &u1, &u2)){
    				if(clipTest (dy,winMax.gety ()-p1.gety (),&u1, &u2)){
    					if(u2<1.0){
    						p2.setCoords(p1.getx ()+u2*dx,p1.gety ()+u2*dy);
    					}
    					if(u1>0.0){
    						p1.setCoords(p1.getx ()+u1*dx, p1.gety ()+u1*dy);
    					}
    					pOut[0]=p1;
    					pOut[1]=p2;
    //					lineDDA (round(p1.getx ()), round (p1.gety ()),round(p2.getx ()),round(p2.gety ()));
    					return 2;
    				}
    			}
    		}
    	}
    
    	return 0;
    }
    
    void display(){
    	glClear (GL_COLOR_BUFFER_BIT);
    	//可视化边界:
    	const int minX=100, minY=100, maxX=300, maxY=300;
    	glColor3f(1.0,0.0,0.0);
    	lineDDA (minX,minY,minX,maxY);
    	lineDDA (minX,minY,maxX,minY);
    	lineDDA (maxX,maxY,minX,maxY);
    	lineDDA (maxX,maxY,maxX,minY);
    
    	glColor3f(0.0,1.0,0.0);
    	GLint n=5;
    	wcPt2D pIn[n];
    	pIn[0].setCoords (0,200);
    	pIn[1].setCoords (150,250);
    	pIn[2].setCoords (250,250);
    	pIn[3].setCoords (400,200);
    	pIn[4].setCoords (200,50);
    
    	for(int i=0;i<n;++i){
    		lineDDA (pIn[i].x,pIn[i].y,pIn[(i+1)%n].x,pIn[(i+1)%n].y);
    	}
    
    
    	wcPt2D pOut[20];
    	wcPt2D tempPOut[2];
    	int outCount=0;
    	int flag=0;
    	for(int i=0;i<n;++i){
    		flag=lineClipLiangBrask (wcPt2D(minX,minY), wcPt2D(maxX, maxY), pIn[i],pIn[(i+1)%n],tempPOut);
    		if(flag==2){
    			for(int j=0;j<2;++j){
    				pOut[outCount++]=tempPOut[j];
    			}
    		}
    	}
    
    	glColor3f(0.0,0.0,1.0);
    	int i=1;
    	for(;i<=outCount;++i){
    		lineDDA (pOut[i-1].x,pOut[i-1].y,pOut[i%outCount].x,pOut[i%outCount].y);
    	}
    
    	glFlush ();
    
    
    	return ;
    }
    

    效果:

    image-20201009120216266

    Sutherland-Hodgman多边形裁剪算法

    #define NDEBUG
    #ifndef GLUT_DISABLE_ATEXIT_HACK
    #define GLUT_DISABLE_ATEXIT_HACK
    #endif
    #include <windows.h>
    #include <gl/glut.h>
    #include <math.h>
    #include <stdio.h>
    
    const int windowWidge=600, windowHeight=600;
    
    
    void setPixel(GLint xCoord, GLint yCoord){
    	glBegin (GL_POINTS);
    	glVertex2i (xCoord, yCoord);
    	glEnd();
    }
    
    
    //-----------------------------------------
    
    void lineDDA (int x0, int y0, int xEnd, int yEnd){
    	int dx=xEnd-x0,dy=yEnd-y0,steps,k;
    	float xIncrement,yIncrement,x=x0,y=y0;
    	if(fabs(dx)> fabs(dy)){
    		steps = fabs(dx);
    	}else {
    		steps = fabs(dy);
    	}
    	xIncrement = float(dx)/float(steps);
    	yIncrement = float(dy)/ float(steps);
    	setPixel(round(x),round(y));
    	for(k = 0;k< steps;k++){
    		x += xIncrement;
    		y += yIncrement;
    		setPixel(round(x),round(y));
    	}
    	return ;
    }
    
    
    
    //---------------------------------------------
    //Sutherland-Hodgman多边形裁剪算法
    
    class wcPt2D {
    
    public:
    	GLfloat x,y;
    public:
    	/*
    Default Constructor:initalize position 48(0.0,0.0).*/
    	wcPt2D(){
    		x=y=0.0;
    	}
    
    	wcPt2D(GLfloat nx, GLfloat ny): x(nx), y(ny){}
    
    	wcPt2D(const wcPt2D& pCopy){
    		this->x=pCopy.x;
    		this->y=pCopy.y;
    	}
    
    	void setCoords(GLfloat xCoord,GLfloat yCoord){
    		x = xCoord;
    		y = yCoord;
    		return ;
    	}
    
    	wcPt2D& operator= (wcPt2D p2){
    		this->x=p2.getx ();
    		this->y=p2.gety ();
    		return *this;
    	}
    
    
    	GLfloat getx()const{
    		return x;
    	}
    	GLfloat gety ( ) const {
    		return y;
    	}
    };
    
    
    //枚举类的替代, C++中enum的操作与C有很大不同
    const int Left=0, Right=1, Bottom=2, Top=3;
    
    //typedef enum{
    //	Left, Right, Bottom, Top
    //} Boundary;
    
    using namespace std;
    
    const GLint nClip = 4;
    
    
    //判断点p是否在显示框内
    GLint inside(wcPt2D p, int b, wcPt2D wMin, wcPt2D wMax){
    	int flag=true;
    	switch(b){
    		case Left:{
    			if(p.getx ()<wMin.getx ()){
    				flag=false;
    			}
    			break;
    		}
    		case Right:{
    			if(p.getx ()>wMax.getx ()){
    				flag=false;
    			}
    			break;
    		}
    		case Bottom:{
    			if(p.gety ()<wMin.gety ()){
    				flag=false;
    			}
    			break;
    		}
    		case Top:{
    			if(p.gety ()>wMax.gety ()){
    				flag=false;
    			}
    			break;
    		}
    	}
    	return flag;
    }
    
    //判断向量(p1, p2)是否与边界相交
    GLint cross(wcPt2D p1, wcPt2D p2, int winEdge, wcPt2D wMin, wcPt2D wMax){
    	if(inside (p1,winEdge,wMin,wMax)==inside (p2, winEdge, wMin, wMax)){
    		return false;
    	}else{
    		return true;
    	}
    }
    
    //返回向量(p1, p2)与相应边界的交点
    wcPt2D intersect(wcPt2D p1, wcPt2D p2, int winEdge, wcPt2D wMin, wcPt2D wMax){
    	wcPt2D iPt;
    	GLfloat m;
    
    	if(p1.x!= p2.x){
    		m=(p1.gety ()-p2.gety ())/(p1.getx ()-p2.getx ());
    	}
    	switch (winEdge) {
    		case Left:{
    			iPt.x=wMin.x;
    			iPt.y=p2.y+(wMin.x-p2.x)*m;
    			break;
    		}
    		case Right:{
    			iPt.x=wMax.x;
    			iPt.y=p2.y+(wMax.x-p2.x)*m;
    			break;
    		}
    		case Bottom:{
    			iPt.y=wMin.y;
    			if(p1.x!=p2.x){
    				iPt.x=p2.x+(wMin.y-p2.y)/m;
    			}else{
    				iPt.x=p2.x;
    			}
    			break;
    		}
    		case Top:{
    			iPt.y=wMax.y;
    			if(p1.x!=p2.x){
    				iPt.x=p2.x+(wMax.y-p2.y)/m;
    			}else{
    				iPt.x=p2.x;
    			}
    			break;
    		}
    	}
    	return iPt;
    }
    
    void clipPoint(wcPt2D &p, int winEdge, wcPt2D wMin, wcPt2D wMax, wcPt2D * pOut,
    			   int *cnt, wcPt2D first[], wcPt2D *s){
    	wcPt2D iPt;
    
    	//判断first[winEdge]为nullPtr
    	if(first[winEdge].x==0 && first[winEdge].y==0){
    		first[winEdge]=p;
    	}else{
    		if(cross(p,s[winEdge], winEdge, wMin, wMax)){
    			iPt=intersect (p, s[winEdge], winEdge, wMin, wMax);
    			if(winEdge<Top){
    				clipPoint (iPt, winEdge+1, wMin, wMax, pOut, cnt, first, s);
    			}else{
    				//存交点
    				pOut[*cnt] =iPt;
    				(*cnt)++;
    			}
    		}
    	}
    	s[winEdge]=p;
    	if(inside (p,winEdge, wMin, wMax)){
    		if(winEdge<Top){
    			clipPoint (p, winEdge+1, wMin, wMax, pOut, cnt, first, s);
    		}else{
    			pOut[*cnt]=p;
    			(*cnt)++;
    		}
    	}
    }
    
    void closeClip(wcPt2D wMin, wcPt2D wMax, wcPt2D *pOut, GLint *cnt,
    			   wcPt2D first[],wcPt2D *s){
    	wcPt2D pt;
    	int winEdge;
    	for(winEdge=Left; winEdge<=Top;winEdge++){
    		if(cross(s[winEdge],first[winEdge],winEdge, wMin, wMax)){
    			pt=intersect (s[winEdge], first[winEdge], winEdge, wMin, wMax);
    			if(winEdge<Top){
    				clipPoint (pt, winEdge+1, wMin, wMax, pOut, cnt, first, s);
    			}else{
    				pOut[*cnt]=pt;
    				(*cnt)++;
    			}
    		}
    	}
    }
    
    GLint polygonClipSuthHodg(wcPt2D wMin, wcPt2D wMax, GLint n, wcPt2D *pIn, wcPt2D *pOut){
    	wcPt2D first[nClip] , s[nClip];
    	GLint k, cnt=0;
    	for(k=0;k<n;k++){
    		clipPoint (pIn[k],Left, wMin, wMax, pOut, &cnt, first, s);
    	}
    	closeClip (wMin, wMax, pOut, &cnt, first, s);
    	return cnt;
    }
    
    
    //---------------------------------------------
    
    
    //绘制程序
    void display(){
    
    	//Sutherland-Hodgman多边形裁剪算法
    	glClear (GL_COLOR_BUFFER_BIT);
    	//可视化边界:
    	const int minX=100, minY=100, maxX=300, maxY=300;
    	glColor3f(1.0,0.0,0.0);
    	lineDDA (minX,minY,minX,maxY);
    	lineDDA (minX,minY,maxX,minY);
    	lineDDA (maxX,maxY,minX,maxY);
    	lineDDA (maxX,maxY,maxX,minY);
    
    	//定义多边形的颜色和顶点
    	glColor3f(0.0,1.0,0.0);
    	GLint n=6;
    	wcPt2D pIn[n];
    	pIn[0].setCoords (50,200);
    	pIn[1].setCoords (150,250);
    	pIn[2].setCoords (250,250);
    	pIn[3].setCoords (350,200);
    	pIn[4].setCoords (250,50);
    	pIn[5].setCoords (150,50);
    	//绘制原始多边形
    	for(int i=0;i<n;++i){
    		lineDDA (pIn[i].x,pIn[i].y,pIn[(i+1)%n].x,pIn[(i+1)%n].y);
    	}
    
    	//获取裁剪后的点集
    	wcPt2D pOut[20];
    	int count=polygonClipSuthHodg (wcPt2D(minX,minY),wcPt2D(maxX,maxY),n,pIn,pOut);
    
    	//定义裁剪后的多边形颜色
    	glColor3f(0.0,0.0,1.0);
    	//绘制裁剪后的多边形
    	for(int i=1;i<=count;++i){
    		lineDDA (pOut[i-1].x,pOut[i-1].y,pOut[i%count].x,pOut[i%count].y);
    	}
    
    	glFlush ();
    
    
    	return ;
    }
    
    //初始化绘制
    void init(){
    	glClearColor(1.0,1.0,1.0,0.0);//清除颜色设置
    	glMatrixMode(GL_PROJECTION);//设置投影方式
    	gluOrtho2D (0.0,windowWidge*1.0,0.0,windowHeight*1.0);
    	return ;
    }
    
    int main(int argc, char** argv){
    	glutInit(&argc, argv);//初始化glut
    	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式为单缓冲,RGB模式
    	glutInitWindowPosition(0,0);//设置窗口位置
    	glutInitWindowSize(windowWidge,windowHeight);//设置窗口大小
    	glutCreateWindow("lineClipLiangBrask");//设置窗口标题
    	init();
    	glutDisplayFunc(display);
    	glutMainLoop();
    	return 0;
    }
    
    

    效果:

    image-20201009153730699

    展开全文
  • 基于MFC的计算机图形学中点裁剪算法多边形裁剪算法
  • sutherland-hodgman 多边形裁剪算法

    千次阅读 2022-01-06 13:45:40
    所谓多边形裁剪,就是在二维平面上有一堆多边,和一个矩形窗口。求出现在窗口里的部分是哪些。 蓝线为窗口 裁剪后如下 在这里我们规定矩形的边是平行于x轴和y轴的。 算法思想 一个多边形可以使用一个点序列表示,...

    欢迎关注更多精彩
    关注我,学习常用算法与数据结构,一题多解,降维打击。

    多边形剪裁作用

    所谓多边形裁剪,就是在二维平面上有一堆多边,和一个矩形窗口。求出现在窗口里的部分是哪些。


    蓝线为窗口

    裁剪后如下


    在这里我们规定矩形的边是平行于x轴和y轴的。

    算法思想

    一个多边形可以使用一个点序列表示,每两个连续的点可以组成一条多边形的边。可以对边进行裁剪,最终得到裁剪后多边形的点序列。

    对裁剪窗口的一个边来说,有以上4种情况。
    具体实现总结为2句话:

    1. 有交点加交点。
    2. 末端点在窗口内,加入到队列中。
      总体过程如下:

      具体实现的时候

    算法实现

    #include "glew/2.2.0_1/include/GL/glew.h"
    #include "glfw/3.3.4/include/GLFW/glfw3.h"
    #include <iostream>
    #include "model.h"
    #include <cmath>
    
    using namespace std;
    
    class wcPt2D {
    public:
        double x, y;
    
        wcPt2D() {}
    
        wcPt2D(double a, double b) : x(a), y(b) {}
    
        void out() {
            printf("%.2f, %.2f\n", x, y);
        }
    };
    
    typedef enum {
        Left = 0, Right = 1, Bottom = 2, Top = 3
    } Boundary;
    
    GLint inside(wcPt2D p, Boundary b, wcPt2D wMin, wcPt2D wMax) {
        switch (b) {
            case Left:
                if (p.x < wMin.x) return false;
                break;
            case Right:
                if (p.x > wMax.x) return false;
                break;
            case Bottom:
                if (p.y < wMin.y) return false;
                break;
            case Top:
                if (p.y > wMax.y) return false;
                break;
        }
        return true;
    }
    
    GLint cross(wcPt2D p1, wcPt2D p2, Boundary winEdge, wcPt2D wMin, wcPt2D wMax) {
        auto b1 = inside(p1, winEdge, wMin, wMax);
        auto b2 = inside(p2, winEdge, wMin, wMax);
        return b1!=b2;
    }
    
    wcPt2D intersect(wcPt2D p1, wcPt2D p2, Boundary winEdge, wcPt2D wMin, wcPt2D wMax) {
        wcPt2D iPt;
        GLfloat m;
    
        if (p1.x != p2.x) m = (p1.y - p2.y) / (p1.x - p2.x);
    
        switch (winEdge) {
            case Left:
                iPt.x = wMin.x;
                iPt.y = p2.y + (wMin.x - p2.x) * m;
                break;
            case Right:
                iPt.x = wMax.x;
                iPt.y = p2.y + (wMax.x - p2.x) * m;
                break;
            case Bottom:
                iPt.y = wMin.y;
                if (p1.x != p2.x) iPt.x = p2.x + (wMin.y - p2.y) / m;
                else iPt.x = p2.x;
                break;
            case Top:
                iPt.y = wMax.y;
                if (p1.x != p2.x) iPt.x = p2.x + (wMax.y - p2.y) / m;
                else iPt.x = p2.x;
                break;
        }
    
        return iPt;
    }
    
    
    vector<wcPt2D> clipBoundary(vector<wcPt2D> &pIn, Boundary b, wcPt2D wMin, wcPt2D wMax) {
        vector<wcPt2D> ans;
    
        for(int i=0;i<pIn.size();i++) {
            auto p1 = pIn[i];
            auto p2 = pIn[(i+1)%pIn.size()];
    		// 有交点,加上
            if (cross(p1, p2, b, wMin, wMax)) {
               auto pt = intersect(p1, p2, b, wMin, wMax);
               ans.push_back(pt);
            }
    		// 末端点在窗口内,加上
            if(inside(p2, b, wMin, wMax)) ans.push_back(p2);
        }
    
        return ans;
    }
    
    vector<wcPt2D> polygonClipSutherlandHodgman(wcPt2D wMin, wcPt2D wMax, vector<wcPt2D> pIn) {
        for(Boundary b = Left; b<=Top; b=Boundary(b+1)) {
            pIn = clipBoundary(pIn, b, wMin, wMax);
        }
    
        return pIn;
    }
    
    
    
    void key_callback(GLFWwindow *window, int key, int scancode, int action, int mode) {
        //如果按下ESC,把windowShouldClose设置为True,外面的循环会关闭应用
        if (key == GLFW_KEY_ESCAPE && action == GLFW_PRESS) {
            glfwSetWindowShouldClose(window, GL_TRUE);
            std::cout << "ESC" << mode;
        }
    
        if (action != GLFW_PRESS)return;
        switch (key) {
            case GLFW_KEY_ESCAPE:
                glfwSetWindowShouldClose(window, GL_TRUE);
                break;
            default:
                break;
        }
    
    }
    
    void mouse_click(GLFWwindow *window, int button, int action, int mods) {
        cout << button << "," << action << "," << mods << endl;
        double xpos, ypos;
        glfwGetCursorPos(window, &xpos, &ypos);
        cout << xpos / 300 - 1 << "," << 1 - ypos / 300 << endl;
        cout << xpos << "," << ypos << endl;
    }
    
    int main(void) {
        //初始化GLFW库
        if (!glfwInit())
            return -1;
        //创建窗口以及上下文
        GLFWwindow *window = glfwCreateWindow(600, 600, "hello world", NULL, NULL);
        if (!window) {
            //创建失败会返回NULL
            glfwTerminate();
        }
    
        //建立当前窗口的上下文
        glfwMakeContextCurrent(window);
    
        glfwSetKeyCallback(window, key_callback); //注册回调函数
        glfwSetMouseButtonCallback(window, mouse_click);
        //glViewport(0, 0, 400, 400);
        gluOrtho2D(-300, 300.0, -300, 300.0);
        //循环,直到用户关闭窗口
        cout << 123 << endl;
        int n = 4;
        wcPt2D pIn[10] = {
                {-100, 0},
                {0,    -100},
                {100,  0},
                {0,    100},
        };
    
        wcPt2D wMin = {-150, -150};
        wcPt2D wMax = {150, 150};
    
        auto pOut = polygonClipSutherlandHodgman({-75, -75}, {75,75}, vector<wcPt2D>(pIn, pIn+n));
        cout << pOut.size() << endl;
        for (auto p : pOut) {
            p.out();
        }
    
        vector<wcPt2D> pIn1 = {
                {-75, 175},
                {-160,    10},
                {20,  -20},
        };
        auto pOut1 = polygonClipSutherlandHodgman(wMin,wMax, pIn1);
    
    
    
        vector<wcPt2D> pIn2 = {
                {-160, 10},
                {-155,    -50},
                {-140,  -100},
                {-70,  -150},
                {0,  -200},
                {80,  -160},
                {160,  160},
        };
        auto pOut2 = polygonClipSutherlandHodgman(wMin,wMax, pIn2);
    
    
    
    
    
        while (!glfwWindowShouldClose(window)) {
            /*******轮询事件*******/
            glfwPollEvents();
            // cout<<456<<endl;
            //选择清空的颜色RGBA
    
            glEnable(GL_DEPTH_TEST);
            glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
            glColor3f(0.2, 0.5, 0.8);
    
    /*
            glBegin(GL_LINE_STRIP);
            glVertex2d(-90, -80);
            glVertex2d(90, -80);
            glVertex2d(90, 80);
            glVertex2d(-90, 80);
            glVertex2d(-90, -80);
            glEnd();
            */
    
            glBegin(GL_LINE_STRIP);
            glVertex2d(-150, -150);
            glVertex2d(150, -150);
            glVertex2d(150, 150);
            glVertex2d(-150, 150);
            glVertex2d(-150, -150);
            glEnd();
    
    
    
    /*
    
            glColor3f(1, 0.5, 0.8);
            glBegin(GL_POLYGON);
            for (auto p : pIn2) {
                glVertex2d(p.x, p.y);
            }
            glEnd();
            */
    
            glColor3f(1, 0,0);
            glBegin(GL_POLYGON);
            for (auto p : pOut2) {
                glVertex2d(p.x, p.y);
            }
    
            glEnd();
    
            // glFlush();
            glfwSwapBuffers(window);
        }
        glfwTerminate();
        return 0;
    }
    
    

    算法效果

    示例1


    示例2


    示例3



    本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

    展开全文
  • 文章目录说明Sutherland-Hodgeman代码 ...算法较为简单,直接看课本就可以。 代码 /* * 项目名称:Sutherland-Hodgeman * 注意:polyPoint中存储的是多边形的所有顶点,每个顶点仅仅存一次 * 问题:processInp
  • 提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对...
  • 经典多边形裁剪算法 Sutherland-Hodgman的VC++实现 经典多边形裁剪算法 Sutherland-Hodgman的VC++实现
  • 文章目录前言改进前(SutherlandHodgmanClip 多边形裁剪算法)1.新建结构体:点,线,裁剪窗口2.用于画点和画裁剪窗口的函数3.创建裁剪窗口的四条边4.判断点的位置5.求直线与边界的交点6.SutherlandHodgmanClip ...
  • 传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(NlogN)~O(N 2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形...
  • openGL-多边形裁剪算法

    千次阅读 2018-03-24 14:58:04
    考虑使用4把刀分别裁剪一个图形。核心思想是,有一个点在扫描整个图形的边界。在扫描过程中,如果从刀的内侧(需要自己定义)到刀的外侧那么就记录当前点p0,当再次从外侧进入内测时,将当前点和记录的p0连起来。...
  • 提出了一种适合任意多边形裁剪算法,该算法将构成结果多边形的裁剪多边形和实体多边形顶点插入到两者的交点链表中,通过交点位置的排序,形成一个单线性、单指针结构的结果多边形顶点链表.简化了交点的数据结构,...
  • 逐次多边形裁剪算法算法的思想发窗口四条边界单一逐次对多边形进行裁剪,每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪,裁剪时,顺序地测试多边形各顶点,保留边界内侧的顶点,删除外侧的顶点,同时,...
  • } } } /* 裁剪函数 */ void clipFunc(point * clipP, int cc, point * polygonP, int pc, point *& output, int *& oc){ int i, j; edge * cedges = new edge[cc]; point * input = new point[pc]; //构造边 for(i ...
  • 用矩形来裁剪任意多边形,暂时没有考虑交点是多边形或矩形顶点的情况。
  • 在 pycharm 加 pyqt5环境中开发,python实现Sutherland-Hodge 逐次裁剪法(多边形裁剪)。 有优美的 UI界面
  • //定义两个临时数组,用于每次裁剪后新生成的多边形顶点 UINT m_nA, m_nB; int x, y; long tem1, tem2; int i; //原始多边形顶点个数 //原始多边形顶点数组的第一个顶点和最后一个顶点相同,因此实际顶点个数...
  • 裁剪是计算机图形学中许多重要问题的基础,本文总结了多种多边形裁剪算法并加以评述。
  • 多边形裁剪算法PPT学习教案.pptx
  • 1、编写程序实现Sutherland-Hodgeman 多边形裁剪算法。 #include<GL/glut.h> #include<iostream> #include<stdio.h> #include<stdlib.h> typedef struct { float x, y; }wcPt2D; typedef...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,067
精华内容 1,626
关键字:

多边形裁剪算法