计算几何.docx
《计算几何.docx》由会员分享，可在线阅读，更多相关《计算几何.docx（10页珍藏版）》请在冰点文库上搜索。
计算几何
ComputationalGeometry
计算几何
译BySuperBrother
目录
[隐藏]
∙1知识准备
∙2操作
o2.1叉积
o2.2点积
o2.3反正切
∙3全面考虑问题
∙4一些几何算法
o4.1三角形面积
o4.2两条线段平行吗？
o4.3多边形面积
o4.4点到直线的距离
o4.5点在直线上
o4.6点都在直线的同侧
o4.7点在线段上
o4.8点在三角形内
o4.9点在凸多边形内
o4.10四点（或更多）共面
o4.11两条直线相交
o4.12两条线段相交
o4.13两直线的交点
o4.14判断平面内多边形的凹凸性
o4.15点在凹多边形内
∙5几何方法
o5.1蒙特卡洛方法（MonteCarlo）
o5.2分割技术
o5.3转化为图
∙6例子
o6.1PointMoving
o6.2BicycleRouting
o6.3MaximizingLineIntersections
o6.4PolygonClassification
知识准备
∙图论
∙最短路
操作
这个模块讨论几个计算某些几何问题的算法，这些算法大多基于下列两个操作：
叉积和反正切。
叉积
u和v的叉积被表示成uxv。
两个三维的向量u,v的叉积是下列行列式（i,j,k为x,y,z轴上单位向量）:
|ijk|
|UxUyUz|
|VxVyVz|
即:
（Uy*Vz-Vy*Uz）i+（Uz*Vx-Ux*Vz）j+（Ux*Vy-Uy*Vx）k
z分量为0时，上面式子就化为2维的两向量叉积了。
结果只有z分量。
即：
|UxUy|
|VxVy|
Ux*Vy-Uy*Vx
（注意！
二维的叉积较为猥琐。
。
其实叉积最早就是定义在三维空间内的，当z=0时的特殊情形才是二维向量积。
“二维向量”表达式求出的是一个超出平面的向量。
。
这个向量的方向我们不关心，但有时又要利用它。
。
。
（例如求多边形面积）故上式不甚严格）
叉积有3个特点：
∙两个向量的叉积是一个与这两个向量同时垂直的向量。
∙叉积的大小等于下面3个量的乘积:
ou的大小
ov的大小
ou,v夹角的正弦。
当然与u,v同时垂直的向量有两个方向，叉积的方向取决于u在v的右边还是在v的左边。
点积
两个向量u,v的点积是一个标量，用u·v表示。
在三维空间中它被定义为：
uxvx+uyvy+uzvz。
点积的值由以下三个值确定：
∙u的大小
∙v的大小
∙u,v夹角的余弦。
在u,v非零的前提下，点积如果为负，则u,v形成的角大于90度；如果为零，那么u,v垂直；如果为正，那么u,v形成的角为锐角。
反正切
反正切函数对于一个给定的正切值，返回一个在-pi/2到pi/2之间的角（即-90度至+90度）。
C中另外有一个函数atan2，给出y分量和x分量（注意顺序！
），计算向量与x正半轴的夹角，在-pi到pi之间。
它的优点就是不需担心被0除，也不需为了处理x为负的情况而写代码修改角。
atan2函数几乎比普通的atan函数更简单，因为只需调用一次。
全面考虑问题
这些几何问题大多都产生很多特殊情况。
注意这些特殊情况并且要保证自己的程序能处理所有的情况。
浮点运算也会带来新问题。
浮点运算很难精确，因为注意：
计算机只能计算一定精度。
特别地，当判断两个值是否相等时，要判断两个值的差在一个很小的范围内，而不是直接相等。
一些几何算法
这里是一些能帮助你计算几何问题的东西。
三角形面积
为了计算由点（A,B,C）构成的三角形的面积，先选取一个顶点（例如A），再向剩余两个顶点作向量（令u=b-a,v=c-a）。
三角形（A,B,C）的面积即为u,v叉积长度的一半。
另一个求三角形面积的变通方法就是用海伦公式。
如果三角形三边长为a,b,c，令s=（a+b+c）/2，那么三角形面积就是:
sqrt（s*（s-a）*（s-b）*（s-c））
两条线段平行吗？
为了判断两条线段是否平行，分别沿两条线段建立向量，判断叉积是否（几乎为）零。
多边形面积
由点（x1,y1）...（xn,yn）组成的多边形的面积等于下列行列式的值：
1|x1x2...xn|
---||
2|y1y2...yn|
也等于下面的式子的值:
x1y2+x2y3+...+xny1-y1x2-y2x3-...-ynx1
就是选取原点作标准连接原点和个顶点并且两两个地计算叉积并加起来
点到直线的距离
点P到直线AB的距离也可以由叉积给出，准确的说,d（P,AB）=|（P-A）x（B-A）|/|B-A|。
为了点P到由点A,B和C确定的平面的距离，令n=（B-A）x（C-A），那么d（P,ABC）=（P-A）·n/|n|。
点在直线上
如果点到直线的距离是0，那么点在直线上。
点都在直线的同侧
只讲两个点的情况。
如果要确定点C和D是否在直线AB同侧，计算（B-A）x（C-A）和（B-A）x（D-A）的z分量。
如果同号（或如果积为正），那么点C,D在直线AB同侧。
点在线段上
为了求出点C是否在线段AB上，先判断点C是否在直线AB上，再判断线段AB的长度是否等于线段AC长度与线段BC长度之和。
点在三角形内
要确定点A是否在三角形内，首先选择一个三角形内部的点B（重心就很不错）。
接下来，判断点A,B是否都在三边所在的三条直线的同侧。
点在凸多边形内
方法同上
四点（或更多）共面
如果要确定一组点是否共面，任选3个点。
如果对于任意点D，有（（B-A）x（C-A））·（D-A）=~0，那么这些点共面。
两条直线相交
平面内两条直线相交当且仅当直线不平行。
空间内，两直线AB,CD相交则AB,CD不平行，且点A,B,C,D共面。
两条线段相交
平面内，两条线段相交当且仅当A,B在线段CD异侧且C,D在线段AB异侧。
注意两个判断都是必须的，例如第三种情况第一个判断为true，但第二个判断说明线段AB,CD不相交。
在空间中，计算下面方程组，其中i,j未知：
Ax+（Bx-Ax）i=Cx+（Dx-Cx）j
Ay+（By-Ay）i=Cy+（Dy-Cy）j
Az+（Bz-Az）i=Cz+（Dz-Cz）j
如果方程组有解（i,j）满足0<=i<=1，0<=j<=1，那么两线段相交于点（Ax+（Bx-Ax）i,Ay+（By-Ay）i,Az+（Bz-Az）i）
两直线的交点
在平面内的两条直线AB,CD，求交点最直接的方法就是解下列的二元二次方程组：
Ax+（Bx-Ax）i=Cx+（Dx-Cx）j
Ay+（By-Ay）i=Cy+（Dy-Cy）j
交点是:
（Ax+（Bx-Ax）i,Ay+（By-Ay）i）
空间内，解同样的方程组来判断交点，交点是：
（Ax+（Bx-Ax）i,Ay+（By-Ay）i,Az+（Bz-Az）i）
判断平面内多边形的凹凸性
要判断平面内一多边形是否为凸，沿着顺时针方向扫一遍。
对于每三个点（A,B,C），计算叉积（B-A）x（C-A）。
如果叉积的z分量均为负，多边形则为凸多边形。
点在凹多边形内
要确定点是否在凹多边形内，任选一点作射线，计算相交次数。
如果与多边形相交于一点或一边，则换一个方向，否则，点在多边形内当且仅当射线与点相交次数为奇数。
这个方法也可以扩展到三位（或更高），但此时应相交于面（再判断），不是在点上或边上。
几何方法
这些几何方法介绍了一些技巧，可以用来优化时间和求得更精确的解。
蒙特卡洛方法（MonteCarlo）
第一个方法是建立在随机化之上的。
它不去直接计算某件事的概率，而是以一个随机事件来模拟，求得事件发生的频率。
如果次数足够，频率和概率的差别会很小。
这对于确定某些东西来说是很有用的，例如计算某个图形的面积。
它不去直接计算面积，而是建立一个已知大小的区域，每次向该区域扔一个“飞镖”，并计算击中区域内图形的频率。
如果计算足够精确，就可以得到实际面积的一个足够好的近似值。
这个方法要得到一个足够小的相对误差（误差于实际值之商），需要大量成功发生的事件。
如果发生的概率很小，结果就不好了。
分割技术
分割技术可用来优化时间。
这需要把平面分割成小块（通常是分成小格，但有时也会用角度或其它方法），并将元素放入合适的区域中。
当检查图案的某部分时，只有有该图案的格子会被检查到。
所以，时间可以大大地优化，比如，要确定到定点的距离小于某个值的元素（此时图案是个圆），或求是否相交（此时图案为直线）。
转化为图
有时看起来像几何问题的问题实际上却是一个图的问题。
因为输入是平面内的点，并不代表问题是几何问题。
例子
PointMoving
给定一组线段和点A,B，能否在不穿过线段的情况下从A移动到B？
线段将平面分割成不同部分,检查A,B是否在一个部分。
BicycleRouting
给出有起点和终点的一组建筑物，找出从建筑物A到B不穿过任何建筑物的最短路线。
题解：
图论问题。
以建筑物的起点和重终点为点，两点之间在不径直穿过任何建筑物时连一条边，边权为两点之间的距离。
这样就把原问题转化成了最短路问题。
MaximizingLineIntersections
给出平面内一组点，找到能被一条直线能相交到的最多线段。
题解：
很显然，直线必须经过两个交点。
这样，枚举每对交点，计算此时直线的交点数。
可用分割法优化。
PolygonClassification
给出一组直线所确定的多边形，判断多边形是否是简单的（没有任意两条不连续的线段相交）和凸的.
升级会员 