计算几何

计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。计算机的出现使得一些问题大幅简化，然而一些人类直观

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

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

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

计算几何算法

• 判断点是否在直线上
• 判断两线段是否相交
• 判断线段和直线是否相交
• 判断点是否在矩形内
• 判断线段、折线、多边形是否在矩形内
• 判断矩形是否在矩形内
• 判断圆是否在矩形内
• 判断矩形是否在圆内
• 判断点是否在多边形内
• 判断线段是否在多边形内
• 判断点是否在圆内
• 判断圆是否在圆内
• 凸包求法等

外部链接

• 主要的学术会议网页Symposium of Computation Geometry (SoCG)
• 刘鼎元. 苏步青先生对计算几何和CAD事业的贡献.