平面几何常用算法

平面几何常用算法2014.8.211.计算几何基础2023/2/12.凸包问题3.旋转卡壳计算几何基础2023/2/11、向量（矢量）的概念①矢量：有方向的线段，即P1和P2的顺序是有关系的，记为：如果P1是坐标原点，则又称为向量P2。②矢量的斜率：既然矢量是有方向的，那么矢量的斜率k就是有正负之分的，具体如下：IIIⅢⅣ计算几何基础1、向量（矢量）的概念③设=a，则有向线段的长度叫做向量（矢量）a的长度或模，记作|a|。④夹角：两个非0矢量a、b，在空间任取一点O，作=a，=b，则角∠AOB叫做矢量a与b的夹角，记作<a，b>。若<a，b>=π/2，则称a与b互相垂直，记作a⊥b。计算几何基础计算几何基础2、矢量的加减法

以点O为起点、A为端点作矢量a，以点A为起点、B为端点作矢量b，则以点O为起点、B为端点的矢量称为a与b的和a+b，如下中图。

若从A点作，要求的模等于|b|，方向与b相反，即

=-b，则以O为起点、B’为端点的矢量称为a与b的差a-b，如下右图。3、矢量的分解定理：如果平面两个矢量a,b，对任一矢量p，一定存在一个且仅一个有序实数组x,y，使得：p=xa+yb。含义与物理上的合力或力的分解一样。

形式上看，相当于长方形的对角线。

计算几何基础4、矢量的数量积（点乘）

两个矢量的数量积是一个数，大小等于这两个矢量的模的乘积再乘以它们夹角的余弦。即：

a·b＝|a||b|cos<a,b>

数量积等于两个矢量的对应支量乘积之和。即：

a·b＝axbx＋ayby

计算几何基础4、矢量的数量积（点乘）

数量积的性质：①

a·e=|a||e|cos<a,e>=|a|cos<a,e>②

a⊥b等价于a·b＝0,即axbx＋ayby=0③

自乘：|a|2＝a·a④

结合律：（λ·a）·b=λ(a·b)⑤

交换律：a·b＝b·a⑥

分配律：a·(b+c)＝a·b+a·c计算几何基础5、矢量的矢量积（叉乘、叉积）①矢量积的一般含义：两个矢量a和b的矢量积是一个矢量，记作a×b，其模等于由a和b作成的平行四边形的面积，方向与平行四边形所在平面垂直，当站在这个方向观察时，a逆时针转过一个小于π的角到达b的方向。这个方向也可以用物理上的右手螺旋定则判断：右手四指弯向由A转到B的方向（转过的角小于π），拇指指向的就是矢量积的方向。

