算法系列之九:计算几何与图形学有关的几种常用算法(一)

2023-05-16

我的专业是计算机辅助设计(CAD),算是一半机械一半软件,《计算机图形学》是必修课,也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍,这种重复劳动虽然意义不大,但是收获很多,特别是丢弃了多年的数学又重新回到了脑袋中,算是最大的收获吧。尽管已经毕业多年了,但是每次回顾这些算法的代码,都觉得内心十分澎湃,如果换成现在的我,恐怕再也不会有动力去做这些事情了。

在学习《计算机图形学》之前,总觉得很多东西高深莫测,但实际掌握了之后,却发现其中了无神秘可言,就如同被原始人像神一样崇拜的火却被现代人叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何,但是没有理论数学那么高深莫测,它很有实践性,有时候甚至可以简单到匪夷所思。计算几何是随着计算机和CAD的应用而诞生的一门新兴学科,在国外被称为“计算机辅助几何设计(Computer Aided Geometric Design,CAGD)”。“算法系列”接下来的几篇文章就会介绍一些图形学中常见的计算几何算法(顺便晒晒我的旧代码),都是一些图形学中的基础算法,需要一些图形学的知识和数学知识,但是都不难。不信?那就来看看到底有多难。

本文是第一篇,主要是一些图形学常用的计算几何方法,涉及到向量、点线关系以及点与多边形关系求解等数学知识,还有一些平面几何的基本原理。事先声明一下,文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的,在算法效率和可读性二者的考量上,更注重可读性,有时候为了提高可读性会刻意采取“效率不高”的代码形式,实际工程中使用的代码肯定更紧凑更高效,但是算法原理都是一样的,请读者们对此有正确的认识。

一、 判断点是否在矩形内

计算机图形学和数学到底有什么关系?我们先来看几个例子,增加一些感性认识。首先是判断一个点是否在矩形内的算法,这是一个很简单的算法,但是却非常重要。比如你在一个按钮上点击鼠标,系统如何知道你要触发这个按钮对应的事件而不是另一个按钮?对了,就是一个点是否在矩形内的判断处理。Windows 的API提供了PtInRect()函数,实现方法其实就是判断点的x坐标和y坐标是否同时落在矩形的x坐标范围和y坐标范围内,算法实现也很简单:

150bool IsPointInRect(const Rect& rc, const Point& p)

151{

152 double xr = (p.x - rc.p1.x) * (p.x - rc.p2.x);

153 double yr = (p.y - rc.p1.y) * (p.y - rc.p2.y);

154

155 return ( (xr <= 0.0) && (yr <= 0.0) );

156}

看看IsPointInRect()函数的实现是否和你想象的不一样?有时候硬件实现乘法有困难或受限制于CPU乘法指令的效率,可以考虑用下面的函数替换,代码繁琐了一点,但是避免了乘法运算:

120bool IsPointInRect(const Rect& rc, const Point& p)

121{

122 double xl,xr,yt,yb;

123

124 if(rc.p1.x < rc.p2.x)

125 {

126 xl = rc.p1.x;

127 xr = rc.p2.x;

128 }

129 else

130 {

131 xl = rc.p2.x;

132 xr = rc.p1.x;

133 }

134

135 if(rc.p1.y < rc.p2.y)

136 {

137 yt = rc.p2.y;

138 yb = rc.p1.y;

139 }

140 else

141 {

142 yt = rc.p1.y;

143 yb = rc.p2.y;

144 }

145

146 return ( (p.x >= xl && p.x <= xr) && (p.y >= yb && p.y <= yt) );

147}

由于IsPointInRect()函数并不假设矩形的两个定点是按照坐标轴升序排列的,所以算法实现时就考虑了所有可能的坐标范围。IsPointInRect()函数使用的是平面直角坐标系,如果不特别说明,本文所有的算法都是基于平面直角坐标系设计的。另外,IsPointInRect()函数没有指定特别的浮点数精度范围,默认是系统浮点数的最大精度,只在某些必须要与0比较的情况下,采用10-8次方精度,如无特别说明,本文的所有算法都这样处理。

一、 判断点是否在圆内

现在考虑复杂一点,如果图形界面的按钮不是矩形而是圆形的怎么办呢?当然就是判断点是否在圆内部。判断算法的原理就是计算点到圆心的距离d,然后与圆半径r进行比较,若d < r则说明点在圆内,若d = r则说明点在圆上,若d > r则说明点在圆外。这就要提到计算平面上两点距离的算法。以下图为例,计算平面上任意两点之间的距离主要依据著名的勾股定理:

