平面几何常用算法概述.ppt

* * 前面的三角剖分显然对于多边形内部任意一点都是合适的！ 我们可以得到： A=sigma(Ai) （ i=1…N ） 即：A=sigma ∣ ∣/2 （ i=1…N ） Xi – X0 Yi –Y0 X(i+1) – X0 Y(i+1) –Y0 * * 能否把扇心移到多边形以外呢？ P0 P1 P2 P3 P4 * * 既然内外都可以，为什么不设P0为坐标原点呢？ O P1 P2 P3 P4 现在的公式？ * * 简化的公式： A=sigma∣ ∣/2 （ i=1…N ） Xi Yi X(i+1) Y(i+1) * * 基本问题（2）： 给定一个简单多边形，求其重心。 输入：多边形（顶点按逆时针顺序排列） 输出：重心点C 求任意多边形的重心 1、质量集中在顶点上， n个顶点坐标为(xi,yi)，质量为mi，则重心 　　 X = ∑( xi×mi ) / ∑mi 　　Y = ∑( yi×mi ) / ∑mi 　 2、若每个点的质量相同则 　X = ∑xi / n 　　Y = ∑yi / n 2、质量分布均匀 　 3、特殊地，质量均匀的三角形重心： 　X = ( x0 + x1 + x2 ) / 3 　　Y = ( y0 + y1 + y2 ) / 3 * 将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，则面积就是质量】 因为质量都集中在重心 所以把所有求出来的重心按逆时针连接起来又是一个多边形 但是这个多边形的质量集中在顶点上 所以可以利用上面公式进行计算 * 求质量分布均匀的n边形重心 #include cstdio #include cstdlib #include iostream using namespace std; const int N = 1000000; struct point { double x; double y; } p[N], g; //p数组保存多边形的顶点 double crossProd(point A, point B, point C) //计算三角形ABC有向面积 { return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x); } void compGravity(int n) //求重心g { point tmp; double sumArea, area; sumArea = 0; g.x = g.y = 0; for (int i=2; in; ++i) { area = crossProd(p[0], p[i-1], p[i]); sumArea += area; tmp.x = p[0].x + p[i-1].x + p[i].x; tmp.y = p[0].y + p[i-1].y + p[i].y; g.x += tmp.x * area; g.y += tmp.y * area; } g.x /= (sumArea * 3.0); g.y /= (sumArea * 3.0); } * 二、凸包的求解 * 二.凸包的求法(Graham算法) 凸包的定义： 你可以这样想象：平面上有很多根钉子,你的手里有一根橡皮环,你用橡皮环把这些钉子都套起来，然后松手，橡皮环所形成的图形就是这些钉子的一个凸包（如下图） Graham扫描法： 1.选则p0作为y坐标最小的点，如果有多个这样的点，则选择x最小的。 2.剩余的点根据他们相对于p0的极角的大小从小到大排序，设排序后的点依次为P[0....n]。 3. 设置一个栈，P0,P1,P2先入栈。 4.对于 P[3..n]的每个点，若它与栈顶的两个点不构成向左转的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈； 所有点处理完之后栈中保存的点就是凸包了。 思考： 如何对这些极角排序？ 用atan函数？显然会有精度问题，不准确 回忆一下以前讲的向量的叉积。 * p0 p1 p2 如何知道p2的极角就比p1大呢？ 再思考一下如何判断左转还是右转？ 自然也是叉积。。。 显然只需要向量p0p1和向量p0p2做叉积就可以了 ，如果大于0则p2的极角比p1大。 * * * * * * * * * * * * * * * * * * * * * * * * * * * graham算法模板 #includ