查看“︁计算几何”︁的源代码

{{NoteTA
|G1 = IT
}}
'''计算几何'''是一门兴起于[[二十世纪]][[1970年代|七十年代]]末的计算机科学的一个分支，主要研究解决几何问题的算法。

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

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

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

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

==算法介绍==
===矢量概念===
如果把一条线段的端点作出次序之分，则可将这种线段看作有向线段。如果有向线段<math> P_1P_2 </math>的起点<math> P_1 </math>在坐标原点，则把它称为矢量<math> \boldsymbol{P}_2 </math>。这样，点<math> P(x,y) </math> 可以看作起点为原点<math> O(0,0) </math>的二维矢量。相应地，三维空间坐标系下的坐标也可以作类似理解为三维矢量。

设二维矢量<math> \boldsymbol{P}=(x_1,y_1),\boldsymbol{Q}=(x_2,y_2) </math>，则矢量的加法定义为<math> \boldsymbol{P}+\boldsymbol{Q}=(x_1+x_2,y_1+y_2) </math>，矢量的减法定义为<math> \boldsymbol{P}-\boldsymbol{Q}=(x_1-x_2,y_1-y_2) </math>。矢量的加减法有以下性质：<math> \boldsymbol{P}+\boldsymbol{Q}=\boldsymbol{Q}+\boldsymbol{P},\boldsymbol{P}-\boldsymbol{Q}= -(\boldsymbol{Q}-\boldsymbol{P}) </math>。因为点可视为坐标原点至该点的矢量，所以点的加减法就是矢量的加减法。

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

叉乘的一个非常重要的性质是，可以通过它的正负号判断两矢量之间的顺逆时针关系：
*若<math> \boldsymbol{P}\times\boldsymbol{Q} > 0 </math>，则<math> \boldsymbol{P} </math>在<math> \boldsymbol{Q} </math>的顺时针方向(左旋)；
*若<math> \boldsymbol{P}\times\boldsymbol{Q} < 0 </math>，则<math> \boldsymbol{P} </math>在<math> \boldsymbol{Q} </math>的逆时针方向(右旋）；
*若<math> \boldsymbol{P}\times\boldsymbol{Q} = 0 </math>，则<math> \boldsymbol{P} </math>和<math> \boldsymbol{Q} </math>共线，可能同向也可能反向。

===算法举例===
====判断折线段的拐向====
折线段的拐向判断方法可以直接由矢量叉积的性质推出。
对于有公共端点的线段<math> AP </math>和<math> PB </math>，通过计算<math> \nabla = (B - P)\times(P - A) </math>的符号，就可以确定折线的拐向：
*若<math> \nabla > 0 </math>，则<math> AP </math>在<math> P </math>点拐向右侧得到<math> PB </math>；
*若<math> \nabla < 0 </math>，则<math> AP </math>在<math> P </math>点拐向左侧得到<math> PB </math>；
*若<math> \nabla = 0 </math>，则<math> A </math>、<math> P </math>、<math> B </math>三点共线。

====判断点是否在线段上====

==外部链接==
* [http://www.socg.org 主要的学术会议网页]{{Wayback|url=http://www.socg.org/ |date=20200613215402 }}Symposium of Computation Geometry (SoCG)
* {{cite web | language =  | publisher =  | title = 苏步青先生对计算几何和CAD事业的贡献 | url = http://www.fudan.edu.cn/su/37.htm | author = 刘鼎元 | date =  | accessdate =  | archive-date = 2007-07-07 | archive-url = https://web.archive.org/web/20070707000027/http://www.fudan.edu.cn/su/37.htm | dead-url = no }}

{{Computer Science}}
{{应用数学}}
{{Authority control}}

[[Category:计算机科学]]
[[Category:理论计算机科学]]
[[Category:數位幾何學]]
[[Category:計算幾何]]