仅适用于2D面的几何判断，在游戏程序的渲染，鼠标拣选，UI，逻辑判断以及2D物理方面有些用处。

//——————– // 矢量定义 //——————–

// 点 P0( x0, y0 ) 点 P1( x1, y1 ) // 线段：由两个点组成一个线段。 // 当P0，P1两点不重复，组成有且仅有一个线段。 // 有向线段：当两个点有顺序之分时候，则称为有向线段。 // 当P0，P1两点不重复，将组成两个有向线段。表示为P0P1和P1P0 // 矢量：当有向起点在原点，我们则称之为矢量。 // 当P0，P1两点不重复，且P0在原点，将组成一个矢量。表示为P1。 // 注意：当有向线段P0P1的终结点P1在原点时，该有向线段不可称为矢量。必须“起点”为原点的有向线段才可称为矢量。

//——————– // 矢量基本计算 //——————–

// 矢量P0( x0, y0 ) 矢量P1( x1, y1 ) // 矢量间的加法： // 其结果意义是以 P0 矢量的终结点做为原点，做出 P1 该矢量，找到新 P1 矢量的终结点 P2，再以原点为起点，P2 为终结点做出新的矢量。所以P0 + P1 = P1 + P0 // P0 + P1 = ( x0 + x1, y0 + y1 ); // 矢量间的减法： // 其结果意义是以 P0 矢量的终点点做为原点，以 P1 矢量的终结点作为终结点做出一个新的矢量，将其平移为起点在原点所得的新的矢量。即矢量 P0P1 的平移。矢量有方向，所以 P0 - P1 = - ( P1 - P0 ) // P0 - P1 = ( x0 - x1, y0 - y1 ); // 矢量叉乘： // 其结果意义1是 以 原点，P0 矢量尾结点，P1 矢量尾结点，以及 P0 + P1 组成的新矢量尾结点 这四个点组成的平行四边形的面积。注意：该面积是有符号的，而且这个面积是一个标量，不存在方向。 // 其结果意义2是 当得到的面积值 > 0，则代表P0在P1的顺时针方向， 若 = 0，则代表P0，P1，原点，三点共线(可能在原点同向，可能反向)， 若 < 0，则代表P0在P1的逆时针方向。 // P0 x P1 = x0*y1 - x1*y0;

//——————– // 基本的一些常规问题 //——————–

// Q1： 判断折线段的拐向 // 现假设两个线段P0P1和P1P2有公共端点P1，我们通过计算( P2 - P0 ) x ( P1 - P0 ) 就可以确定折线段的拐向 // if (( P2 - P0 ) x ( P1 - P0 ) > 0) 则P0P1在P1点拐向右侧后得到P1P2 // if (( P2 - P0 ) x ( P1 - P0 ) < 0) 则P0P1在P1点拐向左侧后得到P1P2 // if (( P2 - P0 ) x ( P1 - P0 ) == 0) 则P0P1P2三点共线。

// Q2： 判断一个点是否在线段上 // 设现在有点 P0( x0, y0 ) 线段 P1P2 // 我们判断两个条件就可知道该点是否在线段上： // 1：( P0 - P1 ) x ( P2 - P1 ) = 0 可确定P0在直线P1P2上。 // 2：P0在以P1P2为对角顶点的矩形内。可确定P0在线段P1P2上，而不是在P1P2的延长线或反向延长线上。 // 注意的是：要考虑垂直线段和水平线段两种特殊情况。

// Q3： 判断两线段是否相交 // 假设现在有两个线段 P1P2 和 Q1Q2 // 我们判断两个条件来确定两个线段是否相交 // 1：P1P2 为对角顶点的矩形 和 Q1Q2 为对角顶点的矩形 是否相交，若这俩矩形未相交，则此两个线段必然不相交。 // 2：若这俩矩形相交，还可能线段不相交，此时我们再判断这俩线段是否有交点。 // 若两线段相交，则两矢量( p1 - q1 )和( p2 - q1 )必然在矢量( q2 - q1 )的两侧，即( p1 - q1 ) x ( q2 - q1 ) * ( p2 - q1 ) * ( q2 - q1 ) < 0,当( p1 - q1 ) x ( q2 - q1 ) = 0 时，说明矢量( p1 - q1 )和( p2 - q1 )共线，因为P1P2，Q1Q2所在矩形已确定相交，则说明P1必在Q1Q2上。所以，判断P1P2和Q1Q2必相交的依据是( p1 - q1 ) x ( q2 - q1 ) * ( p2 - q1 ) * ( q2 - q1 ) >= 0

