备案控制台
开发者社区 人工智能 文章 正文

多边形裁剪算法

2024-05-24 29
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 多边形裁剪算法

1.先决定窗口范围：

initgraph(800, 600);
  line(200, 450, 200, 200);
  line(200, 200, 600, 200);
  line(600, 200, 600, 450);
  line(600, 450, 200, 450);//框


b9d744382fa844e3990a7720311e211f.jpg


2.进行鼠标操作：鼠标左键按下：画点；鼠标右键按下：连线；鼠标中键按下：与初始点相连接，完成多边形的绘制。

void shubiao() {
  int a[3] = { 0 }, b[3] = { 0 };
  int count = 0;
  int a1 = 0, b1 = 0;//初始点
  int flag = 0;
  cout << "鼠标左键按下：画点\n鼠标右键按下：连线\n鼠标中键按下：与初始点相连接，完成多边形的绘制\n" << endl;
  while (flag==0) {
    if (MouseHit())//判断是否有鼠标信息
    {
      settextcolor(RED);//默认为红色
      MOUSEMSG msg;  //定义一个鼠标消息
      msg = GetMouseMsg();//获取鼠标消息
      switch (msg.uMsg)
      {
      case  WM_LBUTTONDOWN:
      {
        putpixel(msg.x, msg.y, RED);//画点
        xx[count] = msg.x;
        yy[count] = msg.y;
        a[count % 2] = msg.x;
        b[count % 2] = msg.y;
        if (count == 0) {
          a1 = msg.x;
          b1 = msg.y;
        }
        count++;
 
        Vertex p(msg.x, msg.y);
        input_vertice.push_back(p);
 
        break;
      }// 左键按下消息 画点
      case  WM_RBUTTONDOWN:
      {
        setlinecolor(RED);
        line(a[0], b[0], a[1], b[1]);
        break;
      }// 右键按下消息 连线
      case   WM_MBUTTONDOWN:
      {
        setlinecolor(RED);
        line(a[(count - 1) % 2], b[(count - 1) % 2], a1, b1);
        cout << "已完成多边形的绘制" << endl;
        flag = 1;
        break;
      }// 中键按下消息 完成绘图
      }
    }
  }
}


f2ec4ad5e1494ef2bc2d315920b4f87a.jpg

最后与初始点连接时不要按右键，要按中键。

3.进行多边形裁剪：这里使用Sutherland-Hodgman算法。主要是Inside（判断点是否在裁剪边的可见侧），Intersect（直线段与窗口求交，返回交点），SutherlandHodgmanClip函数。

 
bool Inside(Vertex& testPT, EDGE ClipBoundary)
{//判断点是否在裁剪边的可见侧
  if (ClipBoundary.bx > ClipBoundary.ax)
  {
    if (testPT.y >= ClipBoundary.ay)//裁剪边为窗口下边
      return true;
  }
  else if (ClipBoundary.bx < ClipBoundary.ax)
  {
    if (testPT.y <= ClipBoundary.ay)//裁剪边在窗口上边
      return true;
  }
  else if (ClipBoundary.by > ClipBoundary.ay)//裁剪边在窗口右边
  {
    if (testPT.x <= ClipBoundary.ax)
      return true;
  }
  else if (ClipBoundary.by < ClipBoundary.ay)//裁剪边在窗口左边
  {
    if (testPT.x >= ClipBoundary.ax)
      return true;
  }
  return false;
}
 
void Intersect(Vertex& S, Vertex& P, EDGE ClipBoundary, Vertex& IntersectPt)
{
  if (ClipBoundary.ay == ClipBoundary.by)//水平裁剪
  {
    IntersectPt.y = ClipBoundary.ay;
    IntersectPt.x = S.x + (ClipBoundary.ay - S.y) * (P.x - S.x) / (P.y - S.y);
  }
  else//垂直裁剪
  {
    IntersectPt.x = ClipBoundary.ax;
    IntersectPt.y = S.y + (ClipBoundary.ax - S.x) * (P.y - S.y) / (P.x - S.x);
  }
}
 
 
 
