这篇文章上次修改于 328 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

ACM程序课算法笔记9——计算几何入门

线段属性

1.给两条有向线段p0p1和p0p2,线段1是否在线段2顺时针方向?

2.给两条有向线段p0p1和p1p2,线段2是左拐还是右拐?

3.给两条有向线段

平面叉乘

对于向量u=(u1,u2)和 v=(v1,v2) 它们的叉乘定义如下:u x v = u1v2 - u2v1 = |OU||OV|sin a 并且

u x v > 0, v在p的右方向 即向量u在向量v的顺时针方向

u x v < 0, v在p的左方向 即向量u在向量v的逆时针方向

u x v = 0, 两个向量共线

判断相交

给定P1P2和P3P4,如何判断他们相交?

P3P4 x P3P1和P3P4 x P3P2能判断P1P2是否在P3P4的两端

再判断P3P4是否在P1P2的两端即可。

如果 P3 在P1P2中间,判断P3在P1P2中间,可以使用坐标判断,但不能只判断x或者只判断y,需要两个都判断(水平垂直特殊情况)

面积

给定一个简单多边形,求其面积

三角形的面积求法

abs(u1v2 - u2v1) = 2 S△OUV

多边形的面积求法

便于理解,可以分割多边形的面积成n个三角形,对于n个三角形,都用叉积计算三角形面积,然后相加就可以获得多边形面积。

但以上为了便于理解和记忆,这个点选在多边形内部。

但对于叉积,有正负性的特点,所以这个点可以选在外面

为了便于计算,我们通常会把点选为原点,因此有求面积公式:

重心

三角形的重心求法

重心公式:

x0 = (x1 + x2 + x3) / 3

y0 = (x1 + x2 + x3) / 3

多边形的重心求法

将多边形变为n个三角形,分别求n个三角形的面积和重心

根据面积带权取平均值就是重心。公式:

凸包问题

假设平面上有多个点,过某些点作一个多边形,使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候,我们就叫它“凸包”。

给定多个点,求形成凸包的点有哪些?

葛立恒扫描法(Graham’s scan)

算法笔记1博客

贾维斯步进法(Jarvis March)

1、首先由一点必定在凸包的点开始,例如最左的一点A1。

2、找到所有点中极角排序最小的,这个点就是第二个点。使得所有点都在A1A2的右方以A2为原点。

3、重复此步骤,依次找到A3,A4,…,Ak。共有K步。因此,时间复杂度是O(kn)。

安德鲁算法(Andrew)

1、把所有的点以X坐标为主序从小到大排序;

2、显然,排序后的第1个点和最后1个点一定在凸包上;

3、从左到右扫描一遍(左转才入数组 ,否则删点, 循环判断,直到得到下凸部分);

4、从右到左再扫一遍(同上,得到上凸部分);

5、函数返回凸包中的点的数目(方便处理凸包)。

函数结束后,数组中的点即为凸包上的点。