计算几何

来自计算思维百科
跳转至: 导航搜索

计算几何computational geometry,研究几何模型和数据处理的学科,探讨几何形体的计算机表示。分析和综合,研究如何灵活、有效的建立几何形体的数学模型以及在计算机中更好地存储和管理这些模型数据。 计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支,主要研究解决几何问题的算法。

背景

自从1946年世界上第一台电子计算机问世以来,计算机应用的一个重要里程碑是1962年美国麻省理工学院发明了世界上第一台图形显示器。自此之后,计算机可以通过图形显示器直接输入、输出图形,并且可以在显示屏上通过光标的移动而直接修改图形。而在这之前,工程师是通过一厚叠纸上密密麻麻的数字来间接表达工程图形的。 1962年被认为是美国和欧洲CAD开始发展的一年。首先的应用领域是汽车、飞机和造船工业。这3个行业,由于其产品的外形曲面特别复杂,要求特别苛刻,而成为CAD首先应用的领域。 与此同时,也就发展出了一门新兴学科——计算几何,它在美国常常被称为CAGD(Computer Aided Geometric Design,计算机辅助几何设计),专门研究“几何图形信息(曲面和三维实体)的计算机表示、分析、修改和综合”。1972年在美国举行CAGD第一次国际会议,标志计算几何学科的形成。

概述

由函数逼近论、微分几何、代数几何、计算数学等形成的边缘学科,研究几何外形信息的计算机表示、分析和综合。它是计算机辅助几何设计(即CAGD)的数学基础。计算机辅助设计的研究工作始于1955年 ,20世纪60年代进入实用阶段,到70年代已广泛应用于造船、航空、汽车及众多工业产品的外形设计和制造领域。进行此项工作的设计者首先要把一般的曲线或曲面表示在计算机上,然后对这些曲线或曲面的几何性质进行分析,比如看曲线上有无拐点、奇点、曲面的凹凸性等等,最后采用有效的数值计算方法,经过程序运算或人机对话等形式控制或修改这些曲线或曲面,使之符合产品设计的要求。 法国雷诺汽车公司工程师P.E.贝济埃 ,从 1962 年开始研究并首次完成一项曲线曲面设计系统 ,得到了成功的应用。继贝济埃曲线曲面之后,又有两个图形系统问世,它们是B样条曲线曲面和孔斯曲面。计算几何现主要研究和应用的仍然是以上3种图形系统。

计算机辅助几何设计

计算机辅助几何设计(Computer Aided Geometric Design: CAGD)是涉及数学及计算机科学的一门新兴的交叉学科, 它研究的内容是"在计算机图像系统的环境中曲面的表示和逼近", 它主要侧重于计算机设计和制造(CAD/CAM)的数学理论和几何体的构造方面. 虽然CAGD所用的很多理论工具可以溯源到百年以前, 但是具备一门新学科的雏形却是本世纪六十年代末期的事情. 这主要得益于计算机的高速数据运算和强大图形功能. 虽然说CAGD是数学殿堂中的一名新生儿. 但其所用的理论工具却涉及数学中的很多分支, 如逼近论、微分几何、计算数学、代数几何和交换代数等等, 同时还与计算机图形学有紧密的联系. 随着CAGD理论和应用的不断发展, 从飞机, 船舶, 汽车设计, 到工程器件模具设计, 到生物医学图像处理等都能看到其广泛的应用.

计算几何算法

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

参考文献

百度百科:计算几何计算机辅助几何设计

维基百科:计算几何