void SutherlandHodgmanClip(EDGE ClipBoundary)
{
  Vertex S, P, ip;
  output_vertice.clear();
  S = input_vertice[input_vertice.size() - 1];//先从最后一个点指向第一个点的线段开始检验
 
  for (int j = 0; j < input_vertice.size(); j++)
  {
    P = input_vertice[j];
    if (Inside(P, ClipBoundary))//P在里面
    {
      if (Inside(S, ClipBoundary))//SP都在窗口内
      {
        output_vertice.push_back(P);
      }
      else//P在里面 S在外面
      {
        Intersect(S, P, ClipBoundary, ip);
        output_vertice.push_back(ip);
        output_vertice.push_back(P);
      }
    }
    else//P在外面
    {
      if (Inside(S, ClipBoundary))//S在窗口内P在窗口外
      {
        Intersect(S, P, ClipBoundary, ip);
        output_vertice.push_back(ip);
      }
      //SP都在外面则无输出
    }
    S = P;
  }
  input_vertice = output_vertice;//这次的输出作为下一次的输入
}


4.键盘或鼠标响应裁剪命令。这里我使用“w”键。

void  keyboard() {
  cout << "按w开始裁剪..." << endl;
  //settextcolor(BLUE);//填充蓝色
  int key = _getch();
  switch (key)
  {
    //w键
  case 72:
  case'w':
  case'W':
    SutherlandHodgmanClip(::left);
    SutherlandHodgmanClip(bottom);
    SutherlandHodgmanClip(::right);
    SutherlandHodgmanClip(top);
    for (int i = 0; i < output_vertice.size() - 1; i++)
    {
      putpixel(output_vertice[i].x, output_vertice[i].y, RED);
      line(output_vertice[i].x, output_vertice[i].y, output_vertice[i + 1].x, output_vertice[i + 1].y);
    }
    line(output_vertice[output_vertice.size() - 1].x, output_vertice[output_vertice.size() - 1].y, output_vertice[0].x, output_vertice[0].y);
    break;
 
      default:cout << "输入有误！" << endl;
  }
}


5.主函数：

int main() {
  initgraph(800, 600);
  line(200, 450, 200, 200);
  line(200, 200, 600, 200);
  line(600, 200, 600, 450);
  line(600, 450, 200, 450);//框
  //多边形裁剪
  shubiao();
  setlinestyle(PS_SOLID, 5);
  keyboard();
 
 
  system("pause");
  closegraph();
  return 0;
}


6.最后结果：

e5be45783cca4aa5849fab62a7c93f95.jpg

7.最终代码：

#include <graphics.h>
#include <vector>
#include <algorithm>
#include<iostream>
#include<conio.h> 
using namespace std;
const int maxn = 50;
const int window_width = 800, window_height = 600;
int xx[maxn] = { 0 }, yy[maxn] = { 0 };//存各点坐标
 
struct Vertex {
  float x;
  float y;
  Vertex() {}
  Vertex(float xx, float yy)
    :x(xx), y(yy) {}
  bool operator < (const Vertex& a)const //重载运算符
  {
    return x < a.x;
  }
};
typedef Vertex edge[2];
typedef Vertex vertexArray[maxn];
 
struct EDGE//Edge边
{
  float ax, ay, bx, by;
  EDGE() {}
  EDGE(float bxx, float byy, float exx, float eyy)
    :ax(bxx), ay(byy), bx(exx), by(eyy) {}
};
 
vector<Vertex> input_vertice; //输入
vector<Vertex> output_vertice; //输出
 
EDGE left(200, 450, 200, 200);
EDGE bottom(200, 200, 600, 200);
EDGE right(600, 200, 600, 450);
EDGE top(600, 450, 200, 450);
 
 
bool Inside(Vertex& testPT, EDGE ClipBoundary)
{//判断点是否在裁剪边的可见侧
  if (ClipBoundary.bx > ClipBoundary.ax)
  {
    if (testPT.y >= ClipBoundary.ay)//裁剪边为窗口下边
      return true;
  }
  else if (ClipBoundary.bx < ClipBoundary.ax)
  {
    if (testPT.y <= ClipBoundary.ay)//裁剪边在窗口上边
      return true;
  }
  else if (ClipBoundary.by > ClipBoundary.ay)//裁剪边在窗口右边
  {
    if (testPT.x <= ClipBoundary.ax)
      return true;
  }
  else if (ClipBoundary.by < ClipBoundary.ay)//裁剪边在窗口左边
  {
    if (testPT.x >= ClipBoundary.ax)
      return true;
  }
  return false;
}
 
