alex4814*March 26,2012
计算几何，简单来讲就是适合于计算机处理的几何方法。
1位置与方向
首先要处理的就是计算几何中最基本的问题——判断线段相交与否以及
求交点的方法。
1.1点、线、面的位置关系
首先提出这样一个最基本的问题：如何判断两线段相交？以此来看看
计算几何的优点。方法1：解析几何
一条线段其实也就是一条直线，我们可以用解析几何的
方法，列出方程组求出交点来判断它们是否相交。 但是弊端非常明显不说斜率有时候无法表示，还有很大的浮点误差。不过用一般方程如Ax+By=
C可以减少一部分麻烦，但还是免不了判断的麻烦。方法2：点积与叉积
从解析几何的算法中我们看到，要判断两线段是否相
交，就得先求他们的交点。但是思考后我们发现，我们并不关注他们的交点在哪，而仅仅只是想知道，这两条线段是否相交。
现在我们来看看线段相交的各种情况。 （示）
*
alex4814.fu@gmail.com
1
acm@njust1位置与方向
Figure1:Judge the side
线段相交⇔每条线段两个端点都在另一条线段所在直线的异侧（非特殊相交的情况）1.1.1
叉积
看看叉积如何解决这样的问题。
叉积对应正弦，点积对应余弦。象限的正负刚好对应了左右和前后。（示）
我们可以不将线段看作单独的两个点，而是考虑有序实数对的概念，给
()()
之一个序。 同样是(0,0),(0,1)这两个点，(0,0),(0,1)和(0,1),(0,0)是两条不同的线段，称之为有向线段。
叉积是这样一个运算，它可以清楚的判断一个向量与另一个向量的方向关系，而且这个运算的结果显而易见，而且容易实现，但也不是能完全避免浮点误差1。
1231
structpoint{
doublex,y;
};
如果题目中全是int型输入，那么更不允许有误差，在数据量大的情况下，要尽量用int或long long来处理。
2
acm@njust1位置与方向
45678910111213141516171819
#defineeps1e-6intsgn(doubled){
if(fabs(d) } doubledet(doublex1,doubley1,doublex2,doubley2){ returnx1*y2-x2*y1; } //judgewhichsidepistowardsdirected-segab//posforleft,negforright doubleside(pointa,pointb,pointp){ returndet(b.x-a.x,b.y-a.y,p.x-a.x,p.y-a.y); } 让我们看看如何在已知相交的情况下，方便的求得他们的交点。定比分点 xP= 线性方程组 S△ABD·xc+S△ABC·xD S△ABD+S△ABC DxD xP= 要特别注意浮点误差。 再来看看相交的一些特殊情况。（示）1.1.2 点积 −→−−→ 要看P是否在线段AB上，只需要看PA·PB的符号即可。 这样虽然方便，不过还是需要乘法，有些许的误差。 让我们看看另一个方法。坐标比较 在已知P在AB直线上的情况下，我们只需考虑x轴或y轴的坐标分 量即可。 尽量减少误差，选择跨度大的那一维。 3 acm@njust1位置与方向 用点积还可以求两个有向线段之间的夹角。 −1 θ=cos ⃗·B⃗A⃗|·|B⃗||A 如果说线段有向比较容易理解的话，那么有向面积就不那么明显了，但是它将有巨大的作用，待后文介绍。 看个例子：Pipe（离散化）Pipe.cpp 1.2点与多边形的位置关系判断 多边形其实就是一些首尾相接的闭合的线段组成的图形。但 简单多边形 是它有很多不同的类型。我们常见的也是讨论最多的是简单多边形，即对于所有非相邻的线段它们没有交点。凸多边形 直观上我们可以看的出来，对于任意一条凸多边形上的边而言， 整个凸多边形在该边的一侧。如果给这个多边形定上正方向的话，那么就是在左侧。 数学上定义则是： ∀x,y∈D, x+y ∈D2 根据这个定义我们可以得到，x,y上的任意一点均在多边形内的结论。 让我们来看看如何判断一个点，是在多边形内，还是形外。 ∮ A·dS=0 Σ 回顾一下对曲面的回路积分，我们知道积分为零。之所以称之为无源，是因为进出相衡。 同理，一个点如果在多边形的外面，如果它穿越这个多边形，那么进出的次数应当相同。所以我们想到根据从它出发的一条射线，与多边形相交2的次数来判断，它到底是在形内还是形外。 很容易理解，奇数次在内，偶数次在外。 为了处理方便，我们往往取与x轴正方向平行的一条射线。 （示） 2 对于和射线有交点的线段来说，如果该交点两侧线段异侧，才真正视为相交 4 acm@njust1位置与方向 当然我们要注意一些特殊情况，如在边上的点。平移法 我们把这条射线向上或向下平移一小段位移，并不会影响结果（改 变的是偶数个交点）。 而且在也判断条件的时候，并没有真正意义上的平移，而只需要修改判断的条件。 每条线段，只要一个点高于(>)，另一个点不高于(⩽)，交点在P右侧即可。 这就相当于向上平移了一样，本来恰好相交的点。 12345678910111213141516171819202122232425 //whetherthegivenpointisinsideoroutsideofthepolygon//0foroutside//1forinside //2foronedge(exceptvertices)//3forvertex //pointsorderedbyinputpolygondirectionintpointDir(point*pg,pointp){ intis,ps,cnt=0;pg[n]=pg[0];pointup,low; for(i=0;i up=pg[i];low=pg[i+1]; }else{ up=pg[i+1];low=pg[i]; } if(up.y>p.y&&low.y<=p.y){ is=sgn(side(p,low,up));if(is>0)++cnt;elseif(is==0){ ps=between(low,up,p);if(ps==0)return3; 5 acm@njust2凸包 26272829303132 elseif(ps==-1)return2; } } } if(cnt&1)return1;return0; } 2凸包 definition. 2.1Graham 求凸包方法的简单概括就是：序+方向。 当然共线的问题一直是不可忽 视的。 Figure2:convex hull algorithm: 1 凸包的求解算法如下 push(p[0]); 6 acm@njust2凸包 234567 push(p[1]);fori=2ton-1 whilep[i]istherightsideofsegment(stack[top-1],stack[top]) pop(); push(p[i]); 有两个序可以选择，一个极角序，一是水平序。当我们改成水平序的时候，只需要分两链进行即可。Melkman 它是一个求简单多边形凸包的精妙算法，可以在线性时间内求 得。 它最大的特点在于采用了双端队列，可以理解为两头都可以增减的栈。 只要在栈顶维护右手系，栈底维护左手系，就能在线的生成凸包。 算法如下： 1.初始的三个点组成的三角形即凸包。此时栈里为3−1−2−3。2.要保证栈顶右手，栈底左手，即为此有必要交换1、2。3.分别对栈顶和栈底维护。 2.2property: 凸包的性质就是凸性。圆就是凸性的极限。任意一条弦均在圆内。 如果 凸包上每条边只有2个点，那么它不能唯一的确定一个多边形。 至少三个点心上即可。 2.3applications: 点集分割最长直径最小外接矩形 7 acm@njust4半平面交 离散化覆盖m点中的n点的最小面积矩形Finding the Rectangle 3 3.1 多边形的面积、核 再现叉积 运用最简单的三角剖分，我们可以分而治之。 这里我们将看到有向面积 的神奇之处，简单多边形的面积可统一为一个通式。 通过简单的三角剖分可以得到 xiyi1A=2 i=1xi+1yi+1 n∑ 3.2全视角 多边形的核其实也就是能看得见多边形内任何角落的区域，可以没有也 可以是全部（凸包的核即为本身）。 我们可以发现，只要把每条边对应的内侧半平面求交集即可得到该区域。 4半平面交 求多边形核的方法。 4.1仅水平和竖直的情况 我们只需求核的上下左右的边界值lx,rx,by,ay就可以了。 对于(x1,y)→ (x2,y)with(x1 acm@njust4半平面交 operations: 往右by=max(by,y)往上rx=min(rx,x)往左ay=min(rx,x)往下 lx=max(lx,x) 4.2nlgn的求交算法(Zeyuan Zhu) 111 将平面以极角分成(−12π,2π]和(−π,−2π]∪(2π,π)两部分1考虑其中一个(−π,−2π]∪(12π,π)的半平面（另一个类似）， 对它 Step 1:Step 2: 们极角排序。若是极角上同的，选择左侧的那一个Step 3: 从排序后极角最小的两个开始，将它们入栈。 每次按排序的顺序加 入一个半平面，算出该平面与栈顶平面的交点。 如果当前交点在 栈顶两个半平面交点的右边，则出栈。 跟Graham类似，出栈直至交点在左边。Step 4: 该一半给出上半个凸多边形，另一半则会给出下一半。 这里我们又用到了双端队列。 核心代码： 1234567891011121314 deq[0]=vec[0];deq[1]=vec[1];fori=2ton-1 ifparallel(tail,tail-1)orparallel(head,head+1)return;while(head pop(tail); while(head pop(head); push(tail,vec[i]); while(head 9 acm@njust4半平面交 151617 while(head applications:半平面交也就是求一系列线性规划问题的解。 例如两个凸包 求交也可以用半平面交的方法来求。 10 因篇幅问题不能全部显示，请点此查看更多更全内容