[原创]【计算几何各种知识点总结】[不定期补充]

Tabris

CSDN计算几何模板

发布于：2016年4月10日

次浏览

[原创]【计算几何各种知识点总结】[不定期补充]

2016-04-10 19:26:51 Tabris_ 阅读数：3490

博客爬取于 2020-06-14 22:39:21
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51114511

# 计算几何模板总结 ：

http://blog.csdn.net/qq_33184171/article/details/51124611

精度控制

尽量不要用除法，三角函数，强制类型转换（尤其是 double 转 int）等操作，否则精度损失比较大 。
const double PI = acos(-1.0);
const double EPS = 1e-8;
对小数点后 1 位 取整 的方法为 ±1 （+1 位进位 -1 为退位）
eg：8(double)=7.9999999999....;
8(int)=8;
int(8(double))=7; !!!!!!
这样精度损失就大了~~~~

杂点

精度问题

1.在用 1e-n 判断相等的时候不是 n 越大越好 要选择合适的 ，一般为 6/8/9/10
2.判断两条线段距离大小关系的时候有平方倍进行比较。
3.未完待续。。。

点与其他图形的位置关系

点与直线的位置关系

首先明确点与直线的位置关系只有两种：
1.点在直线上

2.点不在直线上

在这里只要用叉积判断就可以了
以上图为例只需满足向量a\cdot b \times a\cdot c=0即可
如果叉积等于 0 则说明两向量共线 所以点在直线上
如果叉积不为 0 则说明点不在直线上

点与线段的关系

知道了如何判断点与直线的位置关系在来判断点与线段的位置关系就容易多了
跟直线类似点与线段也只有两种位置关系：
1.点在线段上
2.点不在线段上

如果点在线段上则需满足以下两种情况：
1.点在线段所在的直线上。
2.点在以线段为对角线的矩形内。
前者很好理解，而后者则确保点不在线段的两端延长线上。
所以除了判断叉积还要判断坐标关系
以下图为例

很容易得出
应满足以下结论

c.x> min(a.x,b.x);
c.x< max(a.x,b.x);
c.y> min(a.y,b.y);
c.y< max(a.y,b.y);
这样就满足了点在矩形内
当然不能忘记用叉积判断；；；

点与三角形的内外

先要说明，当点在三角形边上的时候视为点在三角形的内部
在这里我们运用面积关系来判断点在三角形的内外

观察 S△dab+S△dbc+S△dac 与 S△abc 的大小关系
观察上两图不难发现当点在三角形内是 S△dab+S△dbc+S△dac 是相等于 S△abc 的
而点在三角线外的时候
S△dab+S△dbc+S△dac 是大于 S△abc 的

所以只要计算出两式的大小关系即可
Ps：这里求面积运用的为叉乘，\overrightarrow{ab} \times\overrightarrow{ac}就是 延伸出去的平行四边形的面积
S△_{abc}=\dfrac{\overrightarrow{ab} \times\overrightarrow{ac} }{2}；

判断大小关系的时候不用除以 2 直接判断即可 且更加精确

线段相交

判断两线段是否相交

判断两个线段是否相交，要先想一下两条线段之间都有什么样的位置关系。
1.相离

2.相交

3.重合

4.平行

观察了上面 4 个图片 可以明显的观察到 相交与其他 3 种的不同
一条线段的两个端点分别在另一条线段的两边
了解了这些加上叉乘就可以进行计算了
Ps：如果不了解叉乘的话必须先了解下叉乘，但我相信能做到求线段相交的人一定对叉乘有了全方位的了解
首先我们知道如果两个点在在一条线段两侧 那么对于线段两端与这两个点分别做叉乘计算取得的积一定是小于 0 的
可以得到以下结论

(\overrightarrow{CD} \times\overrightarrow{DA})\cdot(\overrightarrow{CD} \times\overrightarrow{DB})<0;
(\overrightarrow{AB} \times\overrightarrow{BD})\cdot(\overrightarrow{AB} \times\overrightarrow{BC})<0;

