随笔-21  评论-10  文章-21  trackbacks-0
如何快速的计算线段和多边形(内部)是否相交?
判线段相交要采用快速排斥来加速
用递归的想法做, 就转化成判线段与梯形是否相交
  1 #include<iostream>
  2 #include<vector>
  3 #include<cstdio>
  4 using namespace std;
  5 const double EPS = 1e-8// 给梯形缩框
  6 const double eps = 1e-12// 计算精度
  7 
  8 struct Point {
  9     double x, y;
 10 };
 11 
 12 struct Line {
 13     Point a, b;
 14     bool flag;
 15 };
 16 
 17 inline int dcmp(double x) {
 18     return x < -eps ? -1 : x > eps;
 19 }
 20 
 21 inline bool LEQ(double x, double y) // less equal, x <= y
 22 {
 23     return dcmp(x - y) <= 0;
 24 }
 25 
 26 inline bool GEQ(double x, double y) // greater equal, x >= y
 27 {
 28     return dcmp(x - y) >= 0;
 29 }
 30 
 31 double xmult(Point p1, Point p2, Point p0)//p0是原点
 32 {
 33     return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
 34 }
 35 
 36 vector<Line> stack;
 37 Point poly[4];
 38 int n;
 39 
 40 Point SymPoint(Point p, Line L) // 求二维平面上点p关于直线L的对称点
 41 {
 42     Point result;
 43     double a = L.b.x - L.a.x;
 44     double b = L.b.y - L.a.y;
 45     double t = ((p.x - L.a.x) * a + (p.y - L.a.y) * b) / (a * a + b * b);
 46     result.x = 2 * L.a.x + 2 * a * t - p.x;
 47     result.y = 2 * L.a.y + 2 * b * t - p.y;
 48     return result;
 49 }
 50 
 51 Line SymLine(Line L, Line base) {
 52     L.a = SymPoint(L.a, base);
 53     L.b = SymPoint(L.b, base);
 54     return L;
 55 }
 56 
 57 bool segcross(Line L1, Line L2) // 判断二维的两条线段是否相交
 58 {
 59     return (GEQ(max(L1.a.x, L1.b.x), min(L2.a.x, L2.b.x)) &&
 60             GEQ(max(L2.a.x, L2.b.x), min(L1.a.x, L1.b.x)) &&
 61             GEQ(max(L1.a.y, L1.b.y), min(L2.a.y, L2.b.y)) &&
 62             GEQ(max(L2.a.y, L2.b.y), min(L1.a.y, L1.b.y)) &&
 63             LEQ(xmult(L2.a, L1.b, L1.a) * xmult(L2.b, L1.b, L1.a), 0&&
 64             LEQ(xmult(L1.a, L2.b, L2.a) * xmult(L1.b, L2.b, L2.a), 0));
 65 }
 66 
 67 bool inside_convex(Point q) {
 68     for (int i = 0; i < 4; i++)
 69         if (dcmp(xmult(poly[(i + 1% 4], q, poly[i])) < 0)return false;
 70     return true;
 71 }
 72 
 73 bool in_poly(Line fold) {
 74     Line L;
 75     if (inside_convex(fold.a))return true;
 76     for (int i = 0; i < 4; i++) {
 77         L.a = poly[i];
 78         L.b = poly[(i + 1% 4];
 79         if (segcross(fold, L)) return true;
 80     }
 81     return false;
 82 }
 83 
 84 void construt_poly(Line L1, Line L2) {
 85     poly[0].x = L1.a.x + EPS;
 86     poly[0].y = L1.a.y + EPS;
 87     poly[1].x = L2.a.x - EPS;
 88     poly[1].y = L2.a.y + EPS;
 89     poly[2].x = L2.b.x - EPS;
 90     poly[2].y = L2.b.y - EPS;
 91     poly[3].x = L1.b.x + EPS;
 92     poly[3].y = L1.b.y - EPS;
 93 }
 94 
 95 bool isBad(Line fold) {
 96     int cnt = stack.size();
 97     if (cnt < 2 || fold.flag != stack[cnt - 1].flag)return false;
 98     while (cnt >= 2) {
 99         fold = SymLine(fold, stack[cnt - 1]);
100         construt_poly(stack[cnt - 2], stack[cnt - 1]);
101         if (in_poly(fold))return true;
102         cnt--;
103     }
104     return false;
105 }
106 
107 int main() {
108     //freopen("in","r",stdin);
109     Line left;
110     left.a.x = left.b.x = 0;
111     left.a.y = 0, left.b.y = 1;
112     while (scanf("%d"&n) != EOF && n) {
113         stack.clear();
114         stack.push_back(left);
115         bool good = true;
116         for (int i = 0; i < n; i++) {
117             Line tem;
118             tem.b.y = 1;
119             tem.a.y = 0;
120             scanf("%lf %lf %d"&tem.b.x, &tem.a.x, &tem.flag);
121             if (good) {
122                 if (isBad(tem)) {
123                     printf("NO %d\n", i + 1);
124                     good = false;
125                     continue;
126                 }
127                 stack.push_back(tem);
128             }
129         }
130         if (good) printf("YES\n");
131     }
132 }


posted on 2009-09-30 16:27 wangzhihao 阅读(320) 评论(0)  编辑 收藏 引用 所属分类: geometry

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