posts - 12,  comments - 40,  trackbacks - 0
计算几何相关模板(更新中……)
最近在学计算几何,边学,边整理模板,有错的话请大家指出!
 1//计算几何模板 ~ alpc02
 2const double PRECISION = 1e-8;
 3struct Point {
 4    double x, y;
 5}
;
 6int dblcmp(double d) {
 7    return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
 8}
 //三叉口函数,避免精度误差
 9double length(double x, double y) {
10    return sqrt(x*+ y*y);
11}
 //向量长度
12double dotdet(double x1, double y1, double x2, double y2) {
13    return x1*x2 + y1*y2;
14}
 //点积
15double det(double x1, double y1, double x2, double y2) {
16    return x1*y2 - x2*y1;
17}
 //叉积
18int cross(const Point &a, const Point &c, const Point &d) {
19    return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
20}
 //右手螺旋定则,1——a在cd右侧,-1——a在cd左侧,0——三点共线
21bool between(const Point &a, const Point &c, const Point &d) {
22    return dblcmp( dotdet(c.x-a.x, c.y-a.y, d.x-a.x, d.y-a.y) ) != 1;
23}
 //在cross(a,c,d)==0的基础上,可判断点a是否在cd内部
24int segIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
25    int a_cd = cross(a,c,d);
26    if(a_cd == 0 && between(a,c,d))    return 2;
27    int b_cd = cross(b,c,d);
28    if(b_cd == 0 && between(b,c,d))    return 2;
29    int c_ab = cross(c,a,b);
30    if(c_ab == 0 && between(c,a,b))    return 2;
31    int d_ab = cross(d,a,b);
32    if(d_ab == 0 && between(d,a,b))    return 2;
33    if ((a_cd ^ b_cd) == -2 && (c_ab ^ d_ab) == -2)
34        return 1;
35    return 0;
36}
 //两线段相交情况:0——不相交,1——规范相交,2——不规范相交(交于端点或重合)
37void intersectPoint(const Point &a, const Point &b, const Point &c, const Point &d, Point &e) {
38    double sc, sd;
39    sc = fabs( det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) );
40    sd = fabs( det(b.x-a.x, b.y-a.y, d.x-a.x, d.y-a.y) );
41    e.x = (sc * d.x + sd * c.x) / (sc + sd);
42    e.y = (sc * d.y + sd * c.y) / (sc + sd);
43}
 //两线段规范相交时,求交点坐标
44int linesegIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
45    int c_ab = cross(c,a,b);
46    if(c_ab == 0)    return 2;
47    int d_ab = cross(d,a,b);
48    if(d_ab == 0)    return 2;
49    if(c_ab ^ d_ab == -2)
50        return 1;
51    return 0;
52}
 //直线ab和线段cd相交情况:0——不相交,1——规范相交,2——不规范相交(交于端点或重合)
53int lineIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
54    if(dblcmp(det(b.x-a.x, b.y-a.y, d.x-c.x, d.y-c.y)) != 0)
55        return 1;
56    if(cross(a,c,d) == 0)
57        return 2;
58    return 0;
59}
 //两直线相交情况:0——平行,1——规范相交,2——不规范相交(重合)
60



posted on 2007-08-22 18:39 LSM 阅读(1908) 评论(6)  编辑 收藏 引用 所属分类: 计算几何

FeedBack:
# re: 计算几何相关模板(更新中……)[未登录]
2007-08-23 12:45 | Jarod
我还以为是 template.....  回复  更多评论
  
# re: 计算几何相关模板(更新中……)
2007-08-23 14:09 | DeathKnight
计算几何应该有一些不错的库@Jarod
  回复  更多评论
  
# re: 计算几何相关模板(更新中……)[未登录]
2007-08-24 08:53 | LSM

@Jarod
应该叫做acm/icpc中计算几何常用函数
比赛时应该很实用的  回复  更多评论
  
# re: 计算几何相关模板(更新中……)[未登录]
2007-08-24 08:54 | LSM
@LSM
哦?
比如?  回复  更多评论
  
# re: 计算几何相关模板(更新中……)
2009-05-11 21:23 | qq867062837
我觉得直线和线段相交判断的就有问题
比如
P1(0,0) P2(0,2)
P3(1,1) P4(2,1)
P1P2直线与p3p4线段应该是不想交的
而此处的模板却得到了1
  回复  更多评论
  
# re: 计算几何相关模板(更新中……)
2010-03-20 23:49 | 发生的范德萨
模板 打天下。什么世道?  回复  更多评论
  

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


<2007年8月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(4)

随笔分类

随笔档案

牛牛 ACM/ICPC

最新随笔

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