高分求救算法：求一条直线与一个矩形相交点的坐标？

Question

已知一个矩形四个点的坐标，已知一条直线的坐标，求与矩形相交点的坐标？
俺的数学知识很差，最好给出源代码好吗？

Answer 1

如果这周你还没有找到答案的话，我帮你搞定：[email protected]

Answer 2

#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
bool sc(double xa1, double ya1, double xa2, double ya2,double xb1, double yb1, double xb2, double yb2, double &xc, double &yc)
{//这个函数输入两线断端点，返回交点坐标 xc,yc
if(xa1==xa2)
{
if(xb1==xb2)return false;
xc=xa1;
yc=(xc*yb1+xb2*yb1-xc*yb2-xb1*yb2)/(xb1-xb2);
return true;
}
if(xb1==xb2)
{
if(xa1==xa2) return false;
xc=xb1;
yc=(xc*ya1+xa2*ya1-xc*ya2-xa1*ya2)/(xa1-xa2);
return true;
}    xc=(xb2*(ya1-ya2)+xb1*(ya2-ya1)+(xa1-xa2)*(yb1-yb2));
if (xc == 0)return false; 
    xc=(xa2*(xb2*(yb1-ya1)+xb1*(ya1-yb2))+xa1*(xb2*(ya2-yb1)+xb1*(yb2-ya2)))/xc;
    yc=(xb2*(ya1-ya2)+xb1*(ya2-ya1)+(xa1-xa2)*(yb1-yb2));
if (yc == 0)return false; 
    yc=(xb2*(ya2-ya1)*yb1-xa1*ya2*yb1+xa2*ya1*(yb1-yb2)+xb1*ya1*yb2+xa1*ya2*yb2-xb1*ya2*yb2)/yc;
return true;
}void a()
{
double rx1,rx2,rx3,rx4;//矩形坐标
double ry1,ry2,ry3,ry4;//矩形坐标
double lx1,lx2;//直线坐标
double ly1,ly2; double jx,jy; if(sc(rx1,ry1,rx2,ry2,lx1,ly1,lx2,ly2,jx,jy))//找第一条线断和直线的交点
{
if(jx>= min(rx1,rx2) && jx<=max(rx2,rx1) && jy>=min(ry1,ry2) && jy<=max(ry1,ry2)) //看看交点在不在线段内
{
// 保存交点
}
} if(sc(rx2,ry2,rx3,ry3,lx1,ly1,lx2,ly2,jx,jy))//找第2条线断和直线的交点
{
if(jx>= min(rx1,rx2) && jx<=max(rx2,rx1) && jy>=min(ry1,ry2) && jy<=max(ry1,ry2)) //看看交点在不在线段内
{
// 保存交点
}
}
if(sc(rx3,ry3,rx4,ry4,lx1,ly1,lx2,ly2,jx,jy))//找第3条线断和直线的交点
{
if(jx>= min(rx1,rx2) && jx<=max(rx2,rx1) && jy>=min(ry1,ry2) && jy<=max(ry1,ry2)) //看看交点在不在线段内
{
// 保存交点
}
}
if(sc(rx3,ry3,rx1,ry1,lx1,ly1,lx2,ly2,jx,jy))//找第4条线断和直线的交点
{
if(jx>= min(rx1,rx2) && jx<=max(rx2,rx1) && jy>=min(ry1,ry2) && jy<=max(ry1,ry2)) //看看交点在不在线段内
{
// 保存交点
}
}
// .......
}
int main(int argc, char* argv[])
{
printf("Hello World!\n");
return 0;
}

Answer 3

一个pascal得代码
function ClipLine2D(Clip: TRect; var Pt1, Pt2: TPoint): TClipResult;
var
  DX, DY, tE, tL: double;
begin
  Result := [ccNotVisible];
  DX := Pt2.X - Pt1.X;
  DY := Pt2.Y - Pt1.Y;
  if (DX = 0) and (DY = 0) and IsPointInBox(Pt1, Clip) then
   begin
     Result := 没有交点;   //没有交点
     Exit;
   end;
  tE := 0.0;
  tL := 1.0;
  { 0.9 in 1. }
  if _ClipPt(DX, Clip.Left - Pt1.X, tE, tL) then
   if _ClipPt(-DX, Pt1.X - Clip.Right, tE, tL) then
    if _ClipPt(DY, Clip.Bottom - Pt1.Y, tE, tL) then
     if _ClipPt(-DY, Pt1.Y - Clip.Top, tE, tL) then
      begin
        Result := [];
        if tL < 1 then
         begin
           Pt2.X := Pt1.X + tL * DX;
           Pt2.Y := Pt1.Y + tL * DY;
           Result := [ccSecond];
         end;
        if tE > 0 then
         begin
           Pt1.X := Pt1.X + tE * DX;
           Pt1.Y := Pt1.Y + tE * DY;
           Result := Result + [ccFirst];
         end;
        if Result = [] then
         Result := [ccVisible];
      end;
end;
function _ClipPt(const Denom, Num: double; var tE, tL: double): Boolean;
var
  T: double;
begin
  Result := False;
  if Denom > 0 then
   begin
     T := Num / Denom;
     if T > tL then
      Exit
     else if T > tE then
      tE := T;
   end
  else if Denom < 0 then
   begin
     T := Num / Denom;
     if T < tE then
      Exit
     else if T < tL then
      tL := T;
   end
  else if Num > 0 then
   Exit;
  Result := True;
end;