求一条直线和一个矩形的交点的算法/提示，百分相酬

Question

已知直线起点在矩形内（x1,y1），终点由用户输入(x2,y2)，
j矩形的四顶点坐标已知
求直线和矩形边的交点。

Answer 1

归根到底，无非是求直线与矩形的四条边的交点而已。
给出以下代码：
//直线方程式ax+by+c=0的参数结构
typedef struct _EQUATIONPARA
{
double a; //x的参数
double b; //y的参数(为1或0)
double c; //常数
}EQUATIONPARA;//获取两条直线的交点
bool CRouteTools::GetIntersectionPoint(EQUATIONPARA para1,EQUATIONPARA para2,long& x,long& y)
{
if(para1.a == para2.a && para1.b == para2.b)
return false;
if(para1.b==0&&para2.a==0)
{
x = -para1.c;
y = -para2.c;
}
else if(para1.a==0&&para2.b==0)
{
x = -para2.c;
y = -para1.c;
}
else
{
x = (para2.b*para1.c-para1.b*para2.c)/(para2.a*para1.b-para1.a*para2.b);
y = (para1.a*para2.c-para2.a*para1.c)/(para2.a*para1.b-para1.a*para2.b); }
return true;
}
//根据两点，得到对应的直线方程
void CRouteTools::GetEquationPara(long x1,long y1,long x2,long y2,EQUATIONPARA& para)
{
if(x1 == x2)
{
para.a = 1;
para.b = 0;
para.c = -x1;
}
else
{
para.b = 1;
para.a = -(double)(y1-y2)/(double)(x1-x2);
para.c = -(y1+para.a*x1);
}
}
以上函数是计算出两条直线的交点，而不是线段。因此，计算出的交点你还需判断一下是否在线段内。在线段内，而不是延长线上的点即为所需的交点了。

Answer 2

求线段或直线与折线、矩形、多边形的交点： 　　分别求与每条边的交点即可。 　　求线段或直线与圆的交点: 　　设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。 　　1. 如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步。 　　2. 如果L平行于Y轴， 　　　a) 计算圆心到L的距离dis；
　　　b) 如果dis > r 则L和圆没有交点；
　　　c) 利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。　　3. 如果L平行于X轴，做法与L平行于Y轴的情况类似； 　　4. 如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点； 　　5. 如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。 　　凸包的概念： 　　点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
 凸包的求法： 　　现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话，Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh)，在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham扫描法，其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。 　　对于一个有三个或以上点的点集Q，Graham扫描法的过程如下： 　　令p0为Q中Y-X坐标排序下最小的点 
　　设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最远的点外全部移除
　　压p0进栈S
　　压p1进栈S
　　压p2进栈S
    for i ← 3 to m
      do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
        对S弹栈
      压pi进栈S
    return S;
　　　此过程执行后，栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是，我们对点按极角逆时针排序时，并不需要真正求出极角，只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。