计算几何

计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。

自从1946年世界上第一台电子计算机问世以来，计算机应用的一个重要里程碑是1962年美国麻省理工学院发明了世界上第一台图形显示器。自此之后，计算机可以透过图形显示器直接输入、输出图形，并且可以在显示屏上透过游标的移动，直接修改图形。而在这之前，工程师是透过一厚叠纸上密密麻麻的数字来间接表达工程图形的。

1962年被认为是美国和欧洲CAD开始发展的一年。首先的应用领域是汽车、飞机和造船工业。这3个行业，由于其产品的外形曲面特别复杂，要求特别苛刻，而成为CAD首先应用的领域。

与此同时，也就发展出了一门新兴学科——计算几何，它在美国常常被称为CAGD（Computer Aided Geometric Design，计算机辅助几何设计），专门研究“几何图形信息（曲面和三维实体）的计算机表示、分析、修改和综合”。1972年在美国举行CAGD第一次国际会议，标志计算几何学科的形成。

计算几何算法

• 判断点是否在直线上
• 判断两线段是否相交
• 判断线段和直线是否相交
• 判断点是否在矩形内
• 判断线段、折线、多边形是否在矩形内
• 判断矩形是否在矩形内
• 判断圆是否在矩形内
• 判断矩形是否在圆内
• 判断点是否在多边形内
• 判断线段是否在多边形内
• 判断点是否在圆内
• 判断圆是否在圆内
• 计算相交多边形的重叠区域
• 计算点到线段的最近点
• 计算点到圆的最近点及点坐标
• 凸包求法等

算法介绍

矢量概念

如果把一条线段的端点作出次序之分，则可将这种线段看作有向线段。如果有向线段${\displaystyle P_{1}P_{2}}$的起点${\displaystyle P_{1}}$在坐标原点，则把它称为矢量${\displaystyle {\boldsymbol {P}}_{2}}$。这样，点${\displaystyle P(x,y)}$ 可以看作起点为原点${\displaystyle O(0,0)}$的二维矢量。相应地，三维空间坐标系下的坐标也可以作类似理解为三维矢量。

设二维矢量${\displaystyle {\boldsymbol {P}}=(x_{1},y_{1}),{\boldsymbol {Q}}=(x_{2},y_{2})}$，则矢量的加法定义为${\displaystyle {\boldsymbol {P}}+{\boldsymbol {Q}}=(x_{1}+x_{2},y_{1}+y_{2})}$，矢量的减法定义为${\displaystyle {\boldsymbol {P}}-{\boldsymbol {Q}}=(x_{1}-x_{2},y_{1}-y_{2})}$。矢量的加减法有以下性质：${\displaystyle {\boldsymbol {P}}+{\boldsymbol {Q}}={\boldsymbol {Q}}+{\boldsymbol {P}},{\boldsymbol {P}}-{\boldsymbol {Q}}=-({\boldsymbol {Q}}-{\boldsymbol {P}})}$。因为点可视为坐标原点至该点的矢量，所以点的加减法就是矢量的加减法。

矢量的叉积

矢量的叉积，也称矢量的叉乘。矢量${\displaystyle {\boldsymbol {P}}}$与${\displaystyle {\boldsymbol {Q}}}$的叉乘记作${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}}$。定义${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=x_{1}y_{2}-x_{2}y_{1}}$，其结果是一个标量。几何意义为由原点、点${\displaystyle P}$、点${\displaystyle Q}$、点${\displaystyle P+Q}$四点共同组成的平行四边形的面积（带正负号）。计算矢量叉积是直线和线段相关算法的核心。矢量的叉积有以下性质：${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=-({\boldsymbol {Q}}\times {\boldsymbol {P}}),{\boldsymbol {P}}\times (-{\boldsymbol {Q}})=-({\boldsymbol {P}}\times {\boldsymbol {Q}})}$。

叉乘的一个非常重要的性质是，可以通过它的正负号判断两矢量之间的顺逆时针关系：

• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}>0}$，则${\displaystyle {\boldsymbol {P}}}$在${\displaystyle {\boldsymbol {Q}}}$的顺时针方向(左旋)；
• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}<0}$，则${\displaystyle {\boldsymbol {P}}}$在${\displaystyle {\boldsymbol {Q}}}$的逆时针方向(右旋）；
• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=0}$，则${\displaystyle {\boldsymbol {P}}}$和${\displaystyle {\boldsymbol {Q}}}$共线，可能同向也可能反向。

算法举例

判断折线段的拐向

折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段${\displaystyle AP}$和${\displaystyle PB}$，通过计算${\displaystyle \nabla =(B-P)\times (P-A)}$的符号，就可以确定折线的拐向：

• 若${\displaystyle \nabla >0}$，则${\displaystyle AP}$在${\displaystyle P}$点拐向右侧得到${\displaystyle PB}$；
• 若${\displaystyle \nabla <0}$，则${\displaystyle AP}$在${\displaystyle P}$点拐向左侧得到${\displaystyle PB}$；
• 若${\displaystyle \nabla =0}$，则${\displaystyle A}$、${\displaystyle P}$、${\displaystyle B}$三点共线。

判断点是否在线段上

外部链接

• 主要的学术会议网页（页面存档备份，存于互联网档案馆）Symposium of Computation Geometry (SoCG)
• 刘鼎元. 苏步青先生对计算几何和CAD事业的贡献. （原始内容存档于2007-07-07）.