平面几何常用算法

1、平面几何常用算法2014.8.21 1.计算几何基础2022-1-142.凸包问题3.旋转卡壳计算几何基础2022-1-141、向量（矢量）的概念 矢量：有方向的线段，即P1和P2的顺序是有关系的，记为： 21PP21PP如果P1是坐标原点，则 又称为向量P2。 矢量的斜率：既然矢量是有方向的，那么矢量的斜率k就是有正负之分的，具体如下： III计算几何基础计算几何基础 1、向量（矢量）的概念 设 =a，则有向线段 的长度叫做向量（矢量）a的长度或模，记作|a|。 OAOA夹角：两个非0矢量a、b，在空间任取一点O，作 =a， =b，则角AOB叫做矢量a与b的夹角，记作。若=/2，则称a与b互

2、相垂直，记作ab。 OAOB计算几何基础计算几何基础 计算几何基础计算几何基础 2、矢量的加减法 以点O为起点、A为端点作矢量a，以点A为起点、B为端点作矢量b，则以点O为起点、B为端点的矢量称为a与b的和a+b，如下中图。 若从A点作 ，要求 的模等于|b|，方向与b相反，即 =-b，则以O为起点、B为端点的矢量称为a与b的差a-b，如下右图。ABABAB3、矢量的分解定理： 如果平面两个矢量a,b，对任一矢量p，一定存在一个且仅一个有序实数组x,y，使得：p=xa+yb。 含义与物理上的合力或力的分解一样。 形式上看，相当于长方形的对角线。 计算几何基础计算几何基础 4、矢量的数量积（点乘

3、） 两个矢量的数量积是一个数，大小等于这两个矢量的模的乘积再乘以它们夹角的余弦。即： ab|a|b|cos 数量积等于两个矢量的对应支量乘积之和。即： abaxbxayby 计算几何基础计算几何基础 4、矢量的数量积（点乘） 数量积的性质： ae=|a|e|cos=|a|cos ab 等价于 ab0,即axbxayby=0 自乘：|a|2 aa 结合律：（a）b = (ab) 交换律：ab ba 分配律：a(b + c) ab + ac计算几何基础计算几何基础 5、矢量的矢量积（叉乘、叉积） 矢量积的一般含义：两个矢量a和b的矢量积是一个矢量，记作ab，其模等于由a和b作成的平行四边形的面积，

4、方向与平行四边形所在平面垂直，当站在这个方向观察时，a逆时针转过一个小于的角到达b的方向。这个方向也可以用物理上的右手螺旋定则判断：右手四指弯向由A转到B的方向（转过的角小于），拇指指向的就是矢量积的方向。 计算几何基础计算几何基础 叉积的等价定义（更实用），把叉积定义为一个矩阵的行列式： 5、矢量的矢量积（叉乘、叉积） 如图，如果 为正数，则相对原点(0,0)来说，P1在P2的顺时针方向；如果 为负数，则P1在P2的逆时针方向。如果 =0，则P1和P2模相等且共线，方向相同或相反。21pp 21pp 21pp 计算几何基础计算几何基础 如图，如果 为正数，则相对原点(0,0)来说，P1在P2