计算几何基础②叉积的等价定义（更实用），把叉积定义为一个矩阵的行列式：5、矢量的矢量积（叉乘、叉积）如图，如果为正数，则相对原点(0,0)来说，P1在P2的顺时针方向；如果为负数，则P1在P2的逆时针方向。如果=0，则P1和P2模相等且共线，方向相同或相反。计算几何基础如图，如果为正数，则相对原点(0,0)来说，P1在P2的顺时针方向；如果为负数，则P1在P2的逆时针方向。如果=0，则P1和P2模相等且共线，方向相同或相反。9、矢量的矢量积（叉乘、叉积）③探讨一个重要问题：给定两个矢量：和，对它们的公共端点P0来说，判断是否在的顺时针方向。方法：如图，把P0作为原点，得出向量P1’=P1-P0和P2’=P2-P0，因此，这两个向量的叉积为：如果该叉积为正，则在的顺时针方向，如果为负，则在的逆时针方向。如果等于0，则P0，P1，P2三点共线。计算几何基础13p1p2p4p3显然，只要p1,p2两点在线段p3p4的两边，并且p3,p4在线段p1p2的两边，那么这两条线段必然相交思考：如何判断两点是否在一条线段的两边？这样只要d1*d2<0并且d3*d4<0则p1p2和p3p4这两条线段必然相交注意：若是等于0则要判断对应的点是否在线段上。判断两条线段是否相交计算几何基础以下定义的d绝对值为向量的模长，正负为向量的方向。判断线段是否相交的模板（hdu1086）include<iostream>usingnamespacestd;structpoint{doublex,y;};structsegment{pointbegin,end;};doublemin(doublex,doubley){returnx<y?x:y;}doublemax(doublex,doubley){returnx>y?x:y;}boolonsegment(pointpi,pointpj,pointpk)//判断点pk是否在线段pipj上{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)){returntrue;}}returnfalse;}doubledirection(pointpi,pointpj,pointpk)//计算向量pkpi和向量pjpi的叉积{return(pi.x-pk.x)*(pi.y-pj.y)-(pi.y-pk.y)*(pi.x-pj.x);}booljudge(pointp1,pointp2,pointp3,pointp4)//判断线段p1p2和p3p4是否相交{doubled1=direction(p3,p4,p1);doubled2=direction(p3,p4,p2);doubled3=direction(p1,p2,p3);doubled4=direction(p1,p2,p4);if(d1*d2<0&&d3*d4<0)returntrue;if(d1==0&&onsegment(p3,p4,p1))returntrue;if(d2==0&&onsegment(p3,p4,p2))returntrue;if(d3==0&&onsegment(p1,p2,p3))returntrue;if(d4==0&&onsegment(p1,p2,p4))returntrue;returnfalse;}二.判断点是否在多边形内方法一：射线法仔细观察：在多边形内的点和不在多边形内的点向某个方向引一条射线，这些射线和多边形的交点的个数有什么特点？结论：如果从该点引一条射线，这条射线和多边形的交点个数为奇数，则该点在多边形里面，若为偶数，则该点在多边形外面。由于有更好更容易实现的弧长法，就不贴射线法的模板了。弧长法（转角法）：将坐标原点平移到被测点P,这个新坐标系将平面划分为4个象限,对每个多边形顶点P[i],只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点P[i]分析P[i]和P[i+1],有下列四种情况:、(1)P[i+1]和P[i]在同一象限，此时弧长和不变;(1)P[i+1]在P[i]的下一象限,此时弧长和加π/2;(2)P[i+1]在P[i]的上一象限,此时弧长和减π/2;(3)P[i+1]在P[i]的相对象限,首先计算f=p[i+1].y*p[i].x-p[i+1].x*p[i].y(叉积),若f=0,则点在多边形上;若f<0,弧长和减π;若f>0,弧长和加π.最后对算出的代数和和上述的情况一样判断即可.实现的时候要注意:若被测点和多边形的顶点重合时要特殊处理.具体实现的时候取x>=0y>=0作为第一象限x<0y>=0作为第二象限x<0y<0作为第三象限x>=0y<0作为第四象限2023/2/1S=-pi/2-pi/2+0-pi/2-pi/2=-2*pi弧长法模板（zju1081）2023/2/1structpoint{intx,y;}p[MAX];boolinpolygon(pointt,intn)//t为需要判断的点,n为多边形点的个数{inti,sum=0;//用来保存弧长和

p[n]=p[0];//因为第一个点和最后一个点的象限关系也要判断

for(i=0;i<=n;i++)//因为判断的点要作为坐标原点

{p[i].x-=t.x;p[i].y-=t.y;}intt1=p[0].x>=0?(p[0].y>=0?0:3):(p[0].y>=0?1:2);//计算第一个点的象限

for(i=1;i<=n;i++){if(!p[i].x&&!p[i].y)break;//多边形的一个顶点就是被测点

intf=p[i].y*p[i-1].x-p[i].x*p[i-1].y;//做叉积

if(!f&&p[i-1].x*p[i].x<=0&&p[i-1].y*p[i].y<=0)break;//点在边上

intt2=p[i].x>=0?(p[i].y>=0?0:3):(p[i].y>=0?1:2);//计算象限

if(t2==(t1+1)%4)sum+=1;//P[i+1]在P[i]的下一象限,此时弧长和加π/2;

elseif(t2==(t1+3)%4)sum-=1;//P[i+1]在P[i]的上一象限,此时弧长和减π/2;

elseif(t2==(t1+2)%4)//P[i+1]在P[i]的相对象限

{if(f>0)sum+=2;elsesum-=2;}t1=t2;}for(intj=0;j<n;j++)//恢复坐标

{p[j].x+=t.x;p[j].y+=t.y;}if(i<=n||sum)returntrue;elsereturnfalse;}2023/2/119多边形面积和重心2023/2/120基本问题（1）：给定一个简单多边形，求其面积。输入：多边形（顶点按逆时针顺序排列）输出：面积S2023/2/121思考如下图形：2023/2/122先看最简单的多边形——三角形2023/2/123三角形的面积：在解析几何里，△ABC的面积可以通过如下方法求得：点坐标=>边长=>海伦公式=>面积2023/2/124思考：此方法的缺点：计算量大精度损失更好的方法？2023/2/125计算几何的方法：在计算几何里，我们知道，△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负用右手螺旋定则判断负面积正面积BCACBA2023/2/126大功告成：

