cameo/above.fig |
| 1 | #FIG 3.2 Produced by xfig version 3.2.5b |
| 2 | Landscape |
| 3 | Center |
| 4 | Metric |
| 5 | A4 |
| 6 | 100.00 |
| 7 | Single |
| 8 | -2 |
| 9 | 1200 2 |
| 10 | 5 1 1 2 14 7 68 -1 -1 6.000 0 0 0 0 5398.867 4722.104 8550 5535 8467 5807 7512 7197 |
| 11 | 6 7605 5715 7965 5985 |
| 12 | 2 1 0 1 4 7 50 -1 0 4.000 0 0 -1 1 0 2 |
| 13 | 1 1 1.00 30.00 30.00 |
| 14 | 7650 5760 7920 5760 |
| 15 | 4 1 4 50 -1 18 15 0.0000 4 135 300 7785 5985 na\001 |
| 16 | -6 |
| 17 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 5625 6750 45 45 5625 6750 5670 6750 |
| 18 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 8100 6525 45 45 8100 6525 8145 6525 |
| 19 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 8550 7425 45 45 8550 7425 8595 7425 |
| 20 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 5400 4725 45 45 5400 4725 5445 4725 |
| 21 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 9315 4365 45 45 9315 4365 9360 4365 |
| 22 | 1 3 0 2 0 7 50 -1 0 0.000 1 0.0000 7053 5826 45 45 7053 5826 7098 5826 |
| 23 | 2 1 1 2 0 7 45 -1 0 6.000 0 0 -1 1 0 2 |
| 24 | 0 0 2.00 150.00 180.00 |
| 25 | 8100 6525 5400 4725 |
| 26 | 2 1 0 2 0 7 45 -1 0 0.000 0 0 -1 0 0 2 |
| 27 | 5625 6750 9315 4365 |
| 28 | 2 1 0 2 1 7 55 -1 0 0.000 0 0 -1 1 0 2 |
| 29 | 0 0 2.00 150.00 180.00 |
| 30 | 5635 6763 8100 6525 |
| 31 | 2 1 0 2 1 7 55 -1 0 0.000 0 0 -1 1 0 2 |
| 32 | 0 0 2.00 150.00 180.00 |
| 33 | 8100 6525 8550 7425 |
| 34 | 2 1 0 2 4 7 60 -1 0 0.000 0 0 -1 1 0 2 |
| 35 | 0 0 2.00 150.00 180.00 |
| 36 | 8100 6525 7965 4995 |
| 37 | 2 1 0 2 4 7 60 -1 0 0.000 0 0 -1 1 0 2 |
| 38 | 0 0 2.00 150.00 180.00 |
| 39 | 8100 6525 9450 5850 |
| 40 | 2 1 1 2 1 7 55 -1 0 6.000 0 0 -1 0 0 2 |
| 41 | 8550 7425 8775 8550 |
| 42 | 2 1 1 2 1 7 55 -1 0 6.000 0 0 -1 0 0 2 |
| 43 | 5625 6750 4275 7200 |
| 44 | 2 3 0 0 1 7 70 -1 44 0.000 0 0 -1 0 0 6 |
| 45 | 4500 7155 5625 6750 8100 6525 8550 7425 8730 8325 4500 7155 |
| 46 | 2 1 0 2 14 7 55 -1 0 0.000 0 0 -1 1 0 2 |
| 47 | 0 0 2.00 150.00 180.00 |
| 48 | 2925 4725 5400 4725 |
| 49 | 2 1 0 1 4 7 50 -1 0 4.000 0 0 -1 1 0 2 |
| 50 | 1 1 1.00 30.00 30.00 |
| 51 | 8595 6435 8865 6435 |
| 52 | 2 1 0 1 0 7 50 -1 0 4.000 0 0 -1 1 0 2 |
| 53 | 1 1 1.00 30.00 30.00 |
| 54 | 4185 4950 4500 4950 |
| 55 | 2 1 0 1 0 7 50 -1 0 4.000 0 0 -1 1 0 2 |
| 56 | 1 1 1.00 30.00 30.00 |
| 57 | 4140 5400 4500 5400 |
| 58 | 2 1 0 1 0 7 50 -1 0 4.000 0 0 -1 1 0 2 |
| 59 | 1 1 1.00 30.00 30.00 |
| 60 | 4365 5850 4680 5850 |
| 61 | 2 1 0 2 4 7 60 -1 0 0.000 0 0 -1 1 0 2 |
| 62 | 0 0 2.00 150.00 180.00 |
| 63 | 7974 5013 9324 4338 |
| 64 | 2 1 0 2 4 7 60 -1 0 0.000 0 0 -1 1 0 2 |
| 65 | 0 0 2.00 150.00 180.00 |
| 66 | 9450 5850 9315 4320 |
| 67 | 4 0 0 50 -1 18 15 0.0000 4 180 180 5355 6660 A\001 |
| 68 | 4 0 0 50 -1 18 15 0.0000 4 180 180 8685 7515 C\001 |
| 69 | 4 1 4 50 -1 18 15 0.0000 4 180 300 8730 6660 nb\001 |
| 70 | 4 0 0 50 -1 18 15 0.0000 4 180 180 8145 6345 B\001 |
| 71 | 4 1 14 50 -1 18 15 0.0000 4 180 165 5400 4590 P\001 |
| 72 | 4 1 0 50 -1 18 15 0.0000 4 195 195 6750 5445 Q\001 |
| 73 | 4 0 0 50 -1 18 15 0.0000 4 195 1470 3150 5175 Q = A+u*AM\001 |
| 74 | 4 0 0 50 -1 18 15 0.0000 4 195 1425 3150 5625 P = B+v*BQ\001 |
| 75 | 4 0 0 50 -1 18 15 0.0000 4 195 1650 3150 6075 Q = B+1/v*BP\001 |
| 76 | 4 0 0 50 -1 18 15 0.0000 4 180 1695 2925 4635 Tool direction\001 |
| 77 | 4 0 0 50 -1 18 15 0.0000 4 240 1890 5715 7785 Polygon, inside\001 |
| 78 | 4 0 0 50 -1 18 15 0.0000 4 180 975 3150 7020 v >= 0 ?\001 |
| 79 | 4 0 0 50 -1 18 15 0.0000 4 225 1590 3150 6660 u in [0, 1] &&\001 |
| 80 | 4 0 0 50 -1 18 15 0.0000 4 180 210 9225 4275 M\001 |
| 81 | 4 0 0 50 -1 18 15 0.0000 4 240 2115 7155 4005 Midpoint, outside\001 |
cameo/area.c |
25 | 25 | #include "area.h" |
26 | 26 | |
27 | 27 | |
28 | | #define EPSILON 0.0001 |
| 28 | #define EPSILON 1e-6 |
29 | 29 | |
30 | 30 | |
31 | 31 | static int bbox(const struct path *path, |
... | ... | |
107 | 107 | |
108 | 108 | /* |
109 | 109 | * Solve |
110 | | * ax+na*bx = cx+nb*dx |
111 | | * ay+na*by = cy+nb*dy |
| 110 | * |
| 111 | * ax + na*bx = cx + nb*dx |
| 112 | * ay + na*by = cy + nb*dy |
112 | 113 | * |
113 | 114 | * which is |
114 | 115 | * |
115 | | * na*bx + nb*-dx = cx-ax |
116 | | * na*by + nb*-dy = cy-ay |
| 116 | * na*bx + nb*-dx = cx - ax |
| 117 | * na*by + nb*-dy = cy - ay |
117 | 118 | */ |
118 | 119 | |
119 | 120 | static int intersect(double ax, double ay, double bx, double by, |
... | ... | |
124 | 125 | |
125 | 126 | |
126 | 127 | /* |
| 128 | * See above.fig. The equation we solve is |
| 129 | * |
| 130 | * Q = A+u*(AM) |
| 131 | * Q = B+v*(BP) |
| 132 | * |
| 133 | * equals |
| 134 | * |
| 135 | * ax + u*(mx-ax) = bx + v*(px-bx) |
| 136 | * ay + u*(my-ay) = by + v*(py-by) |
| 137 | * |
| 138 | * equals |
| 139 | * |
| 140 | * u*(mx-ax) + v*(bx-px) = bx - ax |
| 141 | * u*(my-ay) + v*(by-py) = by - ay |
| 142 | * |
| 143 | * For BC, the equation becomes |
| 144 | * |
| 145 | * Q = C+u*(CM) |
| 146 | * Q = B+v*(BP) |
| 147 | */ |
| 148 | |
| 149 | static int above(const struct point *a, const struct point *b, |
| 150 | const struct point *c, double px, double py) |
| 151 | { |
| 152 | double ab, bc; |
| 153 | double mx, my; |
| 154 | double u, v; |
| 155 | |
| 156 | ab = hypot(a->x-b->x, a->y-b->y); |
| 157 | bc = hypot(b->x-c->x, b->y-c->y); |
| 158 | if (fabs(ab) < EPSILON || fabs(bc) < EPSILON) |
| 159 | return 0; |
| 160 | |
| 161 | mx = b->x-(b->y-a->y)/ab-(c->y-b->y)/bc; |
| 162 | my = b->y+(b->x-a->x)/ab+(c->x-b->x)/bc; |
| 163 | |
| 164 | if (cramer2(mx-a->x, b->x-px, my-a->y, b->y-py, b->x-a->x, b->y-a->y, |
| 165 | &u, &v)) |
| 166 | if (u >= 0 && u <= 1 && v >= 0) |
| 167 | return 1; |
| 168 | if (cramer2(mx-c->x, b->x-px, my-c->y, b->y-py, b->x-c->x, b->y-c->y, |
| 169 | &u, &v)) |
| 170 | if (u >= 0 && u <= 1 && v >= 0) |
| 171 | return 1; |
| 172 | return 0; |
| 173 | } |
| 174 | |
| 175 | |
| 176 | /* |
127 | 177 | * Solve |
128 | 178 | * |
129 | 179 | * (ax+n*bx-cx)^2+(ay+n*by-cy)^2 = r^2 for n |
... | ... | |
131 | 181 | * http://en.wikipedia.org/wiki/Quadratic_equation |
132 | 182 | */ |
133 | 183 | |
134 | | static int touch(double ax, double ay, double bx, double by, |
| 184 | static int touch_solve(double ax, double ay, double bx, double by, |
135 | 185 | double cx, double cy, double r, int enter, double *n) |
136 | 186 | { |
137 | 187 | double dx = cx-ax; |
... | ... | |
153 | 203 | } |
154 | 204 | |
155 | 205 | |
| 206 | /* |
| 207 | * The points A, B, and C are (if the path is left-handed): |
| 208 | * |
| 209 | * - A: the beginning of the segment leading into the corner |
| 210 | * - B: the corner point |
| 211 | * - C: the beginning of the segment leading out of the corner |
| 212 | * |
| 213 | * If the path is right-handed, we swap A and C, making it left-handed. |
| 214 | */ |
| 215 | |
| 216 | static int touch(double ax, double ay, double bx, double by, |
| 217 | const struct point *a, const struct point *b, const struct point *c, |
| 218 | double r, int enter, int left, double *n) |
| 219 | { |
| 220 | double px, py; |
| 221 | |
| 222 | if (!touch_solve(ax, ay, bx, by, b->x, b->y, r, enter, n)) |
| 223 | return 0; |
| 224 | px = ax+*n*bx; |
| 225 | py = ay+*n*by; |
| 226 | return above(a, b, c, px, py) == left; |
| 227 | } |
| 228 | |
| 229 | |
| 230 | /* |
| 231 | * Here, the points A, B, C, and D are: |
| 232 | * |
| 233 | * - A: before the beginning of the current segment |
| 234 | * - B: the beginning |
| 235 | * - C: the end |
| 236 | * - D: the next point beyond the end |
| 237 | */ |
| 238 | |
156 | 239 | static int hit_segment(double fx, double fy, double tx, double ty, |
157 | | const struct point *a, const struct point *b, double r, int enter, |
158 | | int left, double *n) |
| 240 | const struct point *a, const struct point *b, const struct point *c, |
| 241 | const struct point *d, double r, int enter, int left, double *n) |
159 | 242 | { |
160 | 243 | double dx, dy, nx, ny, nn; |
161 | 244 | double px, py; |
... | ... | |
164 | 247 | tx -= fx; |
165 | 248 | ty -= fy; |
166 | 249 | |
167 | | dx = b->x-a->x; |
168 | | dy = b->y-a->y; |
| 250 | dx = c->x-b->x; |
| 251 | dy = c->y-b->y; |
169 | 252 | |
170 | 253 | if (left) { |
171 | 254 | nx = dx; |
... | ... | |
181 | 264 | |
182 | 265 | nn = hypot(nx, ny); |
183 | 266 | |
184 | | px = a->x-ny/nn*r; |
185 | | py = a->y+nx/nn*r; |
| 267 | px = b->x-ny/nn*r; |
| 268 | py = b->y+nx/nn*r; |
186 | 269 | |
187 | 270 | if (!intersect(fx, fy, tx, ty, px, py, dx, dy, &na, &nb)) |
188 | 271 | return 0; |
189 | 272 | if (nb <= 0) { |
190 | | if (!touch(fx, fy, tx, ty, a->x, a->y, r, enter, &na)) |
| 273 | if (!touch(fx, fy, tx, ty, a, b, c, r, enter, left, &na)) |
191 | 274 | return 0; |
192 | 275 | } |
193 | 276 | if (nb >= 1) { |
194 | | if (!touch(fx, fy, tx, ty, b->x, b->y, r, enter, &na)) |
| 277 | if (!touch(fx, fy, tx, ty, b, c, d, r, enter, left, &na)) |
195 | 278 | return 0; |
196 | 279 | } |
197 | 280 | if (na <= 0 || na >= 1) |
... | ... | |
204 | 287 | static int hit_path(double fx, double fy, double tx, double ty, |
205 | 288 | const struct path *path, int inside, int enter, double r, double *x) |
206 | 289 | { |
207 | | const struct point *p; |
| 290 | const struct point *p, *last, *next2; |
208 | 291 | int left; |
209 | 292 | double nx, tmp; |
210 | 293 | int found = 0; |
211 | 294 | |
| 295 | /* |
| 296 | * @@@ We don't wrap around the ends properly and create a zero-sized |
| 297 | * imaginary segment between path->first and path->last. |
| 298 | */ |
212 | 299 | left = path_tool_is_left(path); |
213 | 300 | if (inside) |
214 | 301 | left = !left; |
| 302 | last = path->last; |
215 | 303 | for (p = path->first; p != path->last; p = p->next) { |
216 | | if (hit_segment(fx, fy, tx, ty, p, p->next, |
| 304 | next2 = p->next->next ? p->next->next : path->first; |
| 305 | if (hit_segment(fx, fy, tx, ty, last, p, p->next, next2, |
217 | 306 | r, enter, left, &tmp)) { |
218 | 307 | if (!found || nx > tmp) |
219 | 308 | nx = tmp; |
220 | 309 | found = 1; |
221 | 310 | } |
| 311 | last = p; |
222 | 312 | } |
223 | 313 | if (found) |
224 | 314 | *x = fx+nx*(tx-fx); |