其实想也很好想
如果两个线段不想交那么势必存在一条线段的两个端点在另一条线段同侧，上述式子就不能满足。
所以通过计算上述式子也就能知道两线段是不是相交了。
但是在实际计算中如果数据量非常大的话那么我们总是计算 4 遍叉乘的话会很麻烦
所以要考虑更简单的判断两条线不相交的办法来排除一些情况，当然也只能排除一些情况而已，但即使这样也能使整个程序运行的快一些。
我们可以通过判断这两条线段的四个点的关系来淘汰很多点：
(这部分证明并没有什么意义，大家想想即可明白，在此就不赘述了，支架以代码形式给出)

max(s1.x,e1.x) < min(s2.x,e2.x)
max(s2.x,e2.x) < min(s1.x,e1.x)
max(s1.y,e1.y) < min(s2.y,e2.y)
max(s2.y,e2.y) < min(s1.y,e1.y)
这 4 中情况都是不相交的

======
上述已经介绍了如何判断线段相交，该上代码了

1
2
3
4
5
6
7
8
9
10
11
12

double multi(Point p1,Point p2,Point p0){
    return ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
}

bool IsIntersected(Point s1,Point e1,Point s2,Point e2) { //两个线段相交
    return(max(s1.x,e1.x)>=min(s2.x,e2.x))&&
          (max(s2.x,e2.x)>=min(s1.x,e1.x))&&
          (max(s1.y,e1.y)>=min(s2.y,e2.y))&&
          (max(s2.y,e2.y)>=min(s1.y,e1.y))&&
          (multi(s1,s2,e1)*multi(s1,e2,e1)<=0)&&
          (multi(s2,s1,e2)*multi(s2,e1,e2)<=0);
}

求两圆相交面积

两个圆的位置一共有五种情况
1.内含 2.内切 3.相交 4.外切 5.外离
在计算几何中 内含与内切 可以当做同一种情况 外切与外离 可以当做同一种情况
Ps：如果有疑问可以自己画一画图 就会明白了

所以在计算几何中只要分成 3 种情况就行了
先定义 d 为两圆圆心距离

1.外离

外离
这种情况下 d>=r1+r2
两圆间没有相交的部分
所以相交面积是 0

2.内含

内含
这种情况下 大圆把小圆全部覆盖
相交的面积就是校园的面积 PI * r1 * r1
此情况下 d<=r 大-r 小
写成代码就是 d <= fabs(r1 - r2)

3.相交

相交
相交的部分可以分成 大小两个圆上弧 ab 与直线 ab 围成的图形
即可看作
S 扇形 abc1-S△abc1+S 扇形 abc2-S△abc2<=>
S 扇形 abc1+S 扇形 abc2-S□ac1bc2;
根据中学学的扇形的面积公式可以推到如下

ang1 = acos(\dfrac{r1 * r1 + d * d - r2 * r2}{2.0*r1*d})
ang2 = acos(\dfrac{r2 * r2 + d * d - r1 * r1}{2.0*r2*d})
S扇形_{abc1}=ang1 * r1 * r1
S扇形_{abc2}=ang2 * r2 * r2
S□ac1bc2=d * r1 * sin(ang1)

S = ang1 * r1 * r1+ang2 * r2 * r2 - d * r1 * sin(ang1)；

======
上述已经介绍了如何计算两圆相交面积，该上代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

double solve(Round a, Round b)
{
    double d = dis(a, b);
    if (d >= a.r + b.r)
        return 0;
    if (d <= fabs(a.r - b.r))
    {
        double r = a.r < b.r ? a.r : b.r;
        return PI * r * r;
    }
    double ang1 = acos((a.r * a.r + d * d - b.r * b.r) / 2. / a.r / d);
    double ang2 = acos((b.r * b.r + d * d - a.r * a.r) / 2. / b.r / d);
    double ret = ang1 * a.r * a.r + ang2 * b.r * b.r - d * a.r * sin(ang1);
    return ret;
}

本页文档最后更新于：2021年5月16日

CSDN

数学

计算几何

几何

知识点