计算几何与图形学有关的几种常用算法.doc
版权申诉
150 浏览量
2024-06-21
07:52:16
上传
评论
收藏 170KB DOC 举报
算法系列之九：计算几何与图形学有关的几种常用算法（一）
分类： 算法系列 2011-12-18 23:13 8182 人阅读 评论(41) 收藏 举报
我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机
图形学》是必修课，也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这
本教科书上的每种算法都实现了一遍，这种重复劳动虽然意义不大，但是收获很
多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收获吧。尽管已
经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成
现在的我，恐怕再也不会有动力去做这些事情了。
在学习《计算机图形学》之前，总觉得很多东西高深莫测，但实际掌握了
之后，却发现其中了无神秘可言，就如同被原始人像神一样崇拜的火却被现代人
叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何，但是没有理论数学
那么高深莫测，它很有实践性，有时候甚至可以简单到匪夷所思。计算几何是随
着计算机和 CAD 的应用而诞生的一门新兴学科，在国外被称为“计算机辅助几何
设计（Computer Aided Geometric Design，CAGD）”。“算法系列”接下来的几
篇文章就会介绍一些图形学中常见的计算几何算法（顺便晒晒我的旧代码），都
是一些图形学中的基础算法，需要一些图形学的知识和数学知识，但是都不难。
不信？那就来看看到底有多难。
本文是第一篇，主要是一些图形学常用的计算几何方法，涉及到向量、点
线关系以及点与多边形关系求解等数学知识，还有一些平面几何的基本原理。事
先声明一下，文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的，
在算法效率和可读性二者的考量上，更注重可读性，有时候为了提高可读性会刻
意采取“效率不高”的代码形式，实际工程中使用的代码肯定更紧凑更高效，但是
算法原理都是一样的，请读者们对此有正确的认识。
一、 判断点是否在矩形内
计算机图形学和数学到底有什么关系？我们先来看几个例子，增加一些感
性认识。首先是判断一个点是否在矩形内的算法，这是一个很简单的算法，但是
剩余19页未读，继续阅读
资源评论
随风浪仔
- 粉丝: 715
- 资源: 2939
