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

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

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

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

计算几何算法

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

算法介绍

编辑

矢量概念

编辑

如果把一条线段的端点作出次序之分,则可将这种线段看作有向线段。如果有向线段 的起点 在坐标原点,则把它称为矢量 。这样,点  可以看作起点为原点 的二维矢量。相应地,三维空间坐标系下的坐标也可以作类似理解为三维矢量。

设二维矢量 ,则矢量的加法定义为 ,矢量的减法定义为 。矢量的加减法有以下性质: 。因为点可视为坐标原点至该点的矢量,所以点的加减法就是矢量的加减法。

矢量的叉积

编辑

矢量的叉积,也称矢量的叉乘。矢量  的叉乘记作 。定义 ,其结果是一个标量。几何意义为由原点、点 、点 、点 四点共同组成的平行四边形的面积(带正负号)。计算矢量叉积是直线和线段相关算法的核心。矢量的叉积有以下性质: 

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

  •  ,则  的顺时针方向(左旋);
  •  ,则  的逆时针方向(右旋);
  •  ,则  共线,可能同向也可能反向。

算法举例

编辑

判断折线段的拐向

编辑

折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段  ,通过计算 的符号,就可以确定折线的拐向:

  •  ,则  点拐向右侧得到 
  •  ,则  点拐向左侧得到 
  •  ,则   三点共线。

判断点是否在线段上

编辑

外部链接

编辑