随笔 - 6  文章 - 3  trackbacks - 0
<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

  1#include<stdio.h>
  2#include<math.h>
  3
  4const double eps=1e-6;
  5
  6//点(x,y) 
  7typedef struct
  8{
  9    double x,y;
 10}
 Point;
 11
 12//直线方程ax+by+c=0 
 13typedef struct
 14{
 15    double a,b,c;
 16}
 Line;
 17
 18//圆的标准方程(x-center.x)^2+(y-center.y)^2=r^2
 19typedef struct
 20{
 21    Point center;
 22    double r;
 23}
 Circle; 
 24
 25//浮点数符号函数 
 26int DblCmp(double d)
 27{
 28    if(fabs(d)<eps) return 0;
 29    else return d>0?1:-1;
 30}

 31
 32//线段AB的中点C
 33Point MidPoint(Point A,Point B)
 34{
 35    Point C;
 36    C.x=(A.x+B.x)/2;
 37    C.y=(A.y+B.y)/2;
 38    return C;
 39}
 
 40
 41//点A到点B的距离 
 42double Dist(Point A,Point B)
 43{
 44    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
 45}

 46
 47//∠ACB的弧度值 
 48double Angle(Point A,Point B,Point C)
 49{
 50    double a,b,c;
 51    a=Dist(B,C);
 52    b=Dist(A,C);
 53    c=Dist(A,B);
 54    return acos((a*a+b*b-c*c)/(2*a*b));
 55}

 56
 57//二维向量a=(x1,y1)与b=(x2,y2)的叉积的数值 
 58double Det(double x1,double y1,double x2,double y2)
 59{
 60    return x1*y2-x2*y1;
 61}

 62
 63//二维向量的叉积AB*AC的数值 
 64double Cross(Point A,Point B,Point C)
 65{
 66    return Det(B.x-A.x,B.y-A.y,C.x-A.x,C.y-A.y);
 67}

 68
 69//二维向量a=(x1,y1)与b=(x2,y2)的点积
 70double DotDet(double x1,double y1,double x2,double y2)
 71{
 72    return x1*x2+y1*y2;
 73}

 74
 75//二维向量的点积AB·AC 
 76double Dot(Point A,Point B,Point C)
 77{
 78    return DotDet(B.x-A.x,B.y-A.y,C.x-A.x,C.y-A.y);
 79}

 80
 81//点A与B或C重合时为0,点A在BC内部时为-1,点A在BC外部时为1
 82int BetweenCmp(Point A,Point B,Point C)
 83{
 84    return DblCmp(Dot(A,B,C));
 85}
 
 86
 87//线段AB,CD规范相交则返回1,并求交点P;不规范相交则返回2;没有交点则返回0
 88int SegsCross(Point A,Point B,Point C,Point D,Point &P)
 89{
 90   double s1,s2,s3,s4;
 91   int d1,d2,d3,d4;
 92   d1=DblCmp(s1=Cross(A,B,C));
 93   d2=DblCmp(s2=Cross(A,B,D));
 94   d3=DblCmp(s3=Cross(C,D,A));
 95   d4=DblCmp(s4=Cross(C,D,B));
 96   if(((d1^d2)==-2)&&((d3^d4)==-2))
 97   {
 98      P.x=(C.x*s2-D.x*s1)/(s2-s1);
 99      P.y=(C.y*s2-D.y*s1)/(s2-s1);
100      return 1;
101   }

102   if(((d1==0)&&(BetweenCmp(C,A,B)<=0))||
103        ((d2==0)&&(BetweenCmp(D,A,B)<=0))|| 
104        ((d3==0)&&(BetweenCmp(A,C,D)<=0))||
105        ((d4==0)&&(BetweenCmp(B,C,D)<=0)))
106        return 2;
107    else return 0;
108}

109
110//直线L1,L2相交则返回1,并求交点P;重合则返回2,平行则返回0;
111int LinesCross(Line L1,Line L2,Point &P)
112{
113    double d1=Det(L1.a,L1.b,L2.a,L2.b),d2=Det(L1.b,L1.c,L2.b,L2.c),d3=Det(L1.a,L1.c,L2.a,L2.c);
114    int x=DblCmp(d1),y=DblCmp(d2);
115    if(x==0&&y==0return 2;
116    else if(x==0&&y!=0return 0;
117    else
118    {
119        P.x=d2/d1;
120        P.y=-d3/d1;
121        return 1;
122    }

123}

124
125//两点式:AB构造直线L 
126Line LineFromSegs(Point A,Point B)
127{
128    Line L;
129    L.a=B.y-A.y;
130    L.b=A.x-B.x;
131    L.c=B.x*A.y-A.x*B.y;
132    return L; 
133}

134
135//点斜式:A及方位向量dir构造直线L 
136Line LineFromPointAndSlope(Point A,Point dir)
137{
138    Line L;
139    if(dir.x==0)
140    {
141        L.a=1;
142        L.b=0;
143        L.c=-A.x;
144    }

145    else 
146    {
147        double k=dir.y/dir.x;
148        L.a=k;
149        L.b=-1;
150        L.c=A.y-k*A.x;  
151    }
    
152    return L; 
153}

154
155//两点A,B构造垂直平分线L
156Line PerbisecFromSegs(Point A,Point B)
157{
158    Line AB=LineFromSegs(A,B),L;
159    Point C=MidPoint(A,B),dir;
160    dir.x=B.y-A.y;dir.y=A.x-B.x;
161    L=LineFromPointAndSlope(C,dir);
162    return L;
163}

164
165//三点A,B,C构造圆O
166Circle CirFromPoints(Point A,Point B,Point C)
167{
168    Circle O;
169    double c=Dist(A,B),ACB=Angle(A,B,C);
170    O.r=c/(2*sin(ACB));
171    Line DO=PerbisecFromSegs(A,B),EO=PerbisecFromSegs(B,C);
172    Point P;
173    if(LinesCross(DO,EO,P)==1) O.center=P;
174    return O; 
175}
posted on 2009-04-14 10:58 姚冰 阅读(428) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理