计算几何

✍ dations ◷ 2025-07-13 11:03:04 #计算机科学,理论计算机科学,数位几何学,计算几何

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

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

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

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

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

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

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

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

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

相关

  • 西墙西墙,又名哭墙(希伯来语:הַכֹּתֶל הַמַּעֲרָבִי‎,HaKotel HaMa'aravi),阿拉伯人称之为布拉克墙(阿拉伯语:حائط البراق‎,Ḥā'iṭ Al-Burāq)位于耶路
  • U.S. Environmental Protection Agency美国国家环境保护署(英语:Environmental Protection Agency,缩写:EPA),简称美国环保署,是美国联邦政府一个独立行政机构,负责维护自然环境与保护人类健康不受环境危害及污染影响。EP
  • 聚酯纤维聚酯(英语:Polyester)是一类在其主链上含有酯基官能团的聚合物。虽然聚酯有很多种,但是“聚酯”一词通常指的是聚对苯二甲酸乙二酯(PET)。聚酯纤维是由饱和的二元酸与二元醇通过缩
  • 弟妇姻亲指基于婚姻关系而生之亲属型态,一方配偶与他方配偶之亲属间,因双方缔结婚姻后,成为相互具法律上亲属关系的情况。《中华民国民法》第969条规定,包括配偶的血亲、血亲的配偶
  • 左拉传《左拉传》是一部1937年的美国传记片,讲述法国作家埃米尔·左拉的一生。它描绘了左拉与著名画家保罗·塞尚的友谊、他通过大量写作获得成功的经历,重点描绘了他参在德雷福斯事
  • 巴图鲁巴图鲁(满语:ᠪᠠᡨᡠᡵᡠ,转写:baturu),有“英雄”、“勇士”之意,为满洲传统封号之一,后来成为清朝时期赏赐有战功之人的封号。因其用来表彰获封之人的武功,故而又有“勇号”之称。
  • 新罗马新罗马(希腊语:Νέα Ῥώμη,转写:Nea Romē,拉丁语:Nova Roma)是罗马皇帝君士坦丁在博斯普鲁斯海峡欧洲海岸建立的帝国新首都的名称,因此也被成为君士坦丁堡,君士坦丁堡的重建自3
  • 田径运动田径(英语:Athletics),或称田径运动(英语:Sport of Athletics)、陆上竞技,是田赛和径赛(英语:Track and Field)、全能比赛的统称。以高度和距离长度计算成绩的跳跃、投掷项目叫“田赛”
  • 鳍龙超目鳍龙超目(学名:Sauropterygia)也作鳍龙总目,其学名意为“蜥蜴的鳍状肢”,是一类非常成功的海生爬行动物,繁盛于中生代。它们因为肩膀的基本适应特征而分类在一起,这特征是为了支撑
  • 河南科技学院河南科技学院是位于中国河南省新乡市红旗区的一所高等院校,由辉县迁来。原名百泉农业专科学校(百泉农专)、平原农学院、河南职业技术师范学院。农业育种方向为该校的强项学科。