计算几何基础ppt课件.ppt
70页
ACM ACM 程序设计程序设计计算机学院计算机学院 刘春英刘春英 下周，下周，调课一周… 每周一星〔每周一星〔4〕：〕：06057229许璟亮许璟亮 第五讲第五讲计算几何初步计算几何初步(Computational Geometry Basic) 第一单元线 段 属 性 思索：1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区别是什么？ 特别提示：l以上引见的线段的三个属性，是计算几何的根底，在很多方面都有运用，比如求凸包等等，请务必掌握！ 第二单元多边形面积 和重心 根本问题〔1〕：l给定一个简单多边形，求其面积l输入：多边形〔顶点按逆时针顺序陈列〕l输出：面积S 思索如以下图形： Any good idea? 先讨论最简单的多边形——三角形 三角形的面积：l在解析几何里， △ABC的面积可以经过如下方法求得：l点坐标 => 边长 => 海伦公式 => 面积 思索：此方法的缺陷：思索：此方法的缺陷：计算量大精度损失更好的方法？ 计算几何的方法：计算几何的方法：l在计算几何里，我们知道，△ABC的面积就是“向量AB〞和“向量AC〞两个向量叉积的绝对值的一半。
其正负表示三角形顶点是在右手系还是左手系ABC成左手系，负面积ABC成右手系，正面积BCACBA 大功告成：大功告成：lArea(A,B,C)= 1/2 * (↑AB) × (↑AC)l =∣ ∣/2l特别留意：l 以上得到是有向面积〔有正负〕！ Xb – X a Yb –Y aXc – X a Yc –Y a 凸多边形的三角形剖分l很自然地，我们会想到以 P1为扇面中心，衔接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：l A=sigma(Ai) (i=1…N-2)P1P2P3P4P5P6A1A2A3A4 凹多边形的面积？P1P4P3P2 依然成立！！！依然成立！！！多边形面积公式：A=sigma(Ai) (i=1…N-2)结论： “有向面积〞A比“面积〞S其实更本质！ 恣意点为扇心的三角形剖分：恣意点为扇心的三角形剖分：l我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？l比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。
P0P1P2P6P5P4P3 前面的三角剖分显然对于多边形内部恣意一点都是适宜的！我们可以得到：A=sigma(Ai) 〔 i=1…N 〕即：A= sigma∣ ∣/2 〔 i=1…N 〕 Xi – X0 Yi –Y0X(i+1) – X0 Y(i+1) –Y0 能不能把扇心移到多边形以外呢？能不能把扇心移到多边形以外呢？P0P1P2P3P4 既然内外都可以，为什么不设既然内外都可以，为什么不设P0为为坐标原点呢？坐标原点呢？OP1P2P3P4如今的公式？ 简化的公式：A=sigma∣ ∣/2〔 i=1…N 〕 Xi YiX(i+1) Y(i+1)面积问题面积问题搞定！搞定！ 根本问题〔2〕：l给定一个简单多边形，求其重心l输入：多边形〔顶点按逆时针顺序陈列〕l输出：重心点C 从三角形的重心谈起：从三角形的重心谈起：三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3可以推行否？Sigma(xi)/N , sigma(yi)/N (i=1…N) ??? 看看一个特例：看看一个特例：. 缘由：缘由：l错误的推行公式是“质点系重心公式〞，即假设以为多边形的质量仅分布在其顶点上，且均匀分布，那么这个公式是对的。
l但是，如今多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！ Solution:l剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而如今质量仅仅分布在这N个重心点上〔等假变换〕，这时候就可以利用刚刚的质点系重心公式了l不过，要略微改一改，改成加权平均数，由于质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积〔有向面积！〕，——这就是权！ 公式：公式：lC=sigma(Ai * Ci) / A (i=1…N)lCi=Centroid(△ O Pi Pi+1)l = (O + ↑Pi +↑Pi+1 )/3lC=sigma((↑Pi +↑Pi+1)(↑Pi ×↑Pi+1) ) /(6A) 全部搞全部搞定！定！ 第三单元第三单元凸包( Convex Hull ) 凸包模板：凸包模板：//xiaoxia版#include
