sutherland-hodgman 多边形裁剪算法

本文主要是介绍sutherland-hodgman 多边形裁剪算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

多边形剪裁作用

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

蓝线为窗口

裁剪后如下

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

算法思想

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

对裁剪窗口的一个边来说，有以上4种情况。
具体实现总结为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) {//创建失败会返回NULLglfwTerminate();}//建立当前窗口的上下文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;//选择清空的颜色RGBAglEnable(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;
}