计算几何学习笔记

2022/8/1 23:25:59

本文主要是介绍计算几何学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

【计算几何】学习笔记

计算几何,即用电脑解决几何问题,可以大致分为二维计算几何和三维计算几何。因作者实力有限,本文仅介绍二维计算几何中比较基础的部分QAQ 如有表述不当请提醒!

二维计算几何,在平面上进行,通常有着点、线、面的参与,用于解决一些几何问题。本文将先讲解一些数学上几何的基础部分,然后再就 OI 中计算几何的运用讲解知识点。

让我们从最基础的开始吧!

目前还没有但预计会有的知识点:

  • 点之间的距离以及相关技巧(欧式距离,曼哈顿距离,切比雪夫距离)

  • 凸包及其运用

  • 旋转卡壳及例题讲解

  • 随机增量法

  • 半平面交(现在不会,以后可能会学)

  • 一些计算几何杂题选讲以及题解。

基础篇-面

先来说说坐标系吧,我们讨论几何的基础。

平面直角坐标系

二维平面,总得有个依托。而我们需要一个能够承载几何图形的工具,不然我们连点、线等最基础的几何图形都无法表达。而我们现在,有一个非常有用的平面:平面直角坐标系,又称笛卡尔坐标系。

平面直角坐标系在二维中,由两条垂直的 \(x\) 轴、\(y\) 轴分成四个象限,交点为原点,并用二维数对 \((x_0,y_0)\) 即可表示平面上任意一个点。而我们的讨论,也将基于此。

极坐标系

你需要事先知道:角度的弧度制,基本的三角函数(起码知道概念)。

直角坐标系好,但在有些时候运算并不是那么方便。有时候,我们也会需要别的坐标系。而极坐标系不同于直角坐标系用二维数对表示坐标,它引入了角度这一表示方式。极坐标系有一极点 \(O\),一条发自极点的射线极轴单位长度正方向角度单位,即可构造出极坐标系。而表达一个点 \(A\) 时,我们则用这个点到极点的距离极径 \(\rho\) 以及与极径在正方向上的夹角极角 \(\theta\) 表示。这样用相对于极点的长度以及相对于极径的角度,即可唯一表示出唯一一个点 \((\rho,\theta)\)。

而这样一个坐标系有什么用呢?很多时候我们并不是完全用极坐标表示,而是利用极坐标做一下事情,比如:按照极坐标的角度排序,可以用于求凸包等。

两者转换

我们最常用的极坐标系即为以 \(x\) 正半轴为极轴,直角坐标系的原点为极点、单位长度不变、弧度制为角度单位、逆时针为正方向。接下来的解释都以此为基准。

对于一个点 \(A\),它的极坐标 \((\rho,\theta)\)如何转换成直角系坐标 \((x,y)\) 呢?我们知道如果 \(\rho=1\),那这个点相当于是在单位圆(即以原点为圆心,\(1\) 为半径的圆)上。而知道角度,我们可以很方便的用三角函数求出 \(x\) 与 \(y\) 坐标。简单来说,坐标即为 \((\cos \theta,\sin \theta)\)。这是三角函数基础知识。而如果 \(\rho\) 不为 \(1\) 怎么办?等比例放大即可,相当于在以原点为圆心,\(\rho\) 为半径的圆上。因此坐标乘个 \(\rho\) 即可,坐标即为 \((\rho\cos \theta,\rho\sin \theta)\)。

那直角坐标 \((x,y)\) 如何转换为极坐标呢?先考虑极径。这个可以直接上个两点之间距离公式(下面会讲)即可。接下来考虑极角。其实这个可以直接用系统内置函数,\(atan2(y,x)\) 即为弧度制的极角。而几何意义即为反正切函数,属于三角函数内容。而为什么要加个 \(2\) 呢?因为 \(atan2\) 函数比 \(atan\) 精度更高,更为实用。因此,极坐标即为 \(\left(\sqrt{x^2+y^2},\tan2(y,x)\right)\) (右边的为距离公式化简)。

这一部分是计算几何的基础。如果极坐标系不了解问题不大,因为并不是所有题目都需要,可以以后学完三角函数再来学。但是直角坐标系一定要熟练运用,否则几何部分会学的很艰难。

基础篇-点

点,抽象理解一下可以理解为零维空间。而正是无数个点,构成了点,线,面……而我们讨论的点,都是在二维或者三维空间中的一个点。

一个点,在平面直角坐标系上的坐标即为 \((x,y)\),而在极坐标上的坐标即为 \((\rho,\theta)\)。我们在 C++ 中通常用结构体封装一下,以方便计算。

两点之间距离

这里只是讲一下欧式距离(即欧几里得距离,我们常用的直线距离)。两点之间的直线距离即为:

\[\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]

这个公式的推导需要用到初中学到的勾股定理。其实也很好理解,我们考虑两个点的距离相对当于两个点构成的直角三角形斜边长,而斜边可以用直角边求出。直角边的绝对值即为坐标差,但平方之后绝对值加不加无所谓。

同时我们考虑如果要扩展到三维,就是根号内加个 \((z_1-z_2)^2\) 即可。

好像没有什么好讲的了……点主要还是要与其他几何概念结合着用,单独的点并没有什么好讲的。下面会有有关点的更多讨论。

基础篇-线

请注意,本部分的线不仅包括直线,还包括曲线,包括一些函数曲线(比如圆)。同时会提到向量。

我们计算几何中,各种各样的线是非常常见的。让我们来认识一下他们吧!

直线

直线算是很常用的了。而直线在几何中的重要性也不言而喻了。

先考虑怎么表示一条直线吧。首先,一个常用的方法就是用初中学的一次函数斜截式表示,形为 \(y=kx+b\) 。其中 \(k,b\) 都是系数。这种方式很好用,很方便,却也有着局限性:不能表示出所有直线,当直线与 \(x\) 轴垂直时,斜截式便无法正确表示出来该条直线了。比如直线 \(x=3\),那这都不算一个函数了一个 \(x\) 对应着无数个 \(y\),又何谈用函数表达式表示呢?因此,很多时候使用斜截式可行,但有时就不行了。

因此,别的表示直线的方式出现了。高中学到的直线一般式可以表示出所有直线,它的表达式为一个二元一次方程,形如 \(Ax+By+C=0\)。这个式子可以表示出任意直线,平时可以比较方便的用它进行一些操作。而像点到直线距离公式,两直线交点等问题,用直线一般式是可以很好地解决的。

但是,还有另一种方法:点向式。这种方法用一个点以及一个方向向量表示,从另一个角度表示了一条直线。这种方法可以利用向量很多优雅的运算达到出乎意料的效果,也是非常好用。但是我不会

剩下的没写完,会持续更新。



这篇关于计算几何学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程