(HDUACM201303版_09)计算几何基础

已覆盖 未覆盖
完整的算法
• 有向弦构成多个有向多边形, 逆时针为正, 顺时针为负
• 弓形面积和与有向多边形面积和即为所求
时间复杂度
• 处理每一个圆
– 计算其他圆覆盖它的区间: O(n) – 排序并扫描得到各条有向弦: O(nlogn) – 计算各个弓形总面积: O(n)
• 这一步的总时间是O(n2logn) • 有向弦最多n2条, 计算有向多边形总面积为
• ACO2O1是平行四边形, 故AB=r1-r2, AC=d • 直角△ABC中, ∠BAC=arccos(r1-r2)/d
B
A
C
O1
O2
其他切点
• 对于每两个圆i, j, 需要求出四种切点相对于 二者的极角, 一共8个极角
• 算内公切线时AB=r1+r2 • 所求出的8个极角只是相对于O1O2的. 若
• 如果规定向量的起点都在原点，则可以用几何图 形表示向量加法和数量乘法
仿射几何
• 仿射几何(Affine Geometry)包括标量集合、 点集合和自由向量集合, 标量一般是实数, 自由向量表示方向和大小, 而位置不固定
仿射组合
• 一般来说点和数不能相乘, 点和点也不能相
加, 但
时以下情况是个例外
– 对任何一条边e，整个多边形在e 的一侧（如果是正方向，则必是 左侧）
• 星形多边形
– 存在多内部一点，能“看到”多边 形内所有点
– 所有满足定义要求的点组成的区 域称为“核”
– 由核和围绕着“核”的尖角构成， 总与圆同态
• 注意“看到”和“清晰看到”的区别
有向面积
• 左图：ABC成左手系，负面积 • 右图：ABC成右手系，正面积

如果t1 * t2 > 0，则在同侧，否则在异侧。
点到直线的距离 点P到直线AB的距离:
d(P,AB) = |(P - A) x (B - A)| / | B - A|
P
A
B
计算几何
二、计算几何的基本算法 5、判断两条线段P1P2 ，P3P4是否相交
方法1：只要在4的基础上，加上一个判断，看交点是否在线段P1P2 ，P3P4上，即： function judgejiao(var p1,p2,p3,p4):Boolean; var p:pointtype; begin getjiao(p1,p2,p3,p4,p); {求交点} if min(p1.x,p2.x)<=p.x<=max(p1.x,p2.x) and min(p1.y,p2.y)<=p.y<=max(p1.y,p2.y) and min(p3.x,p4.x)<=p.x<=max(p3.x,p4.x) and min(p3.y,p4.y)<=p.y<=max(p3.y,p4.y) then jiao:=true {判断在线段内} else jiao:=false; end; 问题是：运用了除法，使得效率很低，并且容易产生误差，当线段几乎平行时，该算法对实际 计算机除法运算的精确度非常敏感。所以，希望在这种题目中只用加、减、乘、比较运算，不 要用除法，也不要用三角函数。
( p1 p0 ) ( p2 p0 ) ( x1 x0 )( y2 y0 ) ( x2 x0 )( y1 y0 )
如果该叉积为正， 则 P 0 P1 在 P 0 P 2 的顺时针方向， 如果为负，则 P 0 P1 在 P 0 P 2 的逆时针方向。 如果等于0，则P0，P1，P2三点共线。

Computational Geometry
计算几何教程
计算几何的恶心之处
代码长，难写。
需要讨论各种边界情况。后面所介绍的算
法，有些对于边界情况的处理很完美，不 需要再做讨论；有些则不然，需要自行处 理边界情况。
精度误差

二维矢量
2-Dimension Vector
矢量
既有大小又有方向的量。
算法演示
2 被弹出栈，3 进栈。
算法演示
没有点被弹出栈，4 进栈。
算法演示
4 被弹出栈，5 进栈。
算法演示
5 被弹出栈，6 进栈。
算法演示
6 被弹出栈，7 进栈。
算法演示
如此直到下凸壳被找到。
算法演示
倒序进行扫描找到上凸壳。
Graham 扫描的时间复杂度
这太傻缺了。算法的瓶颈在排序，所以时
总时间复杂度 O(N2 log N)。
算法扩展
SPOJ CIRUT
求恰好被覆盖 1 次、2 次、„、N 次的面积。
算法的本质在于对“裸露”部分进行处理。
这种方法也可以用于求很多圆与很多凸多 边形的面积并——但是情况复杂得多，要 讨论的情况也多得多。
三维矢量
3-Dimension Vector
总体来说讨论比较辛苦，写起来不算很难。
精度存在比较大的问题，而且半平面交的
题目一般都容许 O(N2) 算法，所以并不是 很常用。
半平面交练习题
POJ 1279 POJ 3525 POJ 2451 POJ 3384
求多边形的核。核中的点满足其到多边形边 界上任一点之间的线段只与多边形在那一点相交。 求凸多边形最大内切圆半径。 裸的半平面交。朱泽园专门为他的算法出的 题，要求 O(N log N) 算法。 求在凸多边形内部放两个半径为 r 的圆所能 覆盖的最大面积。两圆可以重叠，但不能与多边形相交。 需要用到旋转卡壳。

需要注意的细节
（4）圆周率取3.141592654或者更精确，或者用 acos(-1.0)角度制和弧度制的转换，C/C++中的三角 函数均为弧度制 （5）尽量少用除法，开方，三角函数，容易失去精 度。用除法时注意除数不为0，输出的时候要小心0.00000，比如a=-0.0000001，printf(“%.5f”,a); (6)在使用反三角函数时，注意定义域的范围，如 acos（x），当x是你计算得到时可能会出现越界现象， 比如本来应该得到是1，而你计算得到谁 1.0000000001， 这时acos（x）的值就会出错了，所以我们可以加一 句判断，if(fabs(x-1)<eps||fabs(x+1)<eps) x=round（x）
{ //点不线段判定 return dcmp(Cross(a1-p,a2p)==0&&dcmp(Dot(a1-p,a2-p))<0);
}
圆的相关计算
（一）直线与圆的交点
假定直线为AB，圆的圆心为C，半径为r。 方法一：解方程 联立直线方程和圆方程，得到二次函数，可通过二次函 数的求解得到直线和圆的关系及其交点坐标。 方法二：几何法 求C在AB上的投影p，再求AB对应的单位向量v；则两 交点为p-Lv和p+Lv，L为p到交点的距离，在通过勾股定理即可 求得结果。
切
圆的相关计算
else if(d<=fabs(r1-r2) && d>=0) ｛ //内切 if(r1>r2) printf("%0.3lf\n",PI*r2*r2); else printf("%0.3lf\n",PI*r1*r1); } else｛ A1=2*acos((d*d+r1*r1-r2*r2)/(2*d*r1)); //求以圆心为顶点与 两圆交点连线的角 A2=2*acos((d*d+r2*r2-r1*r1)/(2*d*r2)); s1=0.5*r1*r1*sin(A1)+0.5*r2*r2*sin(A2); s2=A1/2*r1*r1+A2/2*r2*r2; s=s2-s1; printf("%0.3lf\n",s); } } }