因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序(X坐标小的排在前面，对于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的中点也在多边形内。

　　在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。

　　至此我们得出算法如下：

　　if 线端PQ的端点不都在多边形内
　　then return false;
　　点集pointSet初始化为空;
　　for 多边形的每条边s
　　do if 线段的某个端点在s上
　　then 将该端点加入pointSet;
　　else if s的某个端点在线段PQ上
　　then 将该端点加入pointSet;
　　else if s和线段PQ相交 // 这时候已经可以肯定是内交了
　　then return false;
　　将pointSet中的点按照X-Y坐标排序;
　　for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
　　do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
　　then return false;
　　return true;

　　这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。

判断折线是否在多边形内：

　　只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，则该算法的时间复杂度为O(m*n)。

　判断多边形是否在多边形内：

　　只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。

　　判断矩形是否在多边形内：

将矩形转化为多边形，然后再判断是否在多边形内。

判断圆是否在多边形内：

　　只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。

判断点是否在圆内：

计算圆心到该点的距离，如果小于等于半径则该点在圆内。

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

因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。

判断圆是否在圆内：

　设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。先比较r1，r2的大小，如果r1<r2则O2不可能在O1内；否则如果两圆心的距离大于r1 - r2 ，则O2不在O1内；否则O2在O1内。

计算点到线段的最近点：

　　如果该线段平行于X轴（Y轴），则过点point作该线段所在直线的垂线，垂足很容易求得，然后计算出垂足，如果垂足在线段上则返回垂足，否则返回离垂足近的端点；如果该线段不平行于X轴也不平行于Y轴，则斜率存在且不为0。设线段的两端点为pt1和pt2，斜率为：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为：y = k* ( x - pt1.x) + pt1.y。其垂线的斜率为 - 1 / k，垂线方程为：y = (-1/k) * (x - point.x) + point.y 。

　　联立两直线方程解得：x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ，y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段上，如果在线段上则返回垂足；如果不在则计算两端点到垂足的距离，选择距离垂足较近的端点返回。

计算点到折线、矩形、多边形的最近点：

只要分别计算点到每条线段的最近点，记录最近距离，取其中最近距离最小的点即可。

计算点到圆的最近距离及交点坐标：

　　如果该点在圆心，因为圆心到圆周任一点的距离相等，返回UNDEFINED。

　　连接点P和圆心O，如果PO平行于X轴，则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y轴，则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X轴和Y轴，则PO的斜率存在且不为0，这时直线PO斜率为k = （ P.y - O.y ）/ ( P.x - O.x )。直线PO的方程为：y = k * ( x - P.x) + P.y。设圆方程为:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，联立两方程组可以解出直线PO和圆的交点，取其中离P点较近的交点即可。

计算两条共线的线段的交点：

　　对于两条共线的线段，它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点；图 (b) 和 (d) 中两条线段有无穷焦点；图 (c) 中两条线段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，如果line1包含了line2的两个端点，则是图(d)的情况，两线段有无穷交点；如果line1只包含line2的一个端点，那么如果line1的某个端点等于被line1包含的line2的那个端点，则是图(c)的情况，这时两线段只有一个交点，否则就是图(b)的情况，两线段也是有无穷的交点；如果line1不包含line2的任何端点，则是图(a)的情况，这时两线段没有交点。