计算几何

✍ dations ◷ 2025-12-03 08:58:32 #计算机科学,理论计算机科学,数位几何学,计算几何

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

自从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)$ 的符号，就可以确定折线的拐向：

相关

磷酸磷酸（英语：phosphoric acid）或称为正磷酸（orthophosphoric acid），化学式H3PO4，是一种常见的无机酸，不易挥发，不易分解，几乎没有氧化性。具有酸的通性，是三元弱酸，其酸性比盐酸、硫酸、硝
科学实在论科学实在论（英语：scientific realism）是对世界的一种看法、理解。在最广泛的意义上，它认为科学所描述的世界，就是真实的世界，亦因而完全独立于人们对世界的个人理解。在科学哲学中
李森科主义李森科主义（俄语：Лысе́нковщина）指的是在苏联科学家特罗菲姆·邓尼索维奇·李森科及其追随者主导之下对基因学和农业科学的政治控制。李森科是苏联农业科学联合会
美国西南研究院美国西南研究院（英语：Southwest Research Institute，简称SwRI）是美国其中一个历史最悠久、规模最庞大的独立非营利性质应用技术研发机构，总部位于美国得克萨斯州圣安东尼奥，由美国
罗马尼亚社会主义共和国罗马尼亚社会主义共和国是二战后在罗马尼亚建立的社会主义政权，罗马尼亚共产党为执政党。在1947至1965年间的正式名称为罗马尼亚人民共和国（罗马尼亚语：Republica Populară Ro
智异山智异山国立公园（朝鲜语：지리산국립공원／智異山國立公園 Jirisan Gungnip Gongwon */?）是位于韩国全罗南道求礼郡、全罗北道南原市以及庆尚南道咸阳郡、山清郡、河东郡的山岳型
谢道时谢道时（1948年3月16日－2016年8月4日），台湾生物化学家，第二十九届中央研究院院士，2009年起任中央研究院细胞与个体生物学研究所所长。谢道时1970年毕业于中华民国国立台湾大学化学
尼古拉斯·卡岑巴赫尼古拉斯·德贝尔维尔·卡岑巴赫（Nicholas deBelleville Katzenbach，1922年1月17日－2012年5月8日），美国律师、政治家，美国民主党人，曾任美国司法部长（1965年-1966年）。卡岑巴赫出生于
马诺夸里马诺夸里（印尼语：Manokwari）又译曼诺瓦里，是印度尼西亚西巴布亚省的第二大城市以及西新几内亚的第五大城市，也是西巴布亚省的首府和马诺夸里县的县治所在。城市位于新几内亚岛西
维尔纳综合征维尔纳综合症（Werner syndrome，缩写WS）又称成人早衰症，是一种极为罕见的常染色体隐性遗传性早衰症，1904年由德国人 Otto Werner 首先报道，患者位于8号染色体短臂的、编码DNA螺旋酶