线段求交应用之CohenSutherland裁剪算法

线段求交应用之CohenSutherland裁剪算法

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

线段剪裁作用

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

上图中绿色为线段，红色为窗口。

剪裁后效果如下。

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

朴素思想及优化

朴素做法就是对于某一条段，用4个边界分别与线段求交。再判断交点的关系，决定哪段在剪裁窗口内。这种方法计算量大，情况也非常复杂。

优化

CohenSutherland算法就是利用窗口的特性，先对线段端点进行编码。
利用编码可以快速判断线段与窗口之间的关系，可以大量减少线段求交的运算。

该算法用一个4位的数字来编码一个端点。
从0到3分别表示是否超过边界，分别是左，右，下，上。
如图，中间0000区域是窗口有效区域。
L1 两端编码都 0，所以可以判断都在界内，直接全部留下。
L3 2点编码都在某一条边的外边，code1&code2>0，所以全部放弃。
L2 需要求交后再判断。
分别与左右上下进行判断并求交，判断可以利用code & (1<0, k 编号与上面表格中一样。
求交时，可以利用边界平行于x轴，y轴特性。
线段求交点击前往

实现

#include "glew/2.2.0_1/include/GL/glew.h"
#include "glfw/3.3.4/include/GLFW/glfw3.h"
#include 
using namespace std;


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"<0) step = (p2.x-p1.x) / deltaX;
    setPixel(p1);
    for (; p1.y < p2.y;) {
        p1.y++;
        if(p0<0) {
            p0+=twDeltaX;
        } else {
            p0+=twDeltaXmTwoDeltaY;
            p1.x+=step;
        }
        setPixel(p1);
        // cout<0) step = (p2.y-p1.y) / deltaY;
    setPixel(p1);
    for (; p1.x < p2.x;) {
        p1.x++;
        if(p0<0) {
            p0+=twDeltaY;
        } else {
            p0+=twDeltaYmTwoDeltaX;
            p1.y+=step;
        }
        setPixel(p1);
        // cout<xWmax) code |= codeRight;
    if(p.yyWmax) code |= codeUp;

    return code;
}

bool inside(int code) {
    return !code;
}

bool reject(int code1, int code2) {
    return code1&code2;
}

bool accept(int code1, int code2) {
    return !(code1|code2);
}

void swap(Point &p1, Point &p2) {
    int a;
    a = p1.x;
    p1.x=p2.x;
    p2.x=a;

    a = p1.y;
    p1.y=p2.y;
    p2.y=a;
}

void CohenSutherLand(Point p1, Point p2) {
    bool done = false;
    int code1, code2;
    double k;
    while(!done) {
        code1 = genCode(p1);
        code2 = genCode(p2);

        if (accept(code1, code2)) {
            done = true;
            break;
        }

        if (reject(code1, code2)) {
            return;
        }

        // 点已经在框内不需要剪裁
        if(inside(code1)) {
            swap(p1, p2);
            continue;
        }

        if(doubleCmp(p1.x, p2.x)) k = (p1.y-p2.y)/(p1.x-p2.x);

        // 查看左边
        if(code1&codeLeft) {
            p1.y+=(xWmin - p1.x)*k;
            p1.x= xWmin;
            continue;
        }

        // 查看左边
        if (code1&codeRight){
            p1.y+=(xWmax - p1.x)*k;
            p1.x= xWmax;
            continue;
        }

        // 查看下方
        if(code1&codeDown){
            if(doubleCmp(p1.x, p2.x)) p1.x += (yWmin - p1.y)/k;
            p1.y = yWmin;
            continue;
        }

        // 查看上方
        if(code1&codeUp){
            if(doubleCmp(p1.x, p2.x)) p1.x += (yWmax - p1.y)/k;
            p1.y = yWmax;
            continue;
        }
    }

    LineBres_1(p1, p2);
}

int main(void) {
    //初始化GLFW库
    if (!glfwInit())
        return -1;
    //创建窗口以及上下文
    GLFWwindow *window = glfwCreateWindow(400, 400, "hello world", NULL, NULL);
    if (!window) {
        //创建失败会返回NULL
        glfwTerminate();
    }

    //建立当前窗口的上下文
    glfwMakeContextCurrent(window);

    glfwSetKeyCallback(window, key_callback); //注册回调函数
    //glViewport(0, 0, 400, 400);
    gluOrtho2D(-200, 200.0, -200, 200.0);
    //循环，直到用户关闭窗口
    cout<<123< 
算法效果 
剪裁前效果 
 
剪裁后效果 
 
 
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5636471.html