// Q4： 判断线段和直线是否相交 // 基本同上，若线段P1P2和直线Q1Q2相交，那么( p1 - q1 ) x ( q2 - q1 ) * ( p2 - q1 ) * ( q2 - q1 ) >= 0即可。

// Q5： 判断矩形中是否包含点 // 只需要判断该点横纵坐标是否在矩形的左右边和上下边之间。

// Q6： 判断线段，折线，多边形是否在矩形中 // 遍历所有端点是否在矩形中。

// Q7： 判断矩形是否在矩形中 // 判断左右边界和上下边界。

// Q8： 判断圆是否在矩形中 // 1：判断圆心是否在矩形中 // 2：判断圆的半径是否小于等于圆心到四个边的距离。

// Q9： 判断点是否在多边形中 // 首先，我们假设，从点P沿X轴做水平射线，当射线与多边形有奇数相交点时，则P在多边形内，为偶数相交点时P在多边形外。 // 但是，这样做有几种特殊情况会出现错误： // 参见图：

// 为了能够统一处理，对于问题1，2，我们定一个规则，当射线与多边形一个顶点相交时，我们判断该顶点是否是邻接顶点中纵坐标较大的点，若是，则计数，否则忽略。 // 对于问题4，我们若得知P点在多边形一个边上，则直接确定该点属于多边行。对于问题3，我们对多边形的与Y轴水平边不做考虑。 // 则此算法伪代码如下： // // count = 0; // 以P为顶点，沿Y轴平行向左做射线L // for 多边形每条边s // { // if ( p 在 s 上 ) // return true; // if ( s 不是水平于 y 轴 ) // { // if ( s 一个端点在 L 上 ) // { // if ( 该端点比邻接两端点纵坐标大或等于最大值 ) // { // count++; // } // } // else // if ( s 和 L 相交 ) // { // count++; // } // } // else // { // countinue; // } // } // // if ( count % 2 == 0 ) // return false; // else // return true; // // 上述代码说明： // 过P做射线L的方法是，设P2点，P2点纵坐标与P点相同，横坐标为一个极大的正数，则通过P和P2就确定了一个射线。 // 该算法时间复杂度为O(n)。

Q10: 判断线段是否在多边形内

首先我们很容易想到当线段两个端点都在多边形内这个条件，但考虑到凹多边形，所以我们需要加一个必要条

件，线段必须和多边形多有边不相交。那么我们得到两个条件来进行判断线段是否在多边形内。 1：线段两个端点都在多边形内或边上。 2：线段与多边形任何边不相交。 但是这样依旧会有问题。见下图：

上图的a和b必须想出一个方法来进行区分。 我们可以先求出线段与多边形相交的所有顶点，将这些顶点丢到一个容器中，然后按照 x,y 大小排序( x小的

排前面，x值相同的y值小的排前面，这样可以连平行垂直问题一起解决。)那么，我们可以确保这个容器中每

两个相邻的点必是线段与多边形相邻的顶点，若任意两个相邻点的中点都在多边形内，那么该线段则必定在多

边形内。 这套理论是经过证明可靠的，因为我不是几何教师，所以不再赘述。 总结：该算法伪代码如下：

if ( 线段PQ的两端点有任意一点不在多边形内 ) { retrun false; } std::set< Piont > tagAbutSet; for( 多边形每条边s ) { if ( 线段PQ某端点在s上 ) { tagAbutSet.insert( 该端点 ); } else if ( 多边形边s某端点在线段PQ上 ) { tagAbutSet.insert( 该端点 ); } else if ( 多边形边s和线段PQ相交 ) { return false; }

排序tagAbutSet;

for ( tagAbutSet每两个邻接点 ) { if ( 这两点中点不在多边形内 ) { return false; } } } return true;

