【干货】计算几何常用算法

2.矢量叉积

设矢量P = （x1,y1） ，Q = (x2,y2)
则矢量叉积定义为：P × Q = x1*y2 – x2*y1   得到的是一个标量
显然有性质 P × Q = – ( Q × P )   P × ( – Q ) = – ( P × Q )
如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积；
叉乘的重要性质：
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q    > 若 P × Q = 0 , 则P 与Q共线，但可能同向也可能反向

3.判断点在线段上

设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：
( Q – P1 ) × ( P2 – P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内

4.判断两线段是否相交