计算几何

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

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

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

相关

心音在生理学中，心音（英语：heart sounds），即心脏的声音，是心脏在运作时，血液流经心脏时产生的震动波。具体来说，是瓣膜开起与关闭时产生的湍流造成的震动波，或由心肌收缩、心脏瓣膜关闭和
唐纳德·戴维森唐纳德·赫伯特·戴维森（英语：Donald Davidson，1917年3月6日－2003年8月30日）20世纪下半叶美国最为著名和活跃的哲学家之一。戴维森1917年3月6日生于美国麻省斯普林菲尔德。在早期
唐纳德·威尼科特唐诺·伍兹·温尼考特（Donald Woods Winnicott，1896年4月7日－1971年1月28日），英国儿童心理学家、精神分析学家，对客体关系理论有一定贡献。他在40年的时间里研究人类成长，希望阐明
益智药益智药（促智药、nootropics、English pronunciation: 发音： /noʊ.əˈtrɒpᵻks/ noh-ə-TROP-iks）也被称为智能药物（smart drugs）或认知增强剂（cognitive enhancers），用于改善健康
Fas通路细胞凋亡（英语：apoptosis，源自希腊语：απόπτωσις，有“堕落、死亡”之意），为一种细胞程序性死亡。相对于细胞坏死（necrosis），细胞凋亡是细胞主动实施的。细胞凋亡一般由生理或
2018年5月25日公投通过修宪，准许堕胎爱尔兰宪法第三十六条修正案（2018年第二十九条法案）是爱尔兰宪法的一项修正案，允许爱尔兰议会立法允许堕胎，废除第八修正案（即1983年宪法修正案（英语：Eighth Amendment of the Cons
优素福·哈比比帕夏鲁丁·优素福·哈比比（印尼文： Bacharuddin Jusuf Habibie 帮助·信息，1936年6月25日－2019年9月11日），印尼前总统。他是印尼自独立以来的第三任总统，在位期间是苏哈托下台后的
经纬度地理坐标系一般是指由经度、纬度和相对高度组成的坐标系，能够标示地球上的任何一个位置。经度和纬度常合称为经纬度，把球面上的经纬度显示在平面地图上需要采用某种地图投影。
第八机械工业部中华人民共和国农业机械部是的中华人民共和国国务院原有的一个组成部门，主管农业机械事务，1959年8月成立农业机械部。1970年7月1日并入第一机械工业部为农机局。1965年1月改称
鄞州区.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature-settings: