大家好，欢迎来到IT知识分享网。

计算几何-基础篇

计算几何

定义：对几何外形信息的计算机表示分析。（其实就是利用计算机建立数学模型解决几何问题。）

计算几何研究的对象是几何图形。早期人们对于图像的研究一般都是先建立坐标系，把图形转换成函数，然后用插值和逼近的数学方法，特别是用样条函数作为工具来分析图形，取得了可喜的成功。然而，这些方法过多地依赖于坐标系的选取，缺乏几何不变性，特别是用来解决某些大挠度曲线及曲线的奇异点等问题时，有一定的局限性。

平面直角坐标系

平面直角坐标系其实就是笛卡尔坐标系，在计算几何中，我们经常会用到坐标表示，点和向量都是通过坐标来保存的。

向量及其运算

向量的基础知识

向量（也称为欧几里得向量、几何向量、矢量）：既有大小又有方向的量称为向量。在数学中研究的向量为自由向量，即只要不改变它的大小和方向，起点和终点可以任意平行移动的向量。记\(\vec{a}\)或a。

有向线段：带有方向的线段称为有向线段。有向线段三要素：起点，方向，长度，有了三要素，终点就唯一确定。我们用有向线段表示向量。

向量的模：有向线段\(\overrightarrow{AB}\)的长度称为向量的模，其实就是向量的大小。即为\(|\overrightarrow{AB}|\)或\(|\vec{a}|\)。

零向量：模为零的向量。零向量的方向任意。

单位向量：模为1的向量称为该方向上的单位向量。

平行向量：方向相同或相反的两个非零向量。记作\(a\parallel b\)。对于多个互相平行的向量，可以任作一条直线与这些向量平行，那么任一组平行向量都可以平移到同一直线上，所以平行向量又叫共线向量。

滑动向量：沿着直线作用的向量称为滑动向量。

固定向量：作用于一点的向量称为固定向量。

相等向量：模相等且方向相同的向量。

相反向量：模相等且方向相反的向量。

向量的夹角：已知两个非零向量\(\vec{a},\vec{b}\),作\(\overrightarrow{OA}=\vec{a},\overrightarrow{OB}=\vec{b}\)，那么$\theta=\angle AOB $ 就是向量\(\vec{a}\)与向量\(\vec{b}\)的夹角。记作：\(\left\langle a,b \right\rangle\)，显然当\(\theta=0\)时，两向量同向，\(\theta= \pi\)时两向量反向，\(\theta = \frac{\pi}{2}\)时，两向量垂直，记作\(\vec{a} \perp \vec{b}\)。并且我们规定\(\theta \in [0,\pi]\)。

\({\color{Red}注意}\)：平面向量具有方向性，我们并不能比较两个向量的大小（但可以比较两向量的模长）。但是两个向量可以相等。

向量的运算

设\(\vec{a}=(x_1,y_1)\),\(\vec{b}=(x_2,y_2)\)。

加减法

既然向量具有平移不变性，那么\(\vec{a}+\vec{b}\)就是将两条有向线段相连，即:\(\vec{a}+\vec{b}=(x_1+x_2,y_1+y_2)\)。

那向量的减法\(\vec{a}-\vec{b}\)，其实就是\(\vec{a}+(-\vec{b})\),即\(\vec{a}-\vec{b}=(x_1-x_2,y_1-y_2)\)。

向量的加减法是满足以下法则的：

• 三角形法则：若要求和的向量首尾顺次相连，那么这些向量的和为第一个向量的起点指向最后一个向量的终点；
• 平行四边形法则：若要求和的两个向量共起点，那么它们的和向量为以这两个向量为邻边的平行四边形的对角线，起点为两个向量共有的起点，方向沿平行四边形对角线方向。

所以说向量的加减法就有了几何意义，并且满足交换律和结合律。

数乘

规定\(\left\lceil 实数\lambda与向量\vec{a}的积 \right\rfloor\)为一个向量，这种运算就是数乘。记作\(\lambda\vec{a}\),并且满足以下性质：

• \(|\lambda\vec{a}|=|\lambda||\vec{a}|\)；
• 当\(\lambda>0\)时，\(\lambda\vec{a}\)与\(\vec{a}\)同向，当\(\lambda=0\)时，\(\lambda\vec{a}=0\)，当\(\lambda<0\)时，\(\lambda\vec{a}\)与\(\vec{a}\)方向相反。

（向量的数乘其实就是对向量进行放缩）

点积

向量的点积也叫数量积、内积，向量的点积表示为\(\vec{a}·\vec{b}\),是一个实数。计算式为：

三角形恒等变换的推导：

同时点积是满足交换律，结合律和分配律的。

点积应用：

叉积

也叫矢量积，外积。几何意义是两向量由平行四边形法则围成的面积。叉积是一个向量，垂直于原来两个向量所在的平面。（根据叉乘的模是平行四边形的面积我们可以想象，叉乘的结果是一个有方向的面，而面的方向平行于面的法线，所以面的方向垂直于面上任何一个向量），即：

并且，\(\vec{a}×\vec{b}=(x_1y_2-x_2y_2)\)。

叉积是一个有向面积：

• \(\vec{a}×\vec{b}=0\)，等价于\(\vec{a},\vec{b}\)，共线（可以反向）；
• \(\vec{a}×\vec{b}>0\)，\(\vec{b}\)在\(\vec{a}\)左侧；
• \(\vec{a}×\vec{b}<0\)，\(\vec{b}\)在\(\vec{a}\)右侧。

判断两向量共线

两个非零向量\(\vec{a}\)与\(\vec{b}\)共线\(\iff\)有唯一实数\(\lambda\)，使得\(\vec{b}=\lambda\vec{a}\)。由向量的数乘即可得证。

推论：如果\(l\)为已经过点A且平行于已知非零向量\(\vec{a}\)的直线，那么对空间任一点O，点P在直线\(l\)上的充要条件是存在实数\(t\)，满足等式：\(\vec{OP}=\vec{OA}+t\vec{a}\)。

其中向量\(\vec{a}\)叫做直线\(l\)的方向向量。

基本定理和坐标表示

平面向量基本定理

平面向量基本定理：两个向量\(\vec{a}\)和\(\vec{b}\)不共线的充要条件是，对于和向量\(\vec{a}\)，\(\vec{b}\)共面的任意向量\(\vec{p}\)，有唯一实数对\((x,y)\)满足\(\vec{p}=x\vec{a}+y\vec{b}\)。

证明(非常简单):

在同一平面内的两个不共线的向量称为基底。

如果基底相互垂直，那么我们在分解的时候就是对向量正交分解。

平面向量的坐标表示

如果取与横轴与纵轴方向相同的单位向量\(i,j\)作为一组基底，根据平面向量基本定理，平面上的所有向量与有序实数对\((x,y)\)一一对应。

而有序实数对

而有序数对\((x,y)\)与平面直角坐标系上的点一一对应，那么我们作\(\vec{OP}=\vec{p}\)，那么终点\(P(x,y)\)也是唯一确定的。由于我们研究的都是自由向量，可以自由平移起点，这样，在平面直角坐标系里，每一个向量都可以用有序实数对唯一表示。

坐标运算

平面向量线性运算

由平面向量的线性运算，我们可以推导其坐标运算，主要方法是将坐标全部化为用基底表示，然后利用运算律进行合并，之后表示出运算结果的坐标形式。

对于向量\(\vec{a}=(m,n)\)和向量\(\vec{b}=(p,q)\)，则有：

向量的坐标表示

已知两点\(A(a,b),B(c,d)\),则\(\vec{AB}=(c-a,d-b)\)。

平移一点

将一点\(P\)沿一定方向平移某单位长度，只需要将要平移的方向和距离组合成一个向量，利用三角形法则，用\(\vec{OP}\)加上这个向量即可，得到的向量终点即为平移后的点。

三点共线的判定

在平面上\(A,B,C\)三点共线的充要条件是：\(\vec{OC}=\lambda\vec{OB}+(1-\lambda)\vec{OA},(O为平面内不与直线AC共线任意一点)\)。

证明：

向量旋转

设\(\vec{a}=(x_1,y_1)\)，那么长度\(l=\sqrt{x^2+y^2}\)。若将顺时针旋转\(\theta\)度得到\(\vec{b}=(x_2,y_2)\)，则有：

可以用点积或三角形恒等变换易证。

计算几何基础的内容就到这里了，现在计算几何的基础都已经掌握了的话，就可以去写更深层次的算法了，完结撒花~。