算法系列之九：计算几何与图形学有关的几种常用算法（一）
分类：算法系列2011-12-18 23:13 8182人阅读评论(41) 收藏举报
我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机图形学》是必修课，也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍，这种重复劳动虽然意义不大，但是收获很多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收获吧。尽管已经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成现在的我，恐怕再也不会有动力去做这些事情了。
在学习《计算机图形学》之前，总觉得很多东西高深莫测，但实际掌握了之后，却发现其中了无神秘可言，就如同被原始人像神一样崇拜的火却被现代人叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何，但是没有理论数学那么高深莫测，它很有实践性，有时候甚至可以简单到匪夷所思。计算几何是随着计算机和CAD的应用而诞生的一门新兴学科，在国外被称为“计算机辅助几何设计（Computer Aided Geometric Design，CAGD）”。“算法系列”接下来的几篇文章就会介绍一些图形学中常见的计算几何算法（顺便晒晒我的旧代码），都是一些图形学中的基础算法，需要一些图形学的知识和数学知识，但是都不难。不信？那就来看看到底有多难。
本文是第一篇，主要是一些图形学常用的计算几何方法，涉及到向量、点线关系以及点与多边形关系求解等数学知识，还有一些平面几何的基本原理。事先声明一下，文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的，在算法效率和可读性二者的考量上，更注重可读性，有时候为了提高可读性会刻意采取“效率不高”的代码形式，实际工程中使用的代码肯定更紧凑更高效，但是算法原理都是一样的，请读者们对此有正确的认识。
一、判断点是否在矩形内
计算机图形学和数学到底有什么关系？我们先来看几个例子，增加一些感性认识。首先是判断一个点是否在矩形内的算法，这是一个很简单的算法，但是
却非常重要。比如你在一个按钮上点击鼠标，系统如何知道你要触发这个按钮对应的事件而不是另一个按钮？对了，就是一个点是否在矩形内的判断处理。Windows 的API提供了PtInRect()函数，实现方法其实就是判断点的x坐标和y坐标是否同时落在矩形的x坐标范围和y坐标范围内，算法实现也很简单：
150bool IsPointInRect(const Rect& rc,const Point& p)
151{
152double xr =(p.x - rc.p1.x)*(p.x - rc.p2.x);
153double yr =(p.y - rc.p1.y)*(p.y - rc.p2.y);
154
155return((xr <=0.0)&&(yr <=0.0));
156}
看看IsPointInRect()函数的实现是否和你想象的不一样？有时候硬件实现乘法有困难或受限制于CPU乘法指令的效率，可以考虑用下面的函数替换，代码繁琐了一点，但是避免了乘法运算：
120bool IsPointInRect(const Rect& rc,const Point& p)
121{
122double xl,xr,yt,yb;
123
124if(rc.p1.x < rc.p2.x)
125{
126 xl = rc.p1.x;
127 xr = rc.p2.x;
128}
129else
130{
131 xl = rc.p2.x;
132 xr = rc.p1.x;
133}
134
135if(rc.p1.y < rc.p2.y)
136{
137 yt = rc.p2.y;
138 yb = rc.p1.y;
139}
140else
141{
142 yt = rc.p1.y;
143 yb = rc.p2.y;
144}
145
146return((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{
116return 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);
179double 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
182return((IsPointInRect(rc, pt))//排除实验
183&& IsZeroFloatValue(cp));//1E-8 精度
184}
185
【未完，下篇继续介绍用矢量叉积判断直线和直线段的位置关系，以及判断点与多边形关系的完整算法】
算法系列之九：计算几何与图形学有关的几种常用算法（二）
分类：算法系列2011-12-25 23:04 2346人阅读评论(9) 收藏举报3.6 用矢量的叉积判断直线段是否有交
矢量叉积计算的另一个常用用途是直线段求交。求交算法是计算机图形学的核心算法，也是体现速度和稳定性的重要标志，高效并且稳定的求交算法是任何一个CAD软件都必需要重点关注的。求交包含两层概念，一个是判断是否相交，另一个是求出交点。直线（段）的求交算法相对来说是比较简单的，首先来看看如何判断两直线段是否相交。
常规的代数计算通常分三步，首先根据线段还原出两条线段所在直线的方程，然后联立方程组求出交点，最后再判断交点是否在线段区间上。常规的代数方法非常繁琐，每次都要解方程组求交点，特别是交点不在线段区间的情况，计算交点就是做无用功。计算几何方法判断直线段是否有交点通常分两个步骤完成，这两个步骤分别是快速排斥试验和跨立试验。假设要判断线段P1P2和线段Q1Q2是否有交点，则：
（1）快速排斥试验
设以线段P1P2 为对角线的矩形为R1，设以线段Q1Q2 为对角线的矩形为R2，如果R1和R2不相交，则两线段不会有交点；
（2）跨立试验。
如果两线段相交，则两线段必然相互跨立对方，所谓跨立，指的是一条线段的两端点分别位于另一线段所在直线的两边。判断是否跨立，还是要用到矢量叉积的几何意义。以图3为例，若P1P2跨立Q1Q2 ，则矢量( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改写成：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明线段P1P2和Q1Q2共线（但是不一定有交点）。同理判断Q1Q2跨立P1P2的依据是：
( Q1 - P1 ) × ( P2 - P1 ) * ( Q2 - P1 ) × ( P2 - P1 ) < 0
具体情况如下图所示：
图3 直线段跨立试验示意图
根据矢量叉积的几何意义，跨立试验只能证明线段的两端点位于另一个线段所在直线的两边，但是不能保证是在另一直线段的两端，因此，跨立试验只是证明两条线段有交点的必要条件，必需和快速排斥试验一起才能组成直线段相交的充分必要条件。根据以上分析，两条线段有交点的完整判断依据就是：1)以两条线段为对角线的两个矩形有交集；2)两条线段相互跨立。
判断直线段跨立用计算叉积算法的CrossProduct()函数即可，还需要一个判断两个矩形是否有交的算法。矩形求交也是最简单的求交算法之一，原理就是根据两个矩形的最大、最小坐标判断。图4展示了两个矩形没有交集的各种情况：
图4 矩形没有交集的几种情况图5展示了两个矩形有交集的各种情况：
图5 矩形有交集的几种情况
从图4和图5可以分析出来两个矩形有交集的几何坐标规律，就是在x坐标方向和y坐标方向分别满足最大值最小值法则，简单解释这个法则就是每个矩形在每个方向上的坐标最大值都要大于另一个矩形在这个坐标方向上的坐标最小值，否则在这个方向上就不能保证一定有位置重叠。由以上分析，判断两个矩形是否相交的算法就可以如下实现：
186bool IsRectIntersect(const Rect& rc1,const Rect& rc2)
187{
188return((std::max(rc1.p1.x,rc1.p2.x)>=std::min(rc2.p1.x,
rc2.p2.x))
189&&(std::max(rc2.p1.x, rc2.p2.x)>=
std::min(rc1.p1.x, rc1.p2.x))
190&&(std::max(rc1.p1.y, rc1.p2.y)>=
std::min(rc2.p1.y, rc2.p2.y))
191&&(std::max(rc2.p1.y, rc2.p2.y)>=
std::min(rc1.p1.y, rc1.p2.y)));
192}
完成了排斥试验和跨立试验的算法，最后判断直线段是否有交点的算法就水到渠成了：
204bool IsLineSegmentIntersect(const LineSeg& ls1,const LineSeg&
ls2)
205{
206if(IsLineSegmentExclusive(ls1, ls2))//排斥实验
207{
208return false;
209}
210//( P1 - Q1 ) ×'a1?( Q2 - Q1 )
211double p1xq = CrossProduct(ls1.ps.x - ls2.ps.x, ls1.ps.y -
ls2.ps.y,
212 ls2.pe.x - ls2.ps.x, ls2.pe.y -
ls2.ps.y);
213//( P2 - Q1 ) ×'a1?( Q2 - Q1 )
214double p2xq = CrossProduct(ls1.pe.x - ls2.ps.x, ls1.pe.y -
ls2.ps.y,
215 ls2.pe.x - ls2.ps.x, ls2.pe.y -
ls2.ps.y);
216
217//( Q1 - P1 ) ×'a1?( P2 - P1 )
218double q1xp = CrossProduct(ls2.ps.x - ls1.ps.x, ls2.ps.y -
ls1.ps.y,
219 ls1.pe.x - ls1.ps.x, ls1.pe.y -
ls1.ps.y);
220//( Q2 - P1 ) ×'a1?( P2 - P1 )
221double q2xp = CrossProduct(ls2.pe.x - ls1.ps.x, ls2.pe.y -
ls1.ps.y,
222 ls1.pe.x - ls1.ps.x, ls1.pe.y -
ls1.ps.y);
223
224//跨立实验
225return((p1xq * p2xq <=0.0)&&(q1xp * q2xp <=0.0)); 226}
IsLineSegmentExclusive()函数就是调用IsRectIntersect()函数根据结果做排斥判断，此处不再列出代码。
3.7 点和多边形关系的算法实现
好了，现在我们已经了解了矢量叉积的意义，以及判断直线段是否有交点的算法，现在回过头看看文章开始部分的讨论的问题：如何判断一个点是否在多边形内部？根据射线法的描述，其核心是求解从P点发出的射线与多边形的边是否有交点。注意，这里说的是射线，而我们前面讨论的都是线段，好像不适用吧？没错，确实是不适用，但是我要介绍一种用计算机解决问题时常用的建模思想，应用了这种思想之后，我们前面讨论的方法就适用了。什么思想呢？就是根据问题域的规模和性质抽象和简化模型的思想，这可不是故弄玄虚，说说具体的思路吧。
计算机是不能表示无穷大和无穷小，计算机处理的每一个数都有确定的值，而且必须有确定的值。我们面临的问题域是整个实数空间的坐标系，在每个维度上都是从负无穷到正无穷，比如射线，就是从坐标系中一个明确的点到无穷远处的连线。这就有点为难计算机了，为此我们需要简化问题的规模。假设问题中多边形的每个点的坐标都不会超过(-10000.0, +10000.0)区间（比如我们常见的图形输出设备都有大小的限制），我们就可以将问题域简化为(-10000.0, +10000.0)
区间内的一小块区域，对于这块区域来说，>= 10000.0就意味着无穷远。你肯定已经明白了，数学模型经过简化后，算法中提到的射线就可以理解为从模型边界到内部点P之间的线段，前面讨论的关于线段的算法就可以使用了。
射线法的基本原理是判断由P点发出的射线与多边形的交点个数，交点个数是奇数表示P点在多边形内（在多边形的边上也视为在多边形内部的特殊情况），正常情况下经过点P的射线应该如图6（a）所示那样，但是也可能碰到多种非正常情况，比如刚好经过多边形一个定点的情况，如图6 （b），这会被误认为和两条边都有交点，还可能与某一条边共线如图6 （c）和（d），共线就有无穷多的交点，导致判断规则失效。还要考虑凹多边形的情况，如图6（e）。
图6 射线法可能遇到的各种交点情况
针对这些特殊情况，在对多边形的每条边进行判断时，要考虑以下这些特殊情况，假设当前处理的边是P1P2，则有以下原则：
1）如果点P在边P1P2上，则直接判定点P在多边形内；
2）如果从P发出的射线正好穿过P1或者P2，那么这个交点会被算作2次（因为在处理以P1或P2为端点的其它边时可能已经计算过这个点了），对这种情况的处理原则是：如果P的y坐标与P1、P2中较小的y坐标相同，则忽略这个交点；
3）如果从P发出的射线与P1P2平行，则忽略这条边；
对于第三个原则，需要判断两条直线是否平行，通常的方法是计算两条直线的斜率，但是本算法因为只涉及到直线段（射线也被模型简化为长线段了），就简化了很多，判断直线是否水平，只要比较一下线段起始点的y坐标是否相等就行了，而判断直线是否垂直，也只要比较一下线段起始点的x坐标是否相等就行了。
应用以上原则后，扫描线法判断点是否在多边形内的算法流程就完整了，图7就是算法的流程图：
最终扫描线法判断点是否在多边形内的算法实现如下：
228bool IsPointInPolygon(const Polygon& py,const Point& pt)
229{
230 assert(py.IsValid());/*只考虑正常的多边形，边数>=3*/
231
232int count =0;
233 LineSeg ll = LineSeg(pt, Point(-INFINITE, pt.y));/*射线L*/ 234for(int i =0; i < py.GetPolyCount(); i++)
235{
236/*当前点和下一个点组成线段P1P2*/
237 LineSeg pp = LineSeg(py.pts[i], py.pts[(i +1)%
py.GetPolyCount()]);
238if(IsPointOnLineSegment(pp, pt))
239{
240return true;
241}
242
243if(!pp.IsHorizontal())
244{
245if((IsSameFloatValue(pp.ps.y, pt.y))&&(pp.ps.y > pp.pe.y))
246{
247 count++;
248}
249else if((IsSameFloatValue(pp.pe.y, pt.y))&&
(pp.pe.y > pp.ps.y))
250{
251 count++;
252}
253else
254{
255if(IsLineSegmentIntersect(pp, ll))
256{
257 count++;
258}
259}
260}
261}
262
263return((count %2)==1);
264}
在图形学领域实施的真正工程代码，通常还会增加一个多边形的外包矩形快速判断，对点根本就不在多边形周围的情况做快速排除，提高算法效率。这又涉及到求多边形外包矩形的算法，这个算法也很简单，就是遍历多边形的所有节点，找出各个坐标方向上的最大最小值。以下就是求多边形外包矩形的算法：
266void GetPolygonEnvelopRect(const Polygon& py, Rect& rc)
267{
268 assert(py.IsValid());/*只考虑正常的多边形，边数>=3*/
269
270double minx = py.pts[0].x;
271double maxx = py.pts[0].x;
272double miny = py.pts[0].y;
273double maxy = py.pts[0].y;
274for(int i =1; i < py.GetPolyCount(); i++)
275{
276if(py.pts[i].x < minx)
277 minx = py.pts[i].x;
278if(py.pts[i].x > maxx)
279 maxx = py.pts[i].x;
280if(py.pts[i].y < miny)
281 miny = py.pts[i].y;
282if(py.pts[i].y > maxy)
283 maxy = py.pts[i].y;
284}
285
286 rc = Rect(minx, miny, maxx, maxy);
287}
除了扫描线法，还可以通过多边形边的法矢量方向、多边形面积以及角度和等方法判断点与多边形的关系。但是这些算法要么只支持凸多边形，要么需要复杂的三角函数运算（多边形边数小于44时，可采用近似公式计算夹角和，避免三角函数运算），使用的范围有限，只有扫描线法被广泛应用。
至此，本文的内容已经完结，以上通过对点与矩形、点与圆、点与直线以及点与多边形位置关系判断算法的讲解，向大家展示了几种常见的计算几何算法实现，用简短而易懂的代码剖析了这些算法的实质。下一篇将介绍计算机图形学中最基本的直线生成算法。
参考资料：
【1】计算几何：算法设计与分析周培德清华大学出版社2005年
【2】计算几何：算法与应用德贝尔赫（邓俊辉译）清华大学出版社2005年【3】算法导论Thomas H.Cormen等（潘金贵等译）机械工业出版社2006年【4】计算机图形学孙家广、杨常贵清华大学出版社1995年
计算几何基础知识整理 一、序言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、本基础目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1. 矢量的概念 2. 矢量加减法 3. 矢量叉积 4. 折线段的拐向判断 5. 判断点是否在线段上 6. 判断两线段是否相交 7. 判断线段和直线是否相交 8. 判断矩形是否包含点 9. 判断线段、折线、多边形是否在矩形中 10. 判断矩形是否在矩形中 11. 判断圆是否在矩形中 12. 判断点是否在多边形中 13. 判断线段是否在多边形内 14. 判断折线是否在多边形内 15. 判断多边形是否在多边形内 16. 判断矩形是否在多边形内 17. 判断圆是否在多边形内 18. 判断点是否在圆内 19. 判断线段、折线、矩形、多边形是否在圆内 20. 判断圆是否在圆内 21. 计算点到线段的最近点 22. 计算点到折线、矩形、多边形的最近点 23. 计算点到圆的最近距离及交点坐标 24. 计算两条共线的线段的交点 25. 计算线段或直线与线段的交点 26. 求线段或直线与折线、矩形、多边形的交点 27. 求线段或直线与圆的交点 28. 凸包的概念 29. 凸包的求法 三、算法介绍 1.矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed
小学数学图形计算公式 （C ：周长 S ：面积 a ：边长、长 、底、上底、棱长 b: 宽 、下底 h: 高 d ：直径 r ：半径 V:体积 ） 1、长方形周长=(长+宽)×2 C=2(a+b) 长方形面积=长×宽 S=ab 2、正方形周长＝边长×4 C = 4a 正方形面积=边长×边长 S = a×a = a 2 3、平行四边形面积=底×高 s=ah 4、三角形面积=底×高÷2 s=ah÷2 三角形高=面积 ×2÷底 h = 2s ÷a 三角形底=面积 ×2÷高 5、梯形面积=(上底+下底)×高÷2 s=(a+b)× h÷2 6、圆的周长=直径×圆周率=2×圆周率×半径 C=лd=2лr d=C π r=C 2π 圆的面积=半径×半径×圆周率 S = πr 2 环形的面积=外圆的面积-内圆的面积 S 环=π（R 2-r 2） 7、长方体的棱长总和 = 长×4 + 宽×4 + 高×4 =（长 + 宽 + 高）×4 长方体表面积=(长×宽+长×高+宽×高)×2 S = 2( ab + ah + bh ) 长方体体积=长×宽×高 = 底面积×高 V=abh = sh 8、正方体的棱长总和=棱长×12 正方体表面积=棱长×棱长×6 S 表 = a×a×6 = 6a 2 正方体体积=棱长×棱长×棱长=底面积×高 V = a×a×a = a 3 = sh 9、圆柱的侧面积=底面周长×高 s 侧=ch=πdh=2πrh 圆柱表面积=侧面积+底面积×2 s 表=s 侧+s 底×2 圆柱体积=底面积×高 V 柱 = sh =πr 2h 10、圆锥体体积=底面积×高×13 V 锥 = 13 sh = 1 3 πr 2h 小学数学图形计算公式 （C ：周长 S ：面积 a ：边长、长 、底、上底、棱长 b: 宽 、下底 h: 高 d ：直径 r ：半径 V:体积 ） 1、长方形周长=(长+宽)×2 C=2(a+b) 长方形面积=长×宽 S=ab 2、正方形周长＝边长×4 C = 4a 正方形面积=边长×边长 S = a×a = a 2 3、平行四边形面积=底×高 s=ah 4、三角形面积=底×高÷2 s=ah÷2 三角形高=面积 ×2÷底 h = 2s ÷a 三角形底=面积 ×2÷高 5、梯形面积=(上底+下底)×高÷2 s=(a+b)× h÷2 6、圆的周长=直径×圆周率=2×圆周率×半径 C=лd=2лr d=C π r=C 2π 圆的面积=半径×半径×圆周率 S = πr 2 环形的面积=外圆的面积-内圆的面积 S 环=π（R 2-r 2） 7、长方体的棱长总和 = 长×4 + 宽×4 + 高×4 =（长 + 宽 + 高）×4 长方体表面积=(长×宽+长×高+宽×高)×2 S = 2( ab + ah + bh ) 长方体体积=长×宽×高 = 底面积×高 V=abh = sh 8、正方体的棱长总和=棱长×12 正方体表面积=棱长×棱长×6 S 表 = a×a×6 = 6a 2 正方体体积=棱长×棱长×棱长=底面积×高 V = a×a×a = a 3 = sh 9、圆柱的侧面积=底面周长×高 s 侧=ch=πdh=2πrh 圆柱表面积=侧面积+底面积×2 s 表=s 侧+s 底×2 圆柱体积=底面积×高 V 柱 = sh =πr 2h 10、圆锥体体积=底面积×高×13 V 锥 = 13 sh = 1 3 πr 2h 中小学教师信息技术考试理论试题 一选择题（40分，每一题1分） 1.下面选项是对信息的实质的理解和说明,其中错误的选项是________. A. 信息就是计算机的处理对象 B. 信息就是关于事物运动的状态和规律的知识 C. 信息就是信息,既不是物质,也不是能量 D. 信息就是人类同外部世界进行交换的内容的名称 2. 信息技术在教学中常用作获取学习资源的工具,人们常说,"因特网是知识的海洋".
POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:
常见几何体的面积、体积求法与应用 要计算某材料的密度、重量，研究某物体性能及其物质结构等，特别对于机械专业的学生，必须要求工件的面积、体积等，若按课本上公式来计算，而课本上公式不统一，不好记住，并且很繁杂，应用时要找公式，对号入座很麻烦。笔者在教学与实践中总结出一种计算常见几何体的面积、体积方法。其公式统一，容易记住，且计算简单。对技校学生来说，排除大部分繁琐的概念、定理，以及公式的推导应用等。 由统计学中的用加权平均数对估计未来很准确。比如，估计某商品下个月销售量，若去年平均销售量为y ，设本月权为4，上月权数为1，下月权数为1，各月权数分别乘销售量相加后除以6等于y 。这样能准确地确定下个月销售量。能不能以这种思想方法用到求几何体的面积、体积呢？通过推导与实践，对于常见的几何体确实可用这种方法来求得其面积、体积。下面分别说明求常见几何体的面积、体积统一公式的正确性与可用性。 常见几何体的面积、体积统一公式： ) 4(6 )4(621002100S S S h V C C C h A ++= ++= （其中A 为几何体侧面积，C 0为上底面周长，C 1为中间横截面周长，C 2 为下底面周长，V 为几何体体积，S 0为上底面面积，S 1为中间横截面面积，S 2为下底面面积，h 为高，h 0为斜高或母线长。注：中间横截面为上、下底等距离的截面。） 一、棱柱、棱锥、棱台、圆柱、圆锥、圆台的面积 、体积用统一公式的正确性 1、棱柱： ⑴据棱柱上底周长、下底周长、中间横截面周长相等，即2 1 C C C ==， 可得： 2020210066 )4(6 C h C h C C C h =?= ++，这与课本中的棱柱侧面积公式等同。 以下每个几何体都能推得与课本中相应公式等同，说明这统一公式的正确性。 ⑵据棱柱上底面、下底面、中间横截面相等，可知：2 1 S S S ==，即： h S S S S h S S S h V 2222210)4(6 )4(6 =++= ++= 。 2、棱锥 ⑴设底边长为a 2，边数为n ，斜高为h 0，侧面三角形中位线为a 1，则
不四 s = —+ 爲Mu = =￡￡sin B 2 2 边形 不四 平边 行形 a. b. c. d —各边长險、爲rsi s -面积右、必一对角线 [H^hY^bh + cH 2 H, 曰-面枳 € _ a￡K abc % 4」戸（尹_&）〔戸 _&）（尹_亡） P-三边和之半 s-三角形囲积 艮-三角形外接圆半径 外 切 角 形 直 角 角 形 尸=匚石一刁 ■S _ 血 P V F P-三边和之半 2 -三角形面积 r -三角形内切圆半径 以=胪亠阱弘b -直角边 c = 3十戸? _斜边 1 , "尹占-面积 c -J/ ■n?十2&曰a'b^ -各边长
隅 角 0 ]073t a s - 面积 d -短轴D - 长轴匸-短 半轴 R -长半轴 扇 形 ISO* -°01745^ 亠二喫 2 360 半径 圆心角= 0.008727r^* 弓-面积
正 六 E 体 正 十 _____ L 面 体 正 多 边 形 (六个正方形 ) 口 -边 数 a - 一边之长 R -外接圆半径 r 内切圆半径 e-巒 财之 1D 心角 顶 用 官-面 积 D -周良 tzFhj u 〔教目） F=6a 2 棱顶点 12 3 丁 = / C 数 目） 稜腆点 30 20 正 立 方 体 截 头 直 锥 （十二个五甬形）爲 柱 卩二 20.6457^ r= 7.663 la 5 F = 6a 2 C L □ -边 长 d-对角线长 = 7^" = 1732^1 。=扌心1 +比） 尸=#餉+宀） + s i 十巧 衍“2 —两端周 围的长 ￡ L-S 2 —两端的 面积 $二gk 十邑+ J 远”叼） C* P -宜截断面周长 F = ^/ + 2s h - 高 V = sh 目-底面积
度。下图是个例子：
四、实验结果与分析（源程序及相关说明） 1)#include
平面几何图形的画法 按照能否通用，平面几何图形大致可以分为两类：一类是没有具体尺寸要求的相交线、平行线、角、三角形、四边形等等；另一类则是需要符合题目条件与结论，或有严格尺寸要求的图形。无论哪一类，都可以凭借Word页面的“绘图工具”画出来，再利用Windows自带的“画图”程序进行编辑。下面举两例予以说明，敬请同仁赐教。 例1、如图，在三角形纸片ABC中，∠C=90°，∠A=30°，AC=3，折叠该纸片，使点A 与点B重合，折痕与AB，AC分别相交于点D，E，求折痕DE的长。 〖画法〗： 1、点击“插入”→“形状”，选择直线形，插入一条水平直线和一条竖直直线，如图（1）； 2、右击直线，选“设置对象格式”，如图（2）； 3、在“颜色与线条”里，将两条直线均设置为黑色、0.75磅，如图（3）； 4、将水平直线复制成3条，如图（4）；
5、右击其中一条水平直线，在“设置对象格式”→“大小”→“旋转”右框内，输入数字“30”，如图（5）；这时所选直线顺时针旋转30°，如图（6）； 6、再选择一条水平直线，将其顺时针旋转60°，如图（7），图（8）； 7、插入一条水平直线，设置为黑色、0.75磅，并顺时针旋转120°，如图（9）； 8、按住“Ctrl”键依次点击排列好的每条直线，在“图片工具”里选择“组合”，并且“另存图片”到某个文件夹，如图（10）；
9、在Windows自带的“画图”程序中打开图片，如图（11）； 10、用“橡皮”工具擦掉图形中多余的部分，如图（12）； 11、用“铅笔”工具添加直角符号，并用“铅笔”工具将部分实线改成虚线，如图（13）； 12、用“画图”程序中的文本工具给图形各点添加大写字母，如图（14）； 13、剪切图片，另存到文件夹，如图（15）；
计算几何算法概览 [ 2001-03-23 ] 怒火之袍出处:放飞技术网 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1.矢量的概念 2.矢量加减法 3.矢量叉积 4.折线段的拐向判断 5.判断点是否在线段上 6.判断两线段是否相交 7.判断线段和直线是否相交 8.判断矩形是否包含点 9.判断线段、折线、多边形是否在矩形中 10.判断矩形是否在矩形中 11.判断圆是否在矩形中 12.判断点是否在多边形中 13.判断线段是否在多边形内 14.判断折线是否在多边形内 15.判断多边形是否在多边形内 16.判断矩形是否在多边形内 17.判断圆是否在多边形内 18.判断点是否在圆内 19.判断线段、折线、矩形、多边形是否在圆内 20.判断圆是否在圆内
计算几何算法概览 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 矢量加减法 矢量叉积 折线段的拐向判断 判断点是否在线段上 判断两线段是否相交
判断线段和直线是否相交 判断矩形是否包含点 判断线段、折线、多边形是否在矩形中 判断矩形是否在矩形中 判断圆是否在矩形中 判断点是否在多边形中 判断线段是否在多边形内 判断折线是否在多边形内 判断多边形是否在多边形内 判断矩形是否在多边形内 判断圆是否在多边形内 判断点是否在圆内 判断线段、折线、矩形、多边形是否在圆内判断圆是否在圆内 计算点到线段的最近点
计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质
计算几何常用算法概览 本站原创：怒火之袍一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 三、算法介绍 矢量的概念：
如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量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 )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = （x1,y1），Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P ×Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质P ×Q = - ( Q ×P ) 和P ×( - Q ) = - ( P ×Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的 顺逆时针关系： 若P ×Q > 0 , 则P在Q的顺时针方向。 若P ×Q < 0 , 则P在Q的逆时针方向。 若P ×Q = 0 , 则P与Q共线，但可能同向也可能反向。
正方形 面积：边长×边长 周长：边长×4 长方形 面积：长×宽 周长：（长+宽）*2 平行四边形 面积=底边*高/2 周长=（底+高）×2 三角形 面积S=√p(p-a)(p-b)(p-c), p=（a+b+c）/2,为三角形三边 周长c=a+b+c 梯形 面积=｛（上底+下底）×高｝÷2周长=四边之和 圆形 面积=πR2 周长=2πR （R为半径） 椭圆形 面积=A = PI * 半长轴长 * 半短轴长
周长= 4A * SQRT(1-E^SIN^T)的(0 - π/2)积分, 其中A为椭圆长轴,E为离心率精确计算要用到积分或无穷级数的求和 半圆形 周长=2R(丌+1) 面积=(丌R的平方)/2 正多边形 面积： 正多边形内角计算公式与半径无关 要已知正多边形边数为N 内角和=180(N-2) 半径为R 圆的内接三角形面积公式:(3倍根号3)除以4再乘以R方 外切三角形面积公式:3倍根号3 R方 外切正方形:4R方 内接正方形:2R方 五边形以上的就分割成等边三角形再算 内角和公式——（n-2）*180` 我们都知道已知A(x1,y1)、B(x2,y2)、C(x3,y3)三点的面积公式为 |x1 x2 x3| S(A,B,C) = |y1 y2 y3| * = [(x1-x3)*(y2-y3) - (x2-x3)*(y1-y3)]* |1 1 1 | (当三点为逆时针时为正，顺时针则为负的) 对多边形A1A2A3、、、An(顺或逆时针都可以)，设平面上有任意的一点P，则有：S(A1,A2,A3，、、、,An) = abs(S(P,A1,A2) + S(P,A2,A3)+、、、+S(P,An,A1))
目录 ㈠点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 ㈡线段及直线的基本运算 1. 点与线段的关系 3 2. 求点到线段所在直线垂线的垂足 4 3. 点到线段的最近点 4 4. 点到线段所在直线的距离 4 5. 点到折线集的最近距离 4 6. 判断圆是否在多边形内 5 7. 求矢量夹角余弦 5 8. 求线段之间的夹角 5 9. 判断线段是否相交 6 10.判断线段是否相交但不交在端点处 6 11.求线段所在直线的方程 6 12.求直线的斜率 7 13.求直线的倾斜角 7 14.求点关于某直线的对称点 7 15.判断两条直线是否相交及求直线交点 7 16.判断线段是否相交，如果相交返回交点 7 ㈢多边形常用算法模块 1. 判断多边形是否简单多边形 8 2. 检查多边形顶点的凸凹性 9 3. 判断多边形是否凸多边形 9 4. 求多边形面积 9 5. 判断多边形顶点的排列方向，方法一 10 6. 判断多边形顶点的排列方向，方法二 10 7. 射线法判断点是否在多边形内 10 8. 判断点是否在凸多边形内 11 9. 寻找点集的graham算法 12 10.寻找点集凸包的卷包裹法 13 11.判断线段是否在多边形内 14 12.求简单多边形的重心 15 13.求凸多边形的重心 17 14.求肯定在给定多边形内的一个点 17 15.求从多边形外一点出发到该多边形的切线 18
16.判断多边形的核是否存在 19 ㈣圆的基本运算 1 .点是否在圆内 20 2 .求不共线的三点所确定的圆 21 ㈤矩形的基本运算 1.已知矩形三点坐标，求第4点坐标 22 ㈥常用算法的描述 22 ㈦补充 1．两圆关系： 24 2．判断圆是否在矩形内： 24 3．点到平面的距离： 25 4．点是否在直线同侧： 25 5．镜面反射线： 25 6．矩形包含： 26 7．两圆交点： 27 8．两圆公共面积： 28 9. 圆和直线关系： 29 10. 内切圆： 30 11. 求切点： 31 12. 线段的左右旋： 31 13．公式： 32 代码: /* 需要包含的头文件 */ #include
多面体的体积和表面积 心乱方-边长 1高 尸-底面积 □-底面中线的交点 一个组合三角形的面积 jl -iS?Ξ角形的个数 O-锥底各对角线交直 务F 2 -两平行底面的面粧 Ji-底面间距离 闻-一个爼合梯形的面积 相-组合梯老数 7 = ∣^ + ?÷√η?) ￡ = M +斤4■爲 ^-Cn 厲-对角銭 S-表面耕 加-侧表面积 尺寸符号 心爲1?-边长 0」底面对角线的交点 体积附）底面积（F ） 表面积（小侧表面积（阳 S=6a 2 V = a??* A S = 2(∣z *? + a??+??ft) 51=2?(α + ?) 柱 和 空 心 圆 柱 ∧ 管 F-外半径 1内半径 f-柱壁厚度 P -平均半径 内 外侧面积 圆柱： y = rtS a *? * ft +2∕τfi a ?=-3d??? 空心言圆拄： y r = ∕ACΛa -r a )^3s?ft ^ = 2f rC Λ+r)Λ + 2√Λi -r a ) S=S +? +c)?Λ+2J 7 (Si = (a+if+c)*h
V y = ψ?(j?2 3 + √+?) 5*1 = KHR+r) I= y ∣(R-r)2+h 2 ￡ =址十疔 ( 0+/) y = -jιr? =2W44r? 3 y=^(4ft+rf) = 157f(??+^ ￡ 斜 线 直 圆 柱 ?-≡小高度 ?-盘大高度 T -底面半径 ^-^c?+?>rtf 1?α+J —) cc≤ α S l - πr(? +?) r-廐面半径 卜母线长 +?2 =鈕 球半径 d ?弓定底11直径 A-弓形高 一半径 d-直径 4 3 皿' — L.P V = Lf I f =——=0.5236 护 3 6 S=A f tr 2 = =
算法系列之九：计算几何与图形学有关的几种常用算法（一） 分类：算法系列2011-12-18 23:13 8182人阅读评论(41) 收藏举报 我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机图形学》是必修课，也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍，这种重复劳动虽然意义不大，但是收获很多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收获吧。尽管已经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成现在的我，恐怕再也不会有动力去做这些事情了。 在学习《计算机图形学》之前，总觉得很多东西高深莫测，但实际掌握了之后，却发现其中了无神秘可言，就如同被原始人像神一样崇拜的火却被现代人叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何，但是没有理论数学那么高深莫测，它很有实践性，有时候甚至可以简单到匪夷所思。计算几何是随着计算机和CAD的应用而诞生的一门新兴学科，在国外被称为“计算机辅助几何设计（Computer Aided Geometric Design，CAGD）”。“算法系列”接下来的几篇文章就会介绍一些图形学中常见的计算几何算法（顺便晒晒我的旧代码），都是一些图形学中的基础算法，需要一些图形学的知识和数学知识，但是都不难。不信？那就来看看到底有多难。 本文是第一篇，主要是一些图形学常用的计算几何方法，涉及到向量、点线关系以及点与多边形关系求解等数学知识，还有一些平面几何的基本原理。事先声明一下，文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的，在算法效率和可读性二者的考量上，更注重可读性，有时候为了提高可读性会刻意采取“效率不高”的代码形式，实际工程中使用的代码肯定更紧凑更高效，但是算法原理都是一样的，请读者们对此有正确的认识。 一、判断点是否在矩形内 计算机图形学和数学到底有什么关系？我们先来看几个例子，增加一些感性认识。首先是判断一个点是否在矩形内的算法，这是一个很简单的算法，但是
常见几何图形的作图方法 一、正正多边形画法 1.正六边形（祥讲，重点掌握） （1）已知正六边形对角线长度（即外接圆的直径） 方法1：，用圆规作图。 方法2：用60°—30°三角板配合丁字尺作图。 利用圆规作图利用三角板配合丁字尺作图 （2）已知正六边形的对边距离，用60°—30°三角板配合丁字尺作图。 方法一（外接圆）方法二（内切圆） 已知对边距离用三角板配合丁字尺作图 2.正五边形 已知外接圆画正五形 ３.正N边形画法（以正7边形为例） ⑴画外接圆 ⑵将外接圆直径等分为N等份 ⑶以N点为圆心，以外接圆直径为半径作圆与水平中心线交于点A,B。⑷由A和B分别与奇数（或偶数）分点连线并与外接圆相交，依次连接各交点。
二、斜度和锥度 1.斜度 1）定义：一直线(或平面)相对于另一直线(或平面)的倾斜程度称为斜度。 斜度 = tga= H L = l n = 1:n 2）斜度符号的画法。 3）斜度的画法 做辅助小斜线 4）斜度的标注方法 斜度符号的方向应与被注图形的斜线斜度方向一致。 斜度的标注 2. 锥度 1）锥度的定义 正圆锥底圆直径与圆锥长度之比称为锥度。正圆锥台的锥度则可用两底圆直径之差与锥台长度之比表示。锥度取决于圆锥角的大小，并把比值化为l：n的 形式，即锥度= D L = D-d l =1：n=2tg (a／2)。 2）锥度符号的画法。3）锥度的画法 做辅助小圆锥 4）锥度的标注
锥度符号的方向应与被注图形的斜线斜度方向一致。 锥度的标注 三、圆弧连接（重点讲解，理解原理，掌握画法：确定连结圆弧的园心与连结点） 1．圆弧连接的概念 用已知半径的圆弧光滑连接(即相切)两已知线段(直线或圆弧)，称为圆弧连接，这段已知半径的圆弧称为连接弧。 2．圆弧连接的三种形式 3. 圆弧连接的作图原理（动画见课件） 4.各种圆弧连接的作图方法 画连接弧前，必须求出其圆心和切点位置。 （仔细讲解作图原理和连接圆弧圆心和切点的求法，强调在理解的基础上记住 结论） 例1：用已知半径的圆弧连接两直线。 已知半径的圆弧连接两直线 例2：用已知半径的圆弧连接直线和圆弧。 作图方法：
引用C++计算几何函数库2009-12-10 15:33:23| 分类：默认分类| 标签：|字号大中小订阅. 引用 wangzecheng125 的C++计算几何函数库 1. 常量定义和包含文件 2. 基本数据结构 3. 精度控制 ㈠点的基本运算 1. 平面上两点之间距离 2. 判断两点是否重合 3. 矢量叉乘 4. 矢量点乘 5. 判断点是否在线段上 6. 求一点饶某点旋转后的坐标 7. 求矢量夹角 ㈡线段及直线的基本运算 1. 点与线段的关系 2. 求点到线段所在直线垂线的垂足 3. 点到线段的最近点 4. 点到线段所在直线的距离 5. 点到折线集的最近距离 6. 判断圆是否在多边形内 7. 求矢量夹角余弦 8. 求线段之间的夹角 9. 判断线段是否相交 10.判断线段是否相交但不交在端点处 11.求点关于某直线的对称点 12.判断两条直线是否相交及求直线交点 13.判断线段是否相交，如果相交返回交点㈢多边形常用算法模块 1. 判断多边形是否简单多边形 2. 检查多边形顶点的凸凹性 3. 判断多边形是否凸多边形 4. 求多边形面积 5. 判断多边形顶点的排列方向 7. 射线法判断点是否在多边形内 8. 判断点是否在凸多边形内 9. 寻找点集的graham算法 10.寻找点集凸包的卷包裹法11.凸包MelkMan算法的实现 12. 凸多边形的直径 13.求凸多边形的重心 ================================ ================================ =========== 导引 /* 需要包含的头文件*/ #include
几何图形初步 第一节几何图形 认识立体图形 （1）几何图形：从实物中抽象出的各种图形叫几何图形．几何图形分为立体图形和平面图形． （2）立体图形：有些几何图形（如长方体、正方体、圆柱、圆锥、球等）的各部分不都在同一个平面内，这就是 立体图形． （3）重点和难点突破： 结合实物，认识常见的立体图形，如：长方体、正方体、圆柱、圆锥、球、棱柱、棱锥等．能区分立体图形与平面 图形，立体图形占有一定空间，各部分不都在同一平面内． 点、线、面、体 1）体与体相交成面，面与面相交成线，线与线相交成点． （2）从运动的观点来看点动成线，线动成面，面动成体．点、线、面、体组成几何图形，点、线、面、体的运动 组成了多姿多彩的图形世界． （3）从几何的观点来看点是组成图形的基本元素，线、面、体都是点的集合． （4）长方体、正方体、圆柱、圆锥、球、棱柱、棱锥等都是几何体，几何体简称体． （5）面有平面和曲面之分，如长方体由6个平面组成，球由一个曲面组成． 欧拉公式 （1）简单多面体的顶点数V、面数F及棱数E间的关系为：V+F-E=2．这个公式叫欧拉公式．公式描述了简单多 面体顶点数、面数、棱数特有的规律． （2）V+F-E=X（P），V是多面体P的顶点个数，F是多面体P的面数，E是多面体P的棱的条数，X（P）是多面体P的欧拉示性数． 几何体的表面积 （1）几何体的表面积=侧面积+底面积（上、下底的面积和） （2）常见的几种几何体的表面积的计算公式 ①圆柱体表面积：2πＲ2+2πRh （R为圆柱体上下底圆半径，h为圆柱体高） ②圆锥体表面积：πｒ2+nπ（h2+r2）360（r为圆锥体低圆半径，h为其高，n为圆锥侧面展开图中扇形的圆 心角） ③长方体表面积：2（ab+ah+bh）（a为长方体的长，b为长方体的宽，h为长方体的高） ④正方体表面积：6a2 （a为正方体棱长 认识平面图形 （1）平面图形：一个图形的各部分都在同一个平面内，如：线段、角、三角形、正方形、圆等． （2）重点难点突破： 通过以前学过的平面图形：三角形、长方形、正方形、梯形、圆，了解它们的共性是在同一平面内． 几何体的展开图 （1）多数立体图形是由平面图形围成的．沿着棱剪开就得到平面图形，这样的平面图形就是相应立体图形的展开 图．同一个立体图形按不同的方式展开，得到的平面展开图是不一样的，同时也可看出，立体图形的展开图是平面 图形． （2）常见几何体的侧面展开图： ①圆柱的侧面展开图是长方形．②圆锥的侧面展开图是扇形．③正方体的侧面展开图是长方形．④三棱柱的侧面展 开图是长方形． （3）立体图形的侧面展开图，体现了平面图形与立体图形的联系．立体图形问题可以转化为平面图形问题解决． 从实物出发，结合具体的问题，辨析几何体的展开图，通过结合立体图形与平面图形的转化，建立空间观念，是解 决此类问题的关键． 展开图折叠成几何提体 通过结合立体图形与平面图形的相互转化，去理解和掌握几何体的展开图，要注意多从实物出发，然后再从给定的 图形中辨认它们能否折叠成给定的立体图形
实验名称计算几何算法的实现 姓名系院专业计算机与信 息 班级学号 实验日期2012年11月8日指导教师成绩 一、实验目的和要求 (1) 理解线段的性质、叉积和有向面积。 (2) 掌握寻找凸包的算法。 (3) 综合运用计算几何和搜索中的知识求解有关问题。 二、实验预习内容 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的 端点重合，思考这样的情况怎么办。 (4) 房间最短路问题： 给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界 固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间， 输出最短路的长度。 三实验项目摘要 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。 (4) 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。下图是个例子：
计算几何常用算法 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。 作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸 多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 矢量加减法 矢量叉积 折线段的拐向判断 判断点是否在线段上 判断两线段是否相交 判断线段和直线是否相交 判断矩形是否包含点 判断线段、折线、多边形是否在矩形中 判断矩形是否在矩形中 判断圆是否在矩形中 判断点是否在多边形中 判断线段是否在多边形内 判断折线是否在多边形内 判断多边形是否在多边形内 判断矩形是否在多边形内 判断圆是否在多边形内 判断点是否在圆内 判断线段、折线、矩形、多边形是否在圆内 判断圆是否在圆内 计算点到线段的最近点 计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法
三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量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 )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P =（x1,y1），Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积 即：P×Q = x1*y2 - x2*y1，其结果是一个标量。 显然有性质P×Q = - (Q×P)和P×( -Q ) = - ( P×Q)。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： 若P ×Q > 0 , 则P在Q的顺时针方向。若P ×Q < 0 , 则P在Q的逆时针方向。若P ×Q = 0 , 则P与Q共线，但可能同向也可能反向。 折线段的拐向判断： 折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) ×(p1 - p0)的符号便可以确定折线段的拐向： 若(p2 - p0) ×(p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。 若(p2 - p0) ×(p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。 若(p2 - p0) ×(p1 - p0) = 0,则p0、p1、p2三点共线。 具体情况可参照下图： 判断点是否在线段上： 设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) ×( P2 - P1 ) = 0 且Q 在以P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现： ON-SEGMENT(pi,pj,pk) if min(xi,xj)<=xk<=max(xi,xj) and min(yi,yj)<=yk<=max(yi,yj) then return true; else return false; 特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。