void Intersect(Vertex& S, Vertex& P, EDGE ClipBoundary, Vertex& IntersectPt)
{
  if (ClipBoundary.ay == ClipBoundary.by)//水平裁剪
  {
    IntersectPt.y = ClipBoundary.ay;
    IntersectPt.x = S.x + (ClipBoundary.ay - S.y) * (P.x - S.x) / (P.y - S.y);
  }
  else//垂直裁剪
  {
    IntersectPt.x = ClipBoundary.ax;
    IntersectPt.y = S.y + (ClipBoundary.ax - S.x) * (P.y - S.y) / (P.x - S.x);
  }
}
 
 
 
void SutherlandHodgmanClip(EDGE ClipBoundary)
{
  Vertex S, P, ip;
  output_vertice.clear();
  S = input_vertice[input_vertice.size() - 1];//先从最后一个点指向第一个点的线段开始检验
 
  for (int j = 0; j < input_vertice.size(); j++)
  {
    P = input_vertice[j];
    if (Inside(P, ClipBoundary))//P在里面
    {
      if (Inside(S, ClipBoundary))//SP都在窗口内
      {
        output_vertice.push_back(P);
      }
      else//P在里面 S在外面
      {
        Intersect(S, P, ClipBoundary, ip);
        output_vertice.push_back(ip);
        output_vertice.push_back(P);
      }
    }
    else//P在外面
    {
      if (Inside(S, ClipBoundary))//S在窗口内P在窗口外
      {
        Intersect(S, P, ClipBoundary, ip);
        output_vertice.push_back(ip);
      }
      //SP都在外面则无输出
    }
    S = P;
  }
  input_vertice = output_vertice;//这次的输出作为下一次的输入
}
 
 
void shubiao() {
  int a[3] = { 0 }, b[3] = { 0 };
  int count = 0;
  int a1 = 0, b1 = 0;//初始点
  int flag = 0;
  cout << "鼠标左键按下：画点\n鼠标右键按下：连线\n鼠标中键按下：与初始点相连接，完成多边形的绘制\n" << endl;
  while (flag == 0) {
    if (MouseHit())//判断是否有鼠标信息
    {
      settextcolor(RED);//默认为红色
      MOUSEMSG msg;  //定义一个鼠标消息
      msg = GetMouseMsg();//获取鼠标消息
      switch (msg.uMsg)
      {
      case  WM_LBUTTONDOWN:
      {
        putpixel(msg.x, msg.y, RED);//画点
        xx[count] = msg.x;
        yy[count] = msg.y;
        a[count % 2] = msg.x;
        b[count % 2] = msg.y;
        if (count == 0) {
          a1 = msg.x;
          b1 = msg.y;
        }
        count++;
 
        Vertex P(msg.x, msg.y);
        input_vertice.push_back(P);
 
        break;
      }// 左键按下消息 画点
      case  WM_RBUTTONDOWN:
      {
        setlinecolor(RED);
        line(a[0], b[0], a[1], b[1]);
        break;
      }// 右键按下消息 连线
      case   WM_MBUTTONDOWN:
      {
        setlinecolor(RED);
        line(a[(count - 1) % 2], b[(count - 1) % 2], a1, b1);
        cout << "已完成多边形的绘制" << endl;
        flag = 1;
        break;
      }// 中键按下消息 完成绘图
      }
    }
  }
}
void  keyboard() {
  cout << "按w开始裁剪..." << endl;
  //settextcolor(BLUE);//填充蓝色
  int key = _getch();
  switch (key)
  {
    //w键
  case 72:
  case'w':
  case'W':
    SutherlandHodgmanClip(::left);
    SutherlandHodgmanClip(bottom);
    SutherlandHodgmanClip(::right);
    SutherlandHodgmanClip(top);
    for (int i = 0; i < output_vertice.size() - 1; i++)
    {
      putpixel(output_vertice[i].x, output_vertice[i].y, RED);
      line(output_vertice[i].x, output_vertice[i].y, output_vertice[i + 1].x, output_vertice[i + 1].y);
    }
    line(output_vertice[output_vertice.size() - 1].x, output_vertice[output_vertice.size() - 1].y, output_vertice[0].x, output_vertice[0].y);
    break;
 
      default:cout << "输入有误！" << endl;
  }
}
 
 
int main() {
  initgraph(800, 600);
  line(200, 450, 200, 200);
  line(200, 200, 600, 200);
  line(600, 200, 600, 450);
  line(600, 450, 200, 450);//框
  //多边形裁剪
  shubiao();
  setlinestyle(PS_SOLID, 5);
  keyboard();
 
 
  system("pause");
  closegraph();
  return 0;
}


