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

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中情况都是不相交的

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

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.0r2d})S扇形_{abc1}=ang1 * r1 * r1S扇形_{abc2}=ang2 * r2 * r2S□ac1bc2=d * r1 * sin(ang1)$

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

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

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;
}