计算几何

✍ dations ◷ 2025-10-20 20:37:14 #计算机科学,理论计算机科学,数位几何学,计算几何

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

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

相关

狂犬病狂犬病疫苗是指用来预防狂犬病的疫苗。目前已有很多有效且安全的疫苗。在暴露于病毒（例如被狗或蝙蝠咬）之前或之后一段时间都可以施打狂犬病疫苗。在接种三剂后可以有长期的免
浮肾浮肾（Nephroptosis）是由于肾脏外部在正常情况下没有其他固定的组织结构支撑，若其外包覆脂肪囊（adipose capsule）的脂肪量过少，或是缺乏肾囊（renal capsule），将造成浮动的现象，又称为游
神经组织神经组织是四大基本组织之一，由神经细胞和神经胶质细胞组成。神经细胞通过突触相连接形成复杂的神经网络，具有感受内外刺激、传导整合信息的能力。神经胶质细胞对神经元起支持
仡佬字陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文籀文 ‧ 鸟虫书 ‧ 篆书（大篆 ‧ 小篆）隶书 ‧ 楷书 ‧ 行书 ‧ 草书漆书 ‧ 书法 ‧ 飞白书笔画 ‧
霍尔县霍尔县 (Hall County, Georgia)是美国乔治亚州北部的一个县。面积1,112平方公里。根据美国2000年人口普查估计，共有人口139,277人。2005年增至165,771人。县治盖恩斯维尔 (Ga
罗兰弗兰克·舍伍德·罗兰（英语：Frank Sherwood Rowland，1927年6月28日－2012年3月10日），美国化学家，因“他们对大气化学的研究工作，特别是臭氧的形成与分解”，与马里奥·莫利纳、保罗·克
C02A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码C02（抗高血压药）是解剖学治疗学及化学分类系统的一个药物分组，这是由世界卫生组织药物统计方法整合中心（The WHO Collabor
每日简报《总统每日简报》（英文：President's Daily Briefing，缩写：PDB.）是每天早上呈交给美国总统的一份高度机密的情报文件，由下属的中央情报局、国防情报局、国家安全局等其他美国情报机
纽澳军团级巡防舰安扎克级巡防舰，或者纽澳军团级巡防舰（英语：Anzac-class frigate）是以德国MEKO 200型为基础设计修改，由澳大利亚Tenix防卫系统公司建造的巡防舰。采用模组化设计，舰上设备由新西兰
纳拉扬希蒂王宫坐标：27°42′56″N 85°19′12″E / 27.71556°N 85.32000°E / 27.71556; 85.32000纳拉扬希蒂王宫（尼泊尔语：नारायणहिटी दरवार संग्रहालय）位于尼泊尔