图1 平面两点距离计算示意图

113//计算欧氏几何空间内平面两点的距离

114double PointDistance(const Point& p1, const Point& p2)

115{

116 return std::sqrt( (p1.x-p2.x)*(p1.x-p2.x)

117 + (p1.y-p2.y)*(p1.y-p2.y) );

118}

一、 判断点是否在多边形内

现在再考虑复杂一点的,如果按钮是个不规则的多边形区域怎么办?别以为这个考虑没有意义,很多多媒体软件和游戏,通常都是用各种形状的不规则图案作为热点(Hot Spot),Windows也提供了PtInRegion() API,用于判断点是否在一个不规则区域中。我们对问题做一个简化,就判断一个点是否在多边形内?判断点P是否在多边形内是计算几何中一个非常基本的算法,最常用的方法是射线法。以P点为端点,向左方做射线L,然后沿着L从无穷远处开始向P点移动,当遇到多边形的某一条边时,记为与多边形的第一个交点,表示进入多边形内部,继续移动,当遇到另一个交点时,表示离开多边形内部。由此可知,当L与多边形的交点个数是偶数时,表示P点在多边形外,当L与多边形交点个数是奇数时,表示P点在多边形内部。

由此可见,要实现判断点是否在多边形内的算法,需要知道直线段求交算法,而求交算法又涉及到矢量的一些基本概念,因此在实现这个算法之前,先讲一下矢量的基本概念以及线段求交算法。

3.1 矢量的基础知识

什么是矢量?简单地讲,就是既有大小又有方向的量,数学中又常被称为向量。矢量有几何表示、代数表示和坐标表示等多种表现形式,本文讨论的是几何表示。如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(Directed Segment),比如线段P1P2,如果起始端点P1就是坐标原点(0, 0),P2的坐标是(x, y),则线段P1P2的二维矢量坐标表示就是P= (x, y)。

3.2 矢量的加法和减法

现在来看几个与矢量有关的重要概念,首先是矢量的加减法。假设有二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量加法定义为:

P + Q = ( x1 + x2 , y1 + y2 )

同样的,矢量减法定义为:

P - Q = ( x1 - x2 , y1 - y2 )

根据矢量加减法的定义,矢量的加减法满足以下性质:


P + Q = Q + P

P - Q = - ( Q - P )

图2 演示了矢量加法和减法的几何意义,由于几何中直线段的两个点不可能刚好在原点,因此线段P1P2的矢量其实就是OP2 - OP1的结果,如图2 (b)所示:

3.3 矢量的叉积(外积)

另一个比较重要的概念是矢量的叉积(外积)。计算矢量的叉积是判断直线和线段、线段和线段以及线段和点的位置关系的核心算法。假设有二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量的叉积定义为:

P × Q = x1*y2 - x2*y1

向量叉积的几何意义可以描述为由坐标原点(0,0)、P、Q和P + Q所组成的平行四边形的面积,而且是个带符号的面积,由此可知,矢量的叉积具有以下性质:

P × Q = - ( Q × P )

叉积的结果P × Q是P和Q所在平面的法矢量,它的方向是垂直与P和Q所在的平面,并且按照P、Q和P × Q的次序构成右手系,所以叉积的另一个非常重要性质是可以通过它的符号可以判断两矢量相互之间位置关系是顺时针还是逆时针关系,具体说明如下:

1) 如果 P × Q > 0 , 则Q在P的逆时针方向;

2) 如果 P × Q < 0 , 则Q在P的顺时针方向;

3) 如果 P × Q = 0 , 则Q与P共线(但可能方向是反的);

3.4 矢量的点积(内积)

最后要介绍的概念是矢量的点积(内积)。假设有二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量的点积定义为:

P·Q = x1*x2 + y1*y2

向量点积的结果是一个标量,它的代数表示是:

P·Q = |P| |Q| cos(P, Q)

(P, Q) 表示向量P和Q的夹角,如果P和Q不共线,则根据上式可以得到向量点积的一个非常重要的性质,具体说明如下:

1) 如果 P · Q > 0 , 则P和Q的夹角是钝角(大于90度);

2) 如果 P · Q < 0 , 则P和Q的夹角是锐角(小于90度);

3) 如果 P · Q = 0 , 则P和Q的夹角是90度;

了解了矢量的概念以及矢量的各种运算的几何意义和代数意义后,就可以开始解决各种计算几何的简单问题了,回想本文开始提到的点与多边形的关系问题,首先要解决的就是判断点和直线段的位置关系问题。

3.5 用矢量的叉积判断点和直线的关系

根据矢量叉积的几何意义,如果线段所表示的矢量和点的矢量的叉积是0,就说明点在线段所在的直线上,相对于坐标原点O来说,线段的矢量其实就是线段终点P2=[x2, y2]的矢量OP2减线段起点P1=[x1, y1]的矢量OP1的结果,因此线段P1P2的矢量可以表示为P1P2=(x2 – x1, y2 – y1)。如果要判断点P是否在线段P1P2上,就要判断矢量P1P2和矢量OP的叉积是否是0。需要注意的是,叉积为0只能说明点P与线段P1P2所在的直线共线,并不能说明点P一定会落在P1P2区间上,因此只是一个必要条件。要正确判断P在线段P1P2上,还需要做一个排斥试验,就是检查点P是否在以直线段为对角线的矩形空间内,如果以上两个条件都为真,即可判定点在线段上。有了上述原理,算法实现就比较简单了,以下就是判断点是否在线段上的算法:

174bool IsPointOnLineSegment(const LineSeg& ls, const Point& pt)

175{

176 Rect rc;

177

178 GetLineSegmentRect(ls, rc);

179 double cp = CrossProduct(ls.pe.x - ls.ps.x, ls.pe.y - ls.ps.y,

180 pt.x - ls.ps.x, pt.y - ls.ps.y); //计算叉积

181

182 return ( (IsPointInRect(rc, pt)) //排除实验

183 && IsZeroFloatValue(cp) ); //1E-8 精度

184}

185

【未完,下篇继续介绍用矢量叉积判断直线和直线段的位置关系,以及判断点与多边形关系的完整算法】

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

