计算几何基础

计算几何是一门用计算机解决几何问题的学科,里面有非常多优美的解决问题的方式方法.

本文主要介绍这几个方面的内容:

1. 判断平面内两线段是否相交
2. 求解多边形的面积
3. 求取多边形重心
4. 求解凸包

 

• 计算几何基础: 向量的内积和外积

向量内积  a · b :

定义: 两个向量a与b的内积为  a·b = |a| |b| cos∠(a, b)，它是数量而不是向量。

几何意义: a·b 等于向量 b 在 a 上的投影 与 a 的长度之积

 

 

向量外积  a × b :  

定义: 向量 a 与 b 的外积 a×b 是一个向量, 其长度等于|a×b| = |a| |b| sin∠(a,b)，

其方向正交于 a 与 b ,并且, (a,b,a×b) 构成右手系, 右手定理判定外积向量方向: a×b , a->b

逆时针: 垂直平面向上     顺时针: 垂直平面向下(例图中为逆时针所以垂直平面向上)

几何意义：a 与 b的外积在数值上等于以 a,b 为邻边的平行四边形的面积 

 

• 判断平面内两线段是否相交

问题描述：已知两条线段 P1P2 和 Q1Q2 ，判断 P1P2 和 Q1Q2 是否相交，若相交，求出交点。

先思考一下平面内两线段位置的情况:

　 　　

　　　　　相交(一)　　　　　　　　　　　     相交(二)　　　　　　　　　　　　　　　不相交

 　　可以发现在相交(一)这种情况下: Q1Q2×Q1P1 和 Q1Q2×Q1P2 结果(方向)相反，则 点P1 和 点P2 在直线Q1Q2的两侧，同理，如果 P1P2×P1Q1 和 P1P2×P1Q2 结果(方向)也相反，则 点Q1 和 点Q2 在直线P1P2的两侧，这样，这两个线段也就相交。

　　看相交(二)这种情况，此时在数值上 Q1Q2×Q1P1=0 和 Q1Q2×Q1P2 > 0，可以断定 点P1 已经在直线Q1Q2上了，

只要判定 点P1 的坐标是否在线段Q1Q2区间内即可

(PS：此时XY区间一定都要判定，下图 点P 在线段Q1Q2所在直线上，如果只判定 点P1 的 Y轴区间会被判定为线段相交）

 

参考链接: https://blog.csdn.net/ACdreamers/article/details/7930911