5、的顺时针方向；如果 为负数，则P1在P2的逆时针方向。如果 =0，则P1和P2模相等且共线，方向相同或相反。21pp 21pp 21pp 9、矢量的矢量积（叉乘、叉积） 探讨一个重要问题：给定两个矢量： 和 ，对它们的公共端点P0来说，判断 是否在 的顺时针方向。 10PP20PP20PP10PP方法：如图，把P0作为原点，得出向量P1=P1-P0和P2=P2-P0，因此，这两个向量的叉积为：如果该叉积为正， 则 在 的顺时针方向，如果为负，则 在 的逆时针方向。如果等于0，则P0，P1，P2三点共线。 )()()()(010202010201yyxxyyxxpppp10PP20PP20PP1

6、0PP计算几何基础计算几何基础 13p1p2p4p3显然，只要p1,p2两点在线段p3p4的两边，并且p3,p4在线段p1p2的两边，那么这两条线段必然相交思考：如何判断两点是否在一条线段的两边？这样只要d1*d20 并且 d3*d40 则p1p2和p3p4这两条线段必然相交注意：若是等于0则要判断对应的点是否在线段上。 判断两条线段是否相交判断两条线段是否相交计算几何基础计算几何基础 以下定义的以下定义的d绝对值为向量的模长，正负为向量的方绝对值为向量的模长，正负为向量的方向。向。判断线段是否相交的模板（hdu1086）include using namespace std;struct p

7、oint double x,y;struct segment point begin,end;double min(double x,double y) return xy?x:y;bool onsegment(point pi,point pj,point pk) /判断点pk是否在线段pi pj上 if(min(pi.x,pj.x)=pk.x&pk.x=max(pi.x,pj.x) if(min(pi.y,pj.y)=pk.y&pk.y=max(pi.y,pj.y) return true; return false;double direction(point pi,po

8、int pj,point pk) /计算向量pkpi和向量pjpi的叉积 return (pi.x-pk.x)*(pi.y-pj.y)-(pi.y-pk.y)*(pi.x-pj.x);bool judge(point p1,point p2,point p3,point p4) /判断线段p1p2和p3p4是否相交 double d1 = direction(p3,p4,p1); double d2 = direction(p3,p4,p2); double d3 = direction(p1,p2,p3); double d4 = direction(p1,p2,p4); if(d1*d20

9、&d3*d40) return true; if(d1=0&onsegment(p3,p4,p1) return true; if(d2=0&onsegment(p3,p4,p2) return true; if(d3=0&onsegment(p1,p2,p3) return true; if(d4=0&onsegment(p1,p2,p4) return true; return false;二.判断点是否在多边形内方法一：射线法仔细观察：在多边形内的点和不在多边形内的点向某个方向引一条射线，这些射线和多边形的交点的个数有什么特点？结论：如果从该点引一

10、条射线，这条射线和多边形的交点个数为奇数，则该点在多边形里面，若为偶数，则该点在多边形外面。由于有更好更容易实现的弧长法，就不贴射线法的模板了。弧长 法（转角法）：将坐标原点平移到被测点P,这个新坐标系将平面划分为4个象限,对每个多边形顶点Pi,只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点Pi分析Pi和Pi+1,有下列四种情况:、 (1) Pi+1和Pi在同一象限，此时弧长和不变; (1) Pi+1在Pi的下一象限,此时弧长和加/2; (2) Pi+1在Pi的上一象限,此时弧长和减/2; (3) Pi+1在Pi的相对象限,首先计算f=pi+1.y*pi.x-pi+1.x*pi.y(叉

11、积),若f=0,则点在多边形上;若f0,弧长和加.最后对算出的代数和和上述的情况一样判断即可.实现的时候要注意:若被测点和多边形的顶点重合时要特殊处理.具体实现的时候取x=0 y=0 作为第一象限 x=0 作为第二象限 x0 y=0 y0 作为第四象限2022-1-14S = -pi/2-pi/2+0-pi/2-pi/2 = -2*pi 弧长法模板（zju1081）2022-1-14struct point int x,y;pMAX;bool inpolygon(point t,int n)/t为需要判断的点,n为多边形点的个数 int i,sum = 0;/用来保存弧长和 pn = p0;

12、/因为第一个点和最后一个点的象限关系也要判断 for(i=0;i=0 ? ( p0.y=0?0:3 ) : ( p0.y=0?1:2 ) ;/计算第一个点的象限 for(i=1;i=n;i+) if(!pi.x&!pi.y) break;/多边形的一个顶点就是被测点 int f = pi.y*pi-1.x-pi.x*pi-1.y; /做叉积 if(!f&pi-1.x*pi.x=0&pi-1.y*pi.y=0 ? ( pi.y=0?0:3 ) : ( pi.y=0?1:2 ); / 计算象限 if(t2=(t1+1)%4) sum+=1; /Pi+1在Pi的下一象限,此时

13、弧长和加/2; else if(t2=(t1+3)%4) sum-=1; /Pi+1在Pi的上一象限,此时弧长和减/2; else if(t2=(t1+2)%4) /Pi+1在Pi的相对象限 if(f0) sum+=2; else sum-=2; t1 = t2; for(int j=0;jn;j+) /恢复坐标 pj.x+=t.x; pj.y+=t.y; if(i 边长 = 海伦公式 = 面积2022-1-1424思考：此方法的缺点：思考：此方法的缺点：计算量大精度损失更好的方法？2022-1-1425计算几何的方法：计算几何的方法： 在计算几何里，我们知道，ABC的面积就是“向量AB”和“

14、向量AC”两个向量叉积的绝对值的一半。其正负用右手螺旋定则判断负面积正面积BCACBA2022-1-1426大功告成：大功告成： Area(A,B,C)= 1/2 * (AB) (AC) = /2特别注意： 以上得到是有向面积（有正负）有向面积（有正负）！ Xb X a Yb Y aXc X a Yc Y a2022-1-1427凸多边形的三角形剖分凸多边形的三角形剖分 很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： A=sigma(Ai) (i=1N-2)P1P2P3P4P5P6A1A2A3A42

15、022-1-1428凹多边形的面积？凹多边形的面积？P1P4P3P22022-1-1429依然成立！依然成立！多边形面积公式：A=sigma(Ai) (i=1N-2)结论： “有向面积”A比“面积”S其实更本本质质！2022-1-1430任意点为扇心的三角形剖分任意点为扇心的三角形剖分： 我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？ 比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P0P1P2P6P5P4P32022-1-1431前面的三角剖分显然对于多边形内部任前面的三角剖分显然对于多边形内部任意一点都是合适的！意一点都是合适的！我们可以得到：A=sig

16、ma(Ai) （ i=1N ）即：A=sigma /2 （ i=1N ） Xi X0 Yi Y0X(i+1) X0 Y(i+1) Y02022-1-1432能否把扇心移到多边形以外呢？能否把扇心移到多边形以外呢？P0P1P2P3P42022-1-1433既然内外都可以，为什么不设既然内外都可以，为什么不设P0为坐标原点呢？为坐标原点呢？OP1P2P3P4现在的公式？2022-1-1434简化的公式：简化的公式：A=sigma /2（ i=1N ） Xi YiX(i+1) Y(i+1)2022-1-1435基本问题（基本问题（2）：）：给定一个简单多边形，求其重心。给定一个简单多边形，求其重心。

17、输入输入：多边形（顶点按逆时针顺：多边形（顶点按逆时针顺序排列）序排列）输出输出：重心点：重心点C C求任意多边形的重心 1、质量集中在顶点上， n个顶点坐标为(xi,yi)，质量为mi，则重心 X = ( ximi ) / mi Y = ( yimi ) / mi 2、若每个点的质量相同则 X = xi / n Y = yi / n 2、质量分布均匀 3、特殊地，质量均匀的三角形重心：X = ( x0 + x1 + x2 ) / 3 Y = ( y0 + y1 + y2 ) / 3 2022-1-14 将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，

18、则面积就是质量】 因为质量都集中在重心 所以把所有求出来的重心按逆时针连接起来又是一个多边形 但是这个多边形的质量集中在顶点上 所以可以利用上面公式进行计算2022-1-14求质量分布均匀的n边形重心#include #include #include using namespace std;const int N = 1000000;struct point double x; double y; pN, g; /p数组保存多边形的顶点double crossProd(point A, point B, point C) /计算三角形ABC有向面积 return (B.x-A.x)*(C.y

19、-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(p0, pi-1, pi); sumArea += area; tmp.x = p0.x + pi-1.x + pi.x; tmp.y = p0.y + pi-1.y + pi.y; g.x += tmp.x * area; g.y += tmp.y * area; g.x /= (

20、sumArea * 3.0); g.y /= (sumArea * 3.0);2022-1-14二、凸包的求解2022-1-14二.凸包的求法(Graham算法)凸包的定义：你可以这样想象：平面上有很多根钉子,你的手里有一根橡皮环,你用橡皮环把这些钉子都套起来，然后松手，橡皮环所形成的图形就是这些钉子的一个凸包（如下图）Graham扫描法：1.选则p0作为y坐标最小的点，如果有多个这样的点，则选择x最小的。2.剩余的点根据他们相对于p0的极角的大小从小到大排序，设排序后的点依次为P0.n。3. 设置一个栈，P0,P1,P2先入栈。4.对于 P3.n的每个点，若它与栈顶的两个点不构成向左转的关系

21、,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈； 所有点处理完之后栈中保存的点就是凸包了。 思考：如何对这些极角排序？用atan函数？显然会有精度问题，不准确回忆一下以前讲的向量的叉积。2022-1-14p0p1p2如何知道p2的极角就比p1大呢？再思考一下如何判断左转还是右转？自然也是叉积。显然只需要向量p0p1和向量p0p2做叉积就可以了 ，如果大于0则p2的极角比p1大。2022-1-14432022-1-14442022-1-14452022-1-14462022-1-14472022-1-14482022-1-14492022-1-14502022-1-14512022-1-

22、14522022-1-14532022-1-14542022-1-14552022-1-14graham算法模板#include #include #include using namespace std; const int MAXN = 105; const double eps = 1e-8;struct Point int x; int y;Point pMAXN; / 保存输入结点 Point stMAXN; / 保存凸包结点，把que当一个栈来使用int top; / 记录栈顶位置double dis(Point a, Point b)/ 求a, b两点距离 return sqrt(double(a.x-b.x)*(a.