如何快速的計算線段和多邊形（內部）是否相交？
判線段相交要采用快速排斥來加速
用遞歸的想法做， 就轉化成判線段與梯形是否相交
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 閱讀(373)
評論(0) 編輯 收藏 引用 所屬分類:
geometry