加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

ACM经典算法之计算几何(求两直线的交点)

(2012-04-07 14:55:58)
标签:

it

分类: DataStructure/Algorithm

语法:result=mindistance(Point p1,Point p2,Point q);

参数:

p1~p4:

直线上不相同的两点

*p:

通过指针返回结果

返回值:

1:两直线相交;2:两直线平行

注意:

 

 

如需要判断两线段交点,检验k和对应k1(注释中)的值是否在0~1之间,用在0~1之间的那个求交点

源程序:

 

 

typedef struct {
   double x,y;
Point;

int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p)
{
   double k;

   //同一直线

  if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0&&

        (p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2;

   //平行,不同一直线

  if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;

 

    k=((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));

//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));

   (*p).x=p1.x+k*(p2.x-p1.x);

   (*p).y=p1.y+k*(p2.y-p1.y);

   return 1;//有交点}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有