计算几何

✍ dations ◷ 2025-08-29 19:46:58 #计算机科学,理论计算机科学,数位几何学,计算几何

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

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

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

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

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

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

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

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

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

相关

抗原呈递细胞抗原呈递细胞（antigen-presenting cell、APC）也称为抗原提呈细胞、辅佐细胞或抗原呈现细胞，是指在免疫应答过程中，能将抗原物质提呈给T细胞的一类辅佐细胞。APC是一群异质性细胞
斯坦利·霍尔斯坦利·霍尔（Granville Stanley Hall，1844年2月1日 - 1924年4月24日）是美国心理学的先驱，致力于儿童发展理论。霍尔也是美国心理学会首任主席，克拉克大学首任校长。霍尔出生在马
天一阁坐标：29°52′25″N 121°32′09″E / 29.87361°N 121.53583°E / 29.87361; 121.53583天一阁是中国现存最古老的私家藏书楼，位于中国浙江省宁波市月湖西侧的天一街。天一阁
以斯拉以斯拉，天主教译厄斯德拉（希伯来语：.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram
体质人类学体质人类学文化人类学语言人类学分子人类学社会人类学考古学应用人类学民族志参与观察文化相对论文化 • 社会史前史 • 人类演化亲属婚姻 • 家庭物质文化种
癌症转移远端转移（英语：Metastasis）也称作恶性转移，是指肿瘤细胞从原始发生的部位借由侵入循环系统，转移到身体其他部位继续生长的过程。通常良性肿瘤不会产生远端转移，而发生转移的病患预
斑岩斑岩，旧称玢岩，是具有斑状结构的火成岩，比较坚固，可用于做建筑材料。斑晶一般由碱性长石或石英组成，基质为细粒或隐晶（玻璃体）。斑岩一部分属于火成岩中的喷出岩，但一般属于火成岩中
俄克拉荷马俄克拉何马大学（University of Oklahoma），成立于1890年，位于美国俄克拉何马州诺曼，学校采学期制，大学部约有20,000名学生，是美国中南部地区有名的大学，所接受的各方捐赠总额，至2008年
贝尔维尤贝尔维尤（英语：Bellevue）是美国华盛顿州金县（King County）东部的一座城市，与西雅图隔华盛顿湖相望。作为西雅图都会区的第三大城市，贝尔维尤在2010年人口普查中的人口为122363人，在2
美国卷耳猫美国卷耳猫是家猫品种之一。体重3-5千克，以耳朵向上卷曲为特征，被毛细腻如丝质般光滑，身体纤细且匀称，该品种的猫是由于猫的遗传基因发生了变异而产生的卷耳特征。美国卷耳猫起