计算两条共线的线段的交点：

计算几何常用算法
[url]http://www.gissky.net/Article/1223.htm
[/url]
作者：未知    文章来源：Sohu博客    点击数：11006    更新时间：2008-4-18
摘要：计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。

计算两条共线的线段的交点：

对于两条共线的线段，它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点；图 (b) 和 (d) 中两条线段有无穷焦点；图 (c) 中两条线段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，如果line1包含了line2的两个端点，则是图(d)的情况，两线段有无穷交点；如果line1只包含line2的一个端点，那么如果line1的某个端点等于被line1包含的line2的那个端点，则是图(c) 的情况，这时两线段只有一个交点，否则就是图(b)的情况，两线段也是有无穷的交点；如果line1不包含line2的任何端点，则是图(a)的情况，这时两线段没有交点。

计算线段或直线与线段的交点:

设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，要计算的就是L0和L1的交点。 1． 首先判断L0和L1是否相交（方法已在前文讨论过），如果不相交则没有交点，否则说明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。

2． 如果P1和P2横坐标相同，即L0平行于Y轴

a) 若L1也平行于Y轴，

i. 若P1的纵坐标和Q1的纵坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 否则说明L0和L1平行，他们没有交点；

b) 若L1不平行于Y轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中可以计算出交点纵坐标；

3． 如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于Y轴，则交点横坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标；

4． 如果P1和P2纵坐标相同，即L0平行于X轴

a) 若L1也平行于X轴，

i. 若P1的横坐标和Q1的横坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 否则说明L0和L1平行，他们没有交点；

b) 若L1不平行于X轴，则交点纵坐标为P1的纵坐标，代入到L1的直线方程中可以计算出交点横坐标；

5． 如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于X轴，则交点纵坐标为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标；

6． 剩下的情况就是L1和L0的斜率均存在且不为0的情况

a) 计算出L0的斜率K0，L1的斜率K1 ；

b) 如果K1 = K2

i. 如果Q1在L0上，则说明L0和L1共线，假如L1是直线的话有无穷交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 如果Q1不在L0上，则说明L0和L1平行，他们没有交点。 c) 联立两直线的方程组可以解出交点来这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就先利用矢量叉乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后面就可以将线段全部看作直线来考虑。需要注意的是，我们可以将直线或线段方程改写为 ax+by+c=0的形式，这样一来上述过程的部分步骤可以合并，缩短了代码长度，但是由于先要求出参数，这种算法将花费更多的时间。

求线段或直线与折线、矩形、多边形的交点：

分别求与每条边的交点即可。

求线段或直线与圆的交点:

设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。

1. 如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步。

2. 如果L平行于Y轴，

a) 计算圆心到L的距离dis； b) 如果dis > r 则L和圆没有交点； c) 利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。 3. 如果L平行于X轴，做法与L平行于Y轴的情况类似；

4. 如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点；

5. 如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。

凸包的概念：

点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

凸包的求法：

现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话，Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh)，在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham扫描法，其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。

对于一个有三个或以上点的点集Q，Graham扫描法的过程如下：

令p0为Q中Y-X坐标排序下最小的点设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最远的点外全部移除 压p0进栈S 压p1进栈S 压p2进栈S for i ← 3 to m do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧 对S弹栈 压pi进栈S return S;

此过程执行后，栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是，我们对点按极角逆时针排序时，并不需要真正求出极角，只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。

四、结语

尽管人类对几何学的研究从古代起便没有中断过，但是具体到借助计算机来解决几何问题的研究，还只是停留在一个初级阶段，无论从应用领域还是发展前景来看，计算几何学都值得我们认真学习、加以运用，希望这篇文章能带你走进这个丰富多彩的世界。