Area(A,B,C)=1/2*(↑AB)×(↑AC)

=∣

∣/2特别注意：以上得到是有向面积（有正负）！Xb–XaYb–YaXc–XaYc–Ya2023/2/127凸多边形的三角形剖分很自然地，我们会想到以P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：

A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A42023/2/128凹多边形的面积？P1P4P3P22023/2/129依然成立！！！多边形面积公式：A=sigma(Ai)(i=1…N-2)结论：“有向面积”A比“面积”S其实更本质！2023/2/130任意点为扇心的三角形剖分：我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？比如，以多边形内部的一个点为扇心，就可以把多边形剖分成N个三角形。P0P1P2P6P5P4P32023/2/131前面的三角剖分显然对于多边形内部任意一点都是合适的！我们可以得到：A=sigma(Ai)（i=1…N

）即：A=sigma∣

∣/2

（i=1…N

）Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y02023/2/132能否把扇心移到多边形以外呢？P0P1P2P3P42023/2/133既然内外都可以，为什么不设P0为坐标原点呢？OP1P2P3P4现在的公式？2023/2/134简化的公式：A=sigma∣

∣/2（i=1…N

）XiYiX(i+1)Y(i+1)2023/2/135基本问题（2）：给定一个简单多边形，求其重心。输入：多边形（顶点按逆时针顺序排列）输出：重心点C求任意多边形的重心1、质量集中在顶点上，n个顶点坐标为(xi,yi)，质量为mi，则重心X=∑(xi×mi)/∑mi

Y=∑(yi×mi)/∑mi

2、若每个点的质量相同则

X=∑xi/n

Y=∑yi/n2、质量分布均匀3、特殊地，质量均匀的三角形重心：

X=(x0+x1+x2)/3

Y=(y0+y1+y2)/32023/2/1将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，则面积就是质量】因为质量都集中在重心所以把所有求出来的重心按逆时针连接起来又是一个多边形但是这个多边形的质量集中在顶点上所以可以利用上面公式进行计算2023/2/1求质量分布均匀的n边形重心#include<cstdio>#include<cstdlib>#include<iostream>usingnamespacestd;constintN=1000000;structpoint{doublex;doubley;}p[N],g;//p数组保存多边形的顶点doublecrossProd(pointA,pointB,pointC)//计算三角形ABC有向面积{return(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}voidcompGravity(intn)//求重心g{pointtmp;doublesumArea,area;sumArea=0;g.x=g.y=0;for(inti=2;i<n;++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);}2023/2/1二、凸包的求解2023/2/1二.凸包的求法(Graham算法)凸包的定义：你可以这样想象：平面上有很多根钉子,你的手里有一根橡皮环,你用橡皮环把这些钉子都套起来，然后松手，橡皮环所形成的图形就是这些钉子的一个凸包（如下图）Graham扫描法：1.选则p0作为y坐标最小的点，如果有多个这样的点，则选择x最小的。2.剩余的点根据他们相对于p0的极角的大小从小到大排序，设排序后的点依次为P[0....n]。3.设置一个栈，P0,P1,P2先入栈。4.对于P[3..n]的每个点，若它与栈顶的两个点不构成"向左转"的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。思考：如何对这些极角排序？用atan函数？显然会有精度问题，不准确回忆一下以前讲的向量的叉积。2023/2/1p0p1p2如何知道p2的极角就比p1大呢？再思考一下如何判断左转还是右转？自然也是叉积。。。显然只需要向量p0p1和向量p0p2做叉积就可以了，如果大于0则p2的极角比p1大。2023/2/1432023/2/1442023/2/1452023/2/1462023/2/1472023/2/1482023/2/1492023/2/1502023/2/1512023/2/1522023/2/1532023/2/1542023/2/1552023/2/1graham算法模板#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;constintMAXN=105;constdoubleeps=1e-8;structPoint{intx;inty;};Pointp[MAXN];//保存输入结点Pointst[MAXN];//保存凸包结点，把que当一个栈来使用inttop;//记录栈顶位置doubledis(Pointa,Pointb)//求a,b两点距离{returnsqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}intcross(Pointp1,Pointp2,Pointp0)//求P0P1与P0P2的叉积{return(