计算几何算法

判断点是否在直线上

判断两线段是否相交

判断线段和直线是否相交

判断点是否在矩形内

判断线段、折线、多边形是否在矩形内

判断矩形是否在矩形内

判断圆是否在矩形内

判断矩形是否在圆内

判断点是否在多边形内

判断线段是否在多边形内

判断点是否在圆内

判断圆是否在圆内

计算点到线段的最近点

计算点到圆的最近点及点坐标

凸包求法等

算法介绍

矢量概念

如果把一条线段的端点作出次序之分，则可将这种线段看作有向线段。如果有向线段P1P2的起点P1在坐标原点，则把它称为矢量P2。这样，点P(x,y)可以看作起点为原点O(0,0)的二维矢量。相应地，三维空间坐标系下的坐标也可以作类似理解为三维矢量。

设二维矢量P=(x1,y1),Q=(x2,y2)，则矢量的加法定义为P+Q=(x1+x2,y1+y2)，矢量的减法定义为P-Q=(x1-x2,y1-y2)。矢量的加减法有以下性质：P + Q = Q + P ，P-Q = -（Q - P）。因为点可视为坐标原点至该点的矢量，所以点的加减法就是矢量的加减法。

矢量的叉积

矢量的叉积，也称矢量的叉乘。矢量P与Q的叉乘记作P×Q。定义P×Q = x1*y2 - x2*y1，其结果是一个标量。几何意义为由原点、点P、点Q、点P+Q四点共同组成的平行四边形的面积（带正负号）。计算矢量叉积是直线和线段相关算法的核心。矢量的叉积有以下性质：P×Q = -(Q×P)，P×(-Q) = -(P×Q)。

叉乘的一个非常重要的性质是，可以通过它的正负号判断两矢量之间的顺逆时针关系：

若P×Q > 0，则P在Q的顺时针方向；

若P×Q < 0，则P在Q的逆时针方向；

若P×Q = 0，则P和Q共线，可能同向也可能反向。

算法举例

判断折线段的拐向

折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段AP和PB，通过计算∇ = (B - P)×(P - A)的符号，就可以确定折线的拐向：

若∇ > 0，则AP在P点拐向右侧得到PB；

若∇ < 0，则AP在P点拐向左侧得到PB；

若∇ = 0，则A、P、B三点共线。

判断点是否在线段上

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。