计算几何

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

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

自从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)} 的符号,就可以确定折线的拐向:

相关

  • 放射辐射在物理学上指的是能量以波或是次原子粒子移动的型态,在真空或介质中传送。包含:辐射之能量会从辐射源往外向所有方向直线放射。一般依其能量的高低及电离物质的能力分类
  • 数理金融学金融数学(英语:Financial Mathematics)又称计量金融学(英语:Quantitative Finance)、数学金融学(英语:Mathematical Finance),是专为金融市场而设的应用数学。其本义上与金融经济学的
  • 方法科学(词源为拉丁文“scientia”,意为“知识”)是一种系统性的知识体系,它积累和组织并可检验有关于宇宙的解释和预测。科学强调预测结果的具体性和可证伪性,这有别于空泛的哲学。
  • 红壤红土,指富含氧化铁,氧化铝,水氧化铁,水氧化铝,二氧化铁,二氧化铝的土,因富含氧化铁以致土壤发出棕色颜色,土质最好为黑土,最差为红土。 因长年下雨,导致腐植质储存不易,仅留下较重的氧
  • 扣肉扣肉是一道用猪肉、牛肉或羊肉蒸制成的中国南方菜肴。川菜称烧白。扣肉的“扣”是指当肉蒸至熟透后,最后将其倒盖于盘中的过程。通常作法有芋头扣肉及梅菜扣肉。另外扣肉罐头
  • 镰仓市坐标:35°19′N 139°33′E / 35.317°N 139.550°E / 35.317; 139.550镰仓市(日语:鎌倉市/かまくらし Kamakura shi */?)位于日本神奈川县三浦半岛西面,是人口约为18万人的小型
  • span style=color: white;马丁·舒尔茨/span参数所指定的目标页面不存在,建议更正成存在页面或直接建立下列一个页面(建立前请先搜寻是否有合适的存在页面可以取代):马丁·舒尔茨(德语:Martin Schulz;1955年12月20日-)德国政治
  • 徐州会战徐州会战指1938年1月至6月间,中国军队在以徐州为中心的江苏、山东、安徽、河南等省防御侵华日军攻势的作战。是中华民国对日抗战中一次重要的会战。日本军队于1937年12月13日
  • 美国领地美国领地是指美国行政区划的一种分类,其领土由美国政府管理但不属于美国任何一个州。建立这些领地的目的是为了管理这些新获得的地区,因为当时美国领土的边界还在扩张中。这些
  • 2019冠状病毒病疫情引发的经济衰退SARS-CoV-2(病毒)国际运输冠状病毒衰退是指由于2019-20年冠状病毒大流行而在2020年开始影响世界经济的经济衰退。尽管经济数据需要时间来收集,但许多经济学家都认为经济衰退已