算法系列之九:计算几何与图形学有关的几种常用算法(一) 的相关文章

  • Linux 挂载 exFat

    在Linux的学习中为方便大家学习了解更多的Linux方面的内容 xff0c 达内培训 技术小编本文将为大家详解关于Linux方面的技术内容 xff0c 提供给大家作为学习的参考 先说挂载exFAT格式的移动硬盘 xff0c 最近刚刚做了个
  • HTML中meta标签的作用

    HTML中meta标签的作用 首先 xff0c meta标签是一个自结束标签 xff0c 其格式为 lt meta gt xff0c 下面介绍meta标签的作用 xff1a 1 规定字符集 lt meta charset 61 34 utf
  • 多个浏览器窗口中间不同的Session

    关于多个窗口不同Session的作用就不说了 xff0c 直接说步骤 Firefox xff1a 编辑快捷方式的目标 xff0c 后面加上 p no remote Chrome xff1a 打开新的隐身窗口 IE xff1a 文件 gt 新
  • Nginx 开启对 PHP 的解析(转)

    安装 PHP 和 nginx 后 xff0c 无法解析 PHP 文件 其中 xff0c PHP 和 nginx 的编译安装 configure 如下 xff1a PHP 5 3 9 configure prefix 61 usr local
  • JDK 对应数字版本号

    J2SE 7 61 51 0x33 hex J2SE 6 0 61 50 0x32 hex J2SE 5 0 61 49 0x31 hex JDK 1 4 61 48 0x30 hex JDK 1 3 61 47 0x2F hex JDK
  • 打印控件

    Lodop
  • 二进制最大公约数算法

    求最大公约数的Euclid算法需要用到大量的取模运算 xff0c 这在大多数计算机上是一项复杂的工作 xff0c 相比之下减法运算 测试数的奇偶性 折半运算的执行速度都要更快些 二进制最大公约数算法避免了Euclid算法的取余数过程 二进制
  • 1、docker+k8s+kubesphere:准备(20200802更新免密)

    1 准备 docker 43 k8s 43 kubesphere准 环境准备 角色IP地址主机名docker版本硬件操作系统主192 168 5 151node151docker18 09 96核10GCentOS7 8节点192 168
  • 2、docker+k8s+kubesphere:docker安装

    2 docker安装 docker 43 k8s 43 kubesphere 卸载以前的docker yum remove y docker docker client docker client latest docker common
  • 7、docker+k8s+kubesphere:helm与tiller安装

    7 docker 43 k8s 43 kubesphere helm安装 官网地址 https kubesphere io docs zh CN installation install on k8s 官网虽然说低配置可以使用 xff0c
  • 8、docker+k8s+kubesphere:nfs安装(2020-08-02更新)

    8 docker 43 k8s 43 kubesphere nfs安装 server端安装在node151 yum y span class token function install span nfs utils rpcbind 配置文
  • 9、docker+k8s+kubesphere:Kubernetes安装(2020-08-02更新)

    9 docker 43 k8s 43 kubesphere Kubernetes安装 官网说明一定详细查看 span class token punctuation span 本文用的是2 1 1 span class token punc
  • Linux修改进程名称(setproctitle())

    每一个c程序都有个main函数 xff0c 作为程序启动入口函数 main函数的原型是int main int argc char argv 其中argc表示命令行参数的个数 xff1b argv是一个指针数组 xff0c 保存所有命令行字
  • 转载一篇文章:别人做毕业设计的思路

    发信人 zyzyis 小菜 十年一觉扬州梦 信区 SCU CS 标 题 我来谈谈毕业设计 xff08 准备篇 xff09 发信站 四川大学蓝色星空站 Sat Jan 15 11 15 53 2005 转信 很早就想写篇帖子来讲述自己做了近半
  • bash实现的回收站程序

    好久没写博了 哈哈 xff0c 最近在学习Linux 这是偶写的第一个shell脚本 xff0c 是一个实现类似windows里的回收站的程序 xff0c 可以避免误删文件 xff0c 希望能够对大家有所帮助 xff0c 当然自己练手是最重
  • 程序的格式

    一 格式 注 xff1a 比算法还重要 1 该注意的问题 xff1a xff08 1 xff09 大括号对齐 xff08 2 xff09 遇到 要缩进 xff1a Tab或Shift 43 Tab xff08 3 xff09 程序块之间加空
  • 解决中文版SUSELinux在远程终端上的乱码问题

    在远程桌面上打开Linux系统终端 xff0c 执行程序或某些命令时 xff0c 返回结果中出现乱码 解决方法 xff1a 计算机 gt YaST2控制中心 xff08 注 xff1a 非管理员用户 xff08 root xff09 进入时
  • 如何打开并读取QQ聊天记录Msg3.0.db文件的内容

    如何打开并读取QQ聊天记录Msg3 0 db文件的内容
  • 硬盘安装CentOS5.x笔记

    原来安装了一个64位的Linux xff0c 发现老是有些软件安装不了 xff0c 所以打算重新安装一个32位的 xff0c 选的CentOS5 2 i386版的Linux 镜像文件下载来后 xff0c 也懒得再刻盘 xff0c 打算从硬盘
  • 求一个unsigned int 数的二进制表示中有多少个1?

    第一种方法 xff0c 使用普通循环 unsigned int GetBitNum1 unsigned int nValue const unsigned int nNumOfBitInByte 61 8 unsigned int temp

