A simple Blog for wyx I've been down the bottle hoping.
计算几何学习笔记
发表于: | 分类: Oi | 评论:0 | 阅读:96

[TOC]

写在前面

省选之后决定自己要去 $pkusc$, 然后发现自己计算几何一点都不会,这样下去早晚药丸啊……

所以就大力学习了一天的计算几何,题还没怎么写,但是先把理论建立出来……

陆续的还会有上下界网络流学习笔记,博弈论学习笔记,ETT学习笔记 (我先挖坑,填不上的时候抓紧叫我我好填……

然后这些搞完之后就要大规模重新复习算法辣~

希望在不断的努力下能够有更大的突破

正文

我比较弱下面所有的东西都是二维计算几何

点是最基本的单位,在平面内我们用二元组 $(x,y)$ 表示一个点,容易发现所有的点放在一起就构成了一个平面。

平面内任意两个点间的距离为$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

直线

在计算几何中我们摒弃原有的一般式 $ax+by+c=0$,而更多才用一个点加上一个向量来表示一条线,所以我们还得说一下向量

向量

向量是有向线段,有向线段的长度是向量的大小,方向表示向量的方向,以 $A$ 起点指向 $B$ 记做向量 $\vec{AB}$, $|\vec{AB} |$叫做向量的模,模为一的为单位向量,模为0的叫零向量。

为了表示方便,我们会把起点挪到原点,这样就可以用终点坐标来表示一个向量了。

所以代码实现中,向量和点都用 $(x,y)$ 表示

向量有自己的运算规则,这里直接给出

$(x_1,y_1)+(x_2,y_2) = (x_1+x_2,y_1+y_2)$

$(x_1,y_1)-(x_2,y_2) = (x_1-x_2,y_1-y_2)$

$x\times (x_1,y_1) = (x_1\times x, y_1\times x)$

然后介绍几个比较厉害的东西

点积

$(x_1,y_1)\times (x_2,y_2) = x_1x_2+y_1y_2$

这个是最常用的一个式子,还有一个表示是

$\vec{a} \times \vec{b} = |\vec{a}| |\vec{b}| cos(\theta)$

通过上面的式子不难发现 $a\times b = b\times a$, $\lambda(\vec{a} \vec{b}) = (\lambda \vec{a})\times \vec{b} = \vec{a} \times (\lambda \vec{b})$, $(\vec{a}+\vec{b})\times \vec{c} = \vec{a}\times \vec{b} + \vec{b}\times \vec{c}$

在后面为了区分我用 $\times$ 表示点积

叉积

这东西更有用些,计算几何后面好多都用得到

$(x_1,y_1)\cdot (x_2,y_2) = x_1y_2-x_2y_1$

这个是最常用的一个式子,还有一个表示是

$\vec{a} \cdot \vec{b} = |\vec{a}| |\vec{b}| sin(\theta)$

他是 $\vec{a}$ 和 $\vec{b}$ 形成的平行四边形的有向面积

通过上面的式子不难发现 $a\cdot b = -b\cdot a$, $\lambda(\vec{a} \vec{b}) = (\lambda \vec{a})\cdot \vec{b} = \vec{a} \cdot (\lambda \vec{b})$, $(\vec{a}+\vec{b})\cdot \vec{c} = \vec{a}\cdot \vec{b} + \vec{b}\cdot \vec{c}$

在后面为了区分我用 $\cdot$ 表示叉积

旋转向量

如何旋转一个向量?

请看图……如果你看到这些字说明他挂了

恩……所以 $(x,y) \to (x cos(\theta)-y sin(\theta), x sin(\theta) + y cos(\theta))$

向量的极角

就是向量从 $x$ 轴正半轴逆时针转过的角度

系统里我们可以用 $\texttt{atan2(y,x)}$ 来获取极角

向量和点的运算

点+向量 = 点

点-向量 = 点

向量+向量=向量

向量-向量=向量

点-点=向量

恩……我们可以回到直线辣

现在我们已经可以用 $a+\vec{b}$ 来表示一条直线了

你看,根本没有斜率这档子事情,自然少了非常多的麻烦。

后面的直线不特殊说明的话都是这个形式

点到直线的距离

在解析几何中我们有一个非常玄妙的公式

$ax+by+c=0$ 到 $(x_0,y_0)$ 的距离为 $\frac{ax_0+by_0+c}{\sqrt{a^2+b^2}}$

但是现在就不用啦,考虑那个距离必然是形成的平行四边形的高.但是平行四边形的面积就是叉积!

所以 $Q$ 到直线 $P+\vec{b}$ 的距离就是$\frac{\vec{b}\cdot \vec{PQ}}{|\vec{b}|}$

点到线段的距离

求出在直线的距离,然后用叉积判一下是否在线段上

具体的判断方法如图啦啦啦

如果在线段上那就是这个值了,否则必然是到两个端点的距离中较小的一个

直线求交点

恩这个也是非常重要的东西,我们还是看图

……跨立实验

线段相交

分为规范相交和不规范相交,差别在于不规范可以经过端点。

对于不规范我们可以通过规范+特判

考虑如果两个线段规范相交必然对于两条直线都有自己的两个端点被另个一直线分在两侧

所以直接两个叉积就判掉了。这个实验貌似叫跨立实验……

多边形

若干条线段首位顺次连接形成的平面图形,多边形分为凸多边形和凹多边形

一般来说按照顺时针或者逆时针存储所有点

多边形的面积

注意到叉积算出来的东西是有向面积,因此我们可以直接选一个点算一下他和相邻两个节点形成的”三角形“的有向面积就行了

如果是凸多边形还有一个算法是三角剖分,这两个用处都很广泛

判断点是否在多边形内部

多使用射线法:任意引出一条射线,如果和边的交点的个数为奇数个就在内部,否则在外部

注意到我说的是和边的交点,所以对于多边形的一个顶点他的贡献是2而不是1

为了避开这个闹听的问题可以让射线的斜率为无理数

凸包

定义

把规范定义扔进垃圾桶,我们用一个人能听得懂的定义

凸包其实就是一个尽量小的凸多边形然后包住了所有的点

更形象的定义是把点看成是木桩,然后用一个橡皮筋套在上面

求凸包

有两个方法,极角法和水平法

极角法求凸包

1.取出纵坐标最小的点,多个取横坐标最小的

2.把这个点当做原点然后其他点按照极角排序

3.按顺序扫一遍,用单调栈维护凸的性质即可。

注意这个方法不能维护共线的情况

水平法求凸包

1.按照 $x$ 为第一关键字 $y$ 为第二关键字排序

2.分两次求上下凸壳,

注意到求极角的时候常数大且精度误差大,但是极角法代码比较好写

关于凸包的一个随机性质

给定一个随机的 $n$ 个点的图,那么他的凸包上只有 $\log(n)$ 个点。在数据随机的情况下可以直接暴力

旋转卡壳

注意读音,旋转卡(qia)壳(qiao)

还是先搞几个定义

对踵点

如果凸多边形上的两个点能通过两条平行的直线吧整个凸多边形夹在中间,这两个点就叫做对踵点

旋转卡壳就是求对踵点的算法

做法

维护两个点,枚举第一个点,然后容易发现第二个点的取值是单峰的,而且第一个点在向后的过程中第二个也在向后

所以可以像two-pointer一样搞一下。

最远点

给定点集 $X$, 求 $X$ 中最远点对之间的距离

求凸包然后最远点必然是对踵点对之一

半平面交

给定若干半平面,求他们的交集的过程就是半平面交

暴力插入每个平面求交复杂度是 $O(n^2)$ 的

然后把所有平面按照极角排序按顺序加进去,用双端队列维护当前的交集,每次长度要对队首和队尾更正,

复杂度是 $O(n\log(n))$ . 细节较多。

辛普森积分和自适应辛普森积分

辛普森积分

用二次函数的积分来不断拟合被积分函数

考虑三个点 $(a, f(a)), (b, f(b)), (c, f(c)), c = \frac{a+b}{2}$

我们拉格朗日插个值

然后就有了一个非常优雅的式子

$$f(x) = \frac{(x-b)(x-c)}{(a-b)(a-c)}f(a) + \frac{(x-a)(x-c)}{(b-a)(b-c)} f(b) + \frac{(x-b)(x-a)}{(c-b)(c-a)} f(c)$$

然后我们就可以愉快的积分啦

$\int_a^b{f(x)}dx = \frac{b-a}{6}{f(a)+f(b)+4f(c)}$

自适应辛普森积分

考虑到上面那个式子其实只支持了二次函数。我们尝试着让他解决更高次的东西。

我们强行带一下这个东西,然后再取一个位置 $t$, 算一下左面和右面,如果相差不大就用这个,否则递归左右

这个东西在迭代次数够多的时候就近似是答案了。

kdtree

这个就不讲了吧……其实和计算几何没什么大关系。

文末总结

这里只写了常用的计算几何的知识点,那么还有一部分习题将会在不久之后放在博客上……

码了这么多看一遍应该还是有点收获的吧Orz

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP