在图1中，P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) 0当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。
所以判断P1P2跨立Q1Q2的依据是： ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0 同理判断Q1Q2跨立P1P2的依据是： ( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0至此已经完全解决判断线段是否相交的问题。
5.判断线段和直线是否相交如果线段 P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即： ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 06.判断矩形是否包含点只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。
6.判断矩形是否在矩形中只要比较左右边界和上下边界就可以了。
7.判断圆是否在矩形中圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。
8.判断点是否在多边形中以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……
所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。
如果L和多边形的顶点相交，有些情况下交点只能计算一个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，这条边应该被忽略不计。
为了统一起见，我们在计算射线L和多边形的交点的时候，1。
对于多边形的水平边不作考虑；2。
对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。
对于P在多边形边上的情形，直接可判断P属于多边行。
由此得出算法的伪代码如下：1. count ← 0;2. 以P为端点，作从右向左的射线L;3, for 多边形的每条边s4. do if P在边s上5. then return true;6. if s不是水平的7. then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点9. then count ← count+110. else if s和L相交11. then count ← count+1;12. if count mod 2 = 113. then return true14. else return false;其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。
这个算法的复杂度为O(n)。
9.判断线段是否在多边形内线段在多边形内的一个必要条件是线段的两个端点都在多边形内；如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边形外。
于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交；线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。
因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。
证明如下：命题1：如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则P1, P2之间的所有点都在多边形内。
证明：假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1, P'之间，因为多边形是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P'属于多边性内部，P1-Q-P'完全连续，所以P1Q和QP'一定跨越多边形的边界，因此在P1,P'之间至少还有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。
证毕由命题1直接可得出推论：推论2：设多边形和线段PQ的交点依次为P1,P2,……
Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,……
, n-1，Pi ,Pi+1的中点也在多边形内。
在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。
至此我们得出算法如下：1. if 线端PQ的端点不都在多边形内2. then return false;3. 点集pointSet初始化为空;4. for 多边形的每条边s5. do if 线段的某个端点在s上6. then 将该端点加入pointSet;7. else if s的某个端点在线段PQ上8. then 将该端点加入pointSet;9. else if s和线段PQ相交 // 这时候可以肯定是内交10. then return false;11. 将pointSet中的点按照X-Y坐标排序，X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面；12. for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]13. do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中14. then return false;15. return true;这个算法的复杂度也是O(n)。
其中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。
10.判断折线在多边形内只要判断折线的每条线段是否都在多边形内即可。
设折线有m条线段，多边形有n个顶点，则复杂度为O(m*n)。
11.判断多边形是否在多边形内只要判断多边形的每条边是否都在多边形内即可。
判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。
12.判断矩形是否在多边形内将矩形转化为多边形，然后再判断是否在多边形内。
13.判断圆是否在多边形内只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形内。
计算圆心到多边形每条边最短距离的算法在后文阐述。
14.判断点是否在圆内计算圆心到该点的距离，如果小于等于半径则该点在圆内。
15.判断线段、折线、矩形、多边形是否在圆内因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。
16.判断圆是否在圆内设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。
先比较r1，r2的大小，如果r1 r 则L和圆没有交点；c) 利用勾股定理，可以求出两交点坐标，如图6(a)所示；但要注意考虑L和圆的相切情况3. 如果L平行于X轴，做法与L平行于Y轴的情况类似；4. 如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点；5. 如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。
本文转自：算法与数学之美C2如何加入学会注册学会会员：个人会员：关注学会微信：关注学会微信：中国指挥与控制学会（c2_china），回复“个人会员”获取入会申请表，按要求填写申请表即可，如有问题，可在公众号内进行留言。
通过学会审核后方可在线进行支付宝缴纳会费。
单位会员：关注学会微信：中国指挥与控制学会（c2_china），回复“单位会员”获取入会申请表，按要求填写申请表即可，如有问题，可在公众号内进行留言。
通过学会审核后方可缴纳会费。
长按下方学会二维码，关注学会微信
来源：c2_china 中国指挥与控制学会
原文链接：http://mp.weixin.qq.com/s?__biz=MzA4ODcwOTExMQ==&mid=2655628846&idx=6&sn=1914e155948cacf6c84d786ad2349b50
版权声明：除非特别注明，本站所载内容来源于互联网、微信公众号等公开渠道，不代表本站观点，仅供参考、交流、公益传播之目的。转载的稿件版权归原作者或机构所有，如有侵权，请联系删除。
电话：（010）86409582
邮箱：kejie@scimall.org.cn