首页 / 软件开发 / 数据结构与算法 / 算法系列（九） 计算几何与图形学有关的几种常用算法（一）

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

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

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

一、判断点是否在矩形内

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

150 bool 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乘法指令的效率，可以考虑用下面的函数替换，代码繁琐了一点，但是避免了乘法运算 ：

120 bool 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次方精 度，如无特别说明，本文的所有算法都这样处理。