这个算法看似很复杂，但实际上由于排序过程中，线段和多边形的交点必小于多边形的顶点数量，为常数复杂

，基本时间消耗可忽略。整个算法时间复杂度以及是O(n)而已。

Q11：判断一折线是否在多边形内。 只需判断该折线每条线段是否在多边形内即可，设折线有m条线段，多边形有n顶点，时间复杂度为O(m*n)

Q12：判断多边形是否在多边形内 同上，判断一个多边形每个边则可。复杂度同上。

Q13：判断圆是否在多边形内 计算圆心到多边形每条边的最短距离，若距离均大于等于圆半径，则圆在多边形内。

Q14：判断点是否在圆内 计算圆心到该点距离和半径判断即可。

Q15：判断线段，折线，矩形，多边形是否在圆内 遍历判断它们的每个点是否在圆内即可。

Q16：判断圆O1是否在圆O2内 1：先判断两圆半径，若O1半径大于O2半径，则必然失败。 2：上面判断通过后，判断两个圆心间距离 与 两圆半径差 就可以得知。

Q17：求一个点到线段的最近点

若该线段平行于X轴或Y轴，则做垂线求得垂足，若垂足在线段上，则返回垂足，否则，找到离垂最近的端点即

可。 若线段不平行于任何轴，则斜率一定存在且不为0。 现设线段P1P2，点Q其斜率为 k = ( p2.y - p1.y ) / ( p2.x - p1.x ); 该直线方程为 y = k * ( x - p1.x

) + p1.y，其垂线斜率为 - 1 / k, 其垂线方程为 y = ( - 1 / k ) * ( x - q.x ) + q.y 连解两个方程则可获得垂足点坐标 x 和 y 。之后判断(x, y)垂足点是否在线段上，若在，则返回垂足，不在

则计算线段两断点和垂足点之间的距离，返回较近点。

Q18：求点到折线，矩形，多边形的最近点 同上，计算每个组成线段到该点的最近点和距离，求小即可。

Q19：求点到圆的最近距离和该点坐标 1：当点在圆心，则无解。 2：连接点Q和圆心O，若OQ平行X轴或Y轴，则很好求，不说了。 3：连接点Q和圆心O，若OQ不平行任何轴，则线段OQ存在斜率且不为0，斜率k = ( q.y - o.y ) / ( q.x -

o.x )，直线方程为 y = k * ( x - q.x ) + q.y ;加上圆方程 ( x - o.x ) * ( x - o.x ) + ( y - o.y ) * ( y - o.y ) = r * r,可求得交点两个，取离Q点较近的即可。

Q20：计算线段和直线或线段的交点 1：判断P1P2和Q1Q2是否相交，这个在前面已经说明过。若相交则一定有交点，若不相交则一定没有交点。 2：若P1P2的两端点X坐标相同，平行Y轴 2.1若Q1Q2也平行Y轴，则这俩线段在同一直线上，或完全平行。 2.2若Q1Q2不平行Y轴，则交点为横坐标为P1.x，代入Q1Q2方程可求得交点。 3：若Q1Q2平行Y轴，同上 4：若P1P2的两端点Y坐标相同，平行X轴，基本同上 5：若Q1Q2平行X轴，同上 6：剩下的一种情况是P1P2，Q1Q2均不平行X轴和Y轴，即它们的斜率都存在且不为0 6.1 求出P1P2斜率K1，Q1Q2斜率K2 6.2 若K1 = K2 6.2.1 若Q1在P1P2上，则共线。 6.2.2 否则平行。 6.3 联立两方程组求出解，即为交点。

Q21：计算线段和折线，矩形，多边形的交点 判断每个组成边和线段的交点即可，同上。

Q22：计算线段和圆的交点。 1：若线段两端点均在圆内，则无交点。 2：若线段平行于Y轴 2.1 计算圆心到线段间的距离，若距离大于圆半径，则无交点。 2.2 根据勾股定理，求出交点(1或2个) 2.3 判断交点是否在线段上 3：若线段平行于X轴，同上 4：求出线段斜率和圆方程连解求出交点，判断交点是否在线段上。