随机推荐

  • UISlider 滑块控件—IOS开发

    声明 欢迎转载 xff0c 但是请尊重作者劳动成果 xff0c 转载请保留此框内声明 xff0c 谢谢 文章出处 xff1a http blog csdn net iukey PC上的滑块是很丑陋的 xff0c 因为我们只能通过鼠标去拖动他
  • sqlite3中BLOB数据类型存储大对象运用示例

    1 常用接口 个人比较喜欢sqlite 使用最方便 xff0c 唯一的准备工作是下载250K的源 xff1b 而且作者很热心 xff0c 有问必答 以下演示一下使用sqlite的步骤 xff0c 先创建一个数据库 xff0c 然后查询其中的
  • Linux进程同步之System V 信号量

    SystemV信号量是不属于 POSIX 标准 xff0c 它属于 SUS xff08 SingleUNIXSpecification xff09 单一规范中的扩展定义 它和 POSIX 信号量一样都提供基本的信号量功能操作 SystemV
  • IOS用CGContextRef画各种图形(文字、圆、直线、弧线、矩形、扇形、椭圆、三角形、圆角矩形、贝塞尔曲线、图片)...

    首先了解一下CGContextRef An opaque type that represents a Quartz 2D drawing environment Graphics Context是图形上下文 可以将其理解为一块画布 我们可
  • C++实现中文字频统计

    中文文本字频统计系统设计 一 实验内容 问题描述 中文信息处理中常用到汉字的字频统计 xff0c 设计一个小工具统计文本的字频 基本要求 1 输入一个中文文本 2 用三种排序分别输出结果 xff1a 按汉字出现顺序输出的字频 xff0c 按
  • [XMPP]我是怎么通过直接操作数据来为Openfire注册新用户的

    众所周知 xff0c Openfire的注册方式一般有三种 1 带内注册 In Band Registration 即客户端通过匿名方式与Openfire 服务器端建立连接并验证 xff0c 然后发起注册节点XML流 xff0c 以XMPP
  • IdeaVim插件使用技巧

    在 url 61 http kidneyball iteye com blog 1814028 IDEA Intellij小技巧和插件 url 一文中简单介绍了一下IdeaVim插件 在这里详细总结一下这个插件在日常编程中的一些常用小技巧
  • 机器学习系列(3)_逻辑回归应用之Kaggle泰坦尼克之灾

    作者 xff1a 寒小阳 amp amp 龙心尘 时间 xff1a 2015年11月 出处 xff1a http blog csdn net han xiaoyang article details 49797143 声明 xff1a 版权
  • Android 获取系统设置参数。

    转载自 xff1a http blog 163 com fang wang2005 blog static 176928073201136105613638 如何获取Android系统设置参数 下面以获取时间格式为例 xff0c 来判断时间
  • linux下默认删除文件到回收站(bash实现)

    fedora下总是会把文件不小心删除了 xff0c 所以下面的脚本把实现 xff1a 文件删除默认移动到自己的回收站里面 功能 xff1a 脚本实现删除文件或者目录到 waste xff08 自己定义 xff09 脚本附带文件名或者目录名
  • android 开机启动程序

    做一个android开机就会自动启动的程序 xff0c 该程序只要启动一次 xff0c 以后开机就会自动启动 xff0c 直到删除该程序 android开机事件会发送一个叫做Android intent action BOOT COMPLE
  • 在 Linux 平台中调试 C/C++ 内存泄漏方法

    由于 C 和 C 43 43 程序中完全由程序员自主申请和释放内存 xff0c 稍不注意 xff0c 就会在系统中导入内存错误 同时 xff0c 内存错误往往非常严重 xff0c 一般会带来诸如系统崩溃 xff0c 内存耗尽这样严重的后果
  • Java 位运算

    Java 位运算 转 一 xff0c Java 位运算 1 表示方法 xff1a 在Java语言中 xff0c 二进制数使用补码表示 xff0c 最高位为符号位 xff0c 正数的符号位为0 xff0c 负数为1 补码的表示需要满足如下要求
  • iOS学习之UINavigationController详解与使用(一)添加UIBarButtonItem

    1 UINavigationController导航控制器如何使用 UINavigationController可以翻译为导航控制器 xff0c 在iOS里经常用到 我们看看它的如何使用 xff1a 下面的图显示了导航控制器的流程 最左侧是
  • OpenStack多节点部署(一)——服务器选型

    OpenStack多节点部署 xff08 一 xff09 服务器选型 OpenStack多节点部署 xff08 二 xff09 操作系统安装 OpenStack多节点部署 xff08 三 xff09 网络配置 OpenStack多节点部署
  • 【代码】使用C++实现改进的有效边表算法。

    算法的解释和一些细节晚一些再上传 xff0c 先直接上代码 xff1a 如果有错误可以在评论区指出 由于opengl使用实数的坐标 xff0c 所以 xff0c 本程序将使用画线代替画点 include lt GL glut h gt in
  • FireFox导入导出Cookies和收藏夹的方法

    FireFox是一个常用的浏览器 xff0c 扩展插件众多 xff0c 和IE相比有很多优点 xff0c 不过有些细小的地方似乎考虑的不太好 xff0c 比如用户经常会碰到系统重新安装等问题 xff0c 这就需要导入导出FireFox浏览器
  • linux交换分区回收

    author xff1a skate time xff1a 2012 04 11 交换分区回收 如果系统过多的使用交换分区 xff0c 那性能将会变慢 xff0c 所以要找到大量使用交换分区的原因 回收交换分区可以用如下 xff1a swa
  • Linux下查看文件和文件夹大小的df和du命令

    当磁盘大小超过标准时会有报警提示 xff0c 这时如果掌握df和du命令是非常明智的选择 df可以查看一级文件夹大小 使用比例 档案系统及其挂入点 xff0c 但对文件却无能为力 du可以查看文件及文件夹的大小 两者配合使用 xff0c 非
  • 算法系列之九:计算几何与图形学有关的几种常用算法(一)

    我的专业是计算机辅助设计 xff08 CAD xff09 xff0c 算是一半机械一半软件 xff0c 计算机图形学 是必修课 xff0c 也是我最喜欢的课程 热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍 xff0c 这