algorithm.txt

几何算法

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

  

12.判断折线在多边形内 


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

  

13.判断多边形是否在多边形内 

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

  

14.判断矩形是否在多边形内 


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


15.判断圆是否在多边形内 


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


16.判断点是否在圆内 

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

  

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

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

  

18.判断圆是否在圆内 

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

  

19.计算点到线段的最近点 

如果该线段平行于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; 

然后再判断垂足是否在线段上，如果在线段上则返回垂足；如果不在则计算两端点
到垂足的距离，选择距离垂足较近的端点返回。 

  

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

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

  

21.计算点到圆的最近距离 

如果该点在圆心，则返回UNDEFINED
连接点P和圆心O，如果PO平行于X轴，则根据P在O的左边还是右边计算出最近点的
横坐标为centerPoint.x - radius 或 centerPoint.x + radius， 如图4 (a)所示；
如果PO平行于Y轴，则根据P在O的上边还是下边计算出最近点的纵坐标为
centerPoint.y + radius 或 centerPoint.y - radius， 如图4 (b)所示。 

如果PO不平行于X轴和Y轴，则PO的斜率存在且不为0，如图4(c)所示。这时直线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点较近的交点即可。 

  

22.计算两条共线的线段的交点 

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


23.计算线段或直线与线段的交点 

设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，要计算的就是L0和L1
的交点。 

1.首先判断L0和L1是否相交（方法已在前文讨论过），如果不相交则没有交点，
否则说明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。 

2.如果P1和P2横坐标相同，即L0平行于Y轴
  a)若L1也平行于Y轴，
      i.若P1的纵坐标和Q1的纵坐标相同，说明L0和L1共线，假如L1是直线的话他们有
        无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们
        的交点（该方法在前文已讨论过）；
      ii.否则说明L0和L1平行，他们没有交点；
  b)若L1不平行于Y轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中可以计
    算出交点纵坐标；
3.如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于Y轴，则交点横
坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标；
4.如果P1和P2纵坐标相同，即L0平行于X轴
  a)若L1也平行于X轴，
      i.若P1的横坐标和Q1的横坐标相同，说明L0和L1共线，假如L1是直线的话他们
        有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求
        他们的交点（该方法在前文已讨论过）；
     ii.否则说明L0和L1平行，他们没有交点； 

   b)若L1不平行于X轴，则交点纵坐标为P1的纵坐标，代入到L1的直线方程中可以计
     算出交点横坐标；
5.如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于X轴，则交点纵坐标
为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标；
6.剩下的情况就是L1和L0的斜率均存在且不为0的情况
   a)计算出L0的斜率K0，L1的斜率K1 ；
   b)如果K1 = K2
      i.如果Q1在L0上，则说明L0和L1共线，假如L1是直线的话有无穷交点，假如L1
        是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在
        前文已讨论过）；
     ii.如果Q1不在L0上，则说明L0和L1平行，他们没有交点。
   c)联立两直线的方程组可以解出交点来 

说明：这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况
需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就
先利用矢量叉乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后
面就可以将线段全部看作直线来考虑。 

  

24.求线段或直线与折线、矩形、多边形的交点 

分别求与每条边的交点即可。 

  

25.求线段或直线与圆的交点 

设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。
1.如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步
2.如果L平行于Y轴，
  a)计算圆心到L的距离dis
  b)如果dis > r 则L和圆没有交点；
  c)利用勾股定理，可以求出两交点坐标，如图6(a)所示；但要注意考虑L和圆的相
    切情况
3.如果L平行于X轴，做法与L平行于Y轴的情况类似；
4.如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程
，和圆方程联立即可求解出L和圆的两个交点；
5.如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。