计算几何与图形学有关的几种常用算法.doc

算法系列之九：计算几何与图形学有关的几种常用算法（一） 分类： 算法系列 2011-12-18 23:13 8182人阅读 评论(41) \o 收藏 收藏 \o 举报 举报 ? ??????? 我的专业是计算机辅助设计（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) );