文章标签：
算法
关键词：
裁剪算法
多边形算法
什么时候能躺平
目录
相关文章
什么时候能躺平
|
2月前
多边形扫描转换-扫描线算法
多边形扫描转换-扫描线算法
什么时候能躺平
23 2
幼稚十一
|
2月前
|
算法 图形学
【计算机图形学】实验三 用Cohen-Sutherland裁剪算法实现直线段裁剪
【计算机图形学】实验三 用Cohen-Sutherland裁剪算法实现直线段裁剪
幼稚十一
240 2
幼稚十一
|
2月前
|
算法 图形学
【头歌 计算机图形学 练习】多边形填充v1.0 (第1关：扫描线填充算法（活动边表AET法） 第2关：边缘填充法 第3关：区域四连通种子填充算法 第4关：区域扫描线种子填充算法)
【头歌 计算机图形学 练习】多边形填充v1.0 (第1关：扫描线填充算法（活动边表AET法） 第2关：边缘填充法 第3关：区域四连通种子填充算法 第4关：区域扫描线种子填充算法)
幼稚十一
258 0
HelloDam
|
9月前
|
存储 算法 Java
基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】
基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】
HelloDam
137 0
anrainie
|
算法 索引
连通不规则多边形算法
多边形连通和最小生成树本质上是一样的，问题在于确定权值。 下面算法由js实现，演示由svg提供。 let shown='hidden'; //核心算法 let caculatePath=function(){ ...
anrainie
1116 0
李晓晖
|
算法 索引
一种求任意多边形内部水平方向似最大矩形的算法
文章版权由作者李晓晖和博客园共有，若转载请于明显处标明出处：http://www.cnblogs.com/naaoveGIS/ 1.背景        在前一篇中，我们探讨了如何求凸多边形中的似最大圆，但是针对实际情况需求，我们并没有完全解决问题。
李晓晖
2950 0
科技小毛
|
算法 C#
点在多边形内算法，C#判断一个点是否在一个复杂多边形的内部
科技小毛
1806 0
zting科技
|
算法 API
线段与多边形关系的算法
zting科技
2022 0
ruki
|
算法 异构计算
复杂多边形光栅化算法
虽然已经一年多没有维护gbox这个图形库项目了，最近确实时间不够用。。。 今年的重点是把xmake彻底正好，至少在架构和大功能（包依赖管理）上，要完全落实下来，后期就是零散的维护和插件功能扩展了。
ruki
1202 0
孤独的猫董
|
算法 C语言
裁剪算法
直线裁剪 program clipline;uses crt,graph;var   markseg:word;   gd,gm:integer;   startx,starty,endx,endy:integer;   x1,y1,x2,y2,x,y:integer;   ch:char;   ...
孤独的猫董
850 0

热门文章

最新文章

  • 1
    m基于LDPC编译码的matlab误码率仿真,对比SP,MS,NMS以及OMS四种译码算法
  • 2
    【AI 初识】人工智能中使用了哪些不同的搜索算法？
  • 3
    探索机器学习中的支持向量机（SVM）算法
  • 4
    通过Rust实现公司电脑监控软件的性能优化算法
  • 5
    论文介绍：进化算法优化模型融合策略
  • 6
    探索机器学习中的支持向量机算法
  • 7
    【AI 初识】描述遗传算法概念
  • 8
    Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
  • 9
    LRU（Least Recently Used）算法是一种常用的计算机缓存替换算法
  • 10
    机器学习算法原理与应用：深入探索与实战
  • 1
    面试题：Nginx有哪些负载均衡算法？Nginx位于七层网络结构中的哪一层？
    68
  • 2
    【Hadoop Yarn】Hadoop Yarn 基于优先级的调度算法
    46
  • 3
    【排序算法】插入排序与选择排序详解
    31
  • 4
    【算法与数据结构】深入二叉树实现超详解（全源码优化）
    52
  • 5
    【算法与数据结构】深入解析二叉树（二）之堆结构实现
    31
  • 6
    【算法与数据结构】 C语言实现单链表队列详解2
    22
  • 7
    【算法与数据结构】 C语言实现单链表队列详解1
    38
  • 8
    【算法与数据结构】二叉树（前中后）序遍历2
    25
  • 9
    Machine Learning机器学习之决策树算法 Decision Tree（附Python代码）
    204
  • 10
    从动态规划到贪心算法：最长递增子序列问题的方法全解析
    189

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）