1 /* $Id: tenm_collision.c,v 1.83 2003/01/14 01:03:14 oohara Exp $ */
2 #include <stdio.h>
3 /* malloc */
4 #include <stdlib.h>
5 /* for tenm_polygon_new */
6 #include <stdarg.h>
7
8 #include "tenm_collision.h"
9
10 #define NEAR_ZERO 0.0001
11
12 static double tenm_same_side_temp(double p_x, double p_y,
13 double a_x, double a_y,
14 double b_x, double b_y);
15 static double tenm_same_side_vertical_temp(double p_x, double p_y,
16 double a_x, double a_y,
17 double b_x, double b_y,
18 double on_line_x, double on_line_y);
19
20 static int tenm_collided_point_point(const tenm_point *p,
21 const tenm_point *q);
22 static int tenm_collided_point_circle(const tenm_point *p,
23 const tenm_circle *q);
24 static int tenm_collided_point_segment(const tenm_point *p,
25 const tenm_segment *q);
26 static int tenm_collided_point_polygon(const tenm_point *p,
27 const tenm_polygon *q);
28 static int tenm_collided_circle_circle(const tenm_circle *p,
29 const tenm_circle *q);
30 static int tenm_collided_circle_segment(const tenm_circle *p,
31 const tenm_segment *q);
32 static int tenm_collided_circle_segment2(double p_x, double p_y, double p_r,
33 double q_a_x, double q_a_y,
34 double q_b_x, double q_b_y);
35 static int tenm_collided_circle_polygon(const tenm_circle *p,
36 const tenm_polygon *q);
37 static int tenm_collided_segment_segment(const tenm_segment *p,
38 const tenm_segment *q);
39 static int tenm_collided_segment_segment2(double p_a_x, double p_a_y,
40 double p_b_x, double p_b_y,
41 double q_a_x, double q_a_y,
42 double q_b_x, double q_b_y);
43 static int tenm_collided_segment_polygon(const tenm_segment *p,
44 const tenm_polygon *q);
45 static int tenm_collided_polygon_polygon(const tenm_polygon *p,
46 const tenm_polygon *q);
47
48 int
tenm_same_point(double a_x,double a_y,double b_x,double b_y)49 tenm_same_point(double a_x, double a_y, double b_x, double b_y)
50 {
51 /* assume that a point (really a pixel) is a circle whose diameter is 1 */
52 return tenm_point_nearer(a_x, a_y, b_x, b_y, 1.0);
53 }
54
55 /* checks if the distance between point A(a_x, a_y) and point B(b_x, b_y) is
56 * equal to or smaller than n
57 * return 1 (true) or 0 (false)
58 */
59 int
tenm_point_nearer(double a_x,double a_y,double b_x,double b_y,double n)60 tenm_point_nearer(double a_x, double a_y, double b_x, double b_y, double n)
61 {
62 /* distance^2 = temp = temp1 + temp2 */
63 double temp = 0;
64 double temp1 = 0;
65 double temp2 = 0;
66
67 /* distance can't be negative*/
68 if (n < -NEAR_ZERO)
69 {
70 fprintf(stderr, "tenm_point_nearer: n is negative (%f)\n", n);
71 return 0;
72 }
73
74 if ((n > -NEAR_ZERO) && (n < NEAR_ZERO))
75 return tenm_same_point(a_x, a_y, b_x, b_y);
76
77 temp1 = a_x - b_x;
78 temp1 = temp1 * temp1;
79 temp2 = a_y - b_y;
80 temp2 = temp2 * temp2;
81 temp = temp1 + temp2;
82
83 if (n * n >= temp)
84 return 1;
85 return 0;
86 }
87
88 /* checks if the distance between the point P and the line is equal to
89 * or smaller than n
90 * return 1 (true) or 0 (false)
91 */
92 int
tenm_line_nearer(double p_x,double p_y,double a_x,double a_y,double b_x,double b_y,double n)93 tenm_line_nearer(double p_x, double p_y,
94 double a_x, double a_y, double b_x, double b_y, double n)
95 {
96 /* distance^2 = temp/over */
97 double temp = 0;
98 double over = 0;
99 /* over = over1 + over2 */
100 double over1 = 0;
101 double over2 = 0;
102
103 /* distance can't be nagative */
104 if (n < -NEAR_ZERO)
105 {
106 fprintf(stderr, "tenm_line_nearer: n is negative (%f)\n", n);
107 return 0;
108 }
109
110 /* check if line is really a point */
111 if(tenm_same_point(a_x, a_y, b_x, b_y))
112 {
113 return tenm_point_nearer(p_x, p_y, a_x, a_y, n);
114 }
115
116 temp = (a_x - p_x) * (b_y - a_y) - (a_y - p_y) * (b_x - a_x);
117 temp = temp * temp;
118 over1= b_x - a_x;
119 over1 = over1 * over1;
120 over2 = b_y - a_y;
121 over2 = over2 * over2;
122 over = over1 + over2;
123
124 if (over * n * n >= temp)
125 return 1;
126 return 0;
127 }
128
129 /* checks if the two points P(p_x, p_y) and Q(q_x, q_y) are on the same
130 * side of the line which passes A(a_x, a_y) and B(b_x, b_y)
131 * "on the line" counts as either side
132 * return 1 (true) or 0 (false)
133 */
134 int
tenm_same_side(double p_x,double p_y,double q_x,double q_y,double a_x,double a_y,double b_x,double b_y)135 tenm_same_side(double p_x, double p_y, double q_x, double q_y,
136 double a_x, double a_y, double b_x, double b_y)
137 {
138 double temp_p;
139 double temp_q;
140
141 /* check if we really have a line */
142 if (tenm_same_point(a_x, a_y, b_x, b_y))
143 {
144 fprintf(stderr, "tenm_same_side: not a line\n");
145 return 0;
146 }
147
148 temp_p = tenm_same_side_temp(p_x, p_y, a_x, a_y, b_x, b_y);
149 temp_q = tenm_same_side_temp(q_x, q_y, a_x, a_y, b_x, b_y);
150 if ((temp_p >= 0) && (temp_q >= 0))
151 return 1;
152 if ((temp_p <= 0) && (temp_q <= 0))
153 return 1;
154 return 0;
155 }
156
157 /* local-only function used in tenm_same_side */
158 static double
tenm_same_side_temp(double p_x,double p_y,double a_x,double a_y,double b_x,double b_y)159 tenm_same_side_temp(double p_x, double p_y,
160 double a_x, double a_y, double b_x, double b_y)
161 {
162 return (b_y - a_y) * p_x - (b_x - a_x) * p_y
163 -((b_y - a_y) * a_x - (b_x - a_x) * a_y);
164 }
165
166 /* checks if the two points P(p_x, p_y) and Q(q_x, q_y) are on the same
167 * side of the line L
168 * such that:
169 * 1) L passes the point (on_line_x, on_line_y)
170 * 2) L is vertical to the line which passes (a_x, a_y) and (b_x, b_y)
171 * "on the line" counts as either side
172 * return 1 (true) or 0 (false)
173 */
174 int
tenm_same_side_vertical(double p_x,double p_y,double q_x,double q_y,double a_x,double a_y,double b_x,double b_y,double on_line_x,double on_line_y)175 tenm_same_side_vertical(double p_x, double p_y, double q_x, double q_y,
176 double a_x, double a_y, double b_x, double b_y,
177 double on_line_x, double on_line_y)
178 {
179 double temp_p;
180 double temp_q;
181
182 /* check if we really have a line */
183 if (tenm_same_point(a_x, a_y, b_x, b_y))
184 {
185 fprintf(stderr, "tenm_same_side_vertical: not a line\n");
186 return 0;
187 }
188
189 temp_p = tenm_same_side_vertical_temp(p_x, p_y,
190 a_x, a_y, b_x, b_y,
191 on_line_x, on_line_y);
192 temp_q = tenm_same_side_vertical_temp(q_x, q_y,
193 a_x, a_y, b_x, b_y,
194 on_line_x, on_line_y);
195 if ((temp_p >= 0) && (temp_q >= 0))
196 return 1;
197 if ((temp_p <= 0) && (temp_q <= 0))
198 return 1;
199 return 0;
200 }
201
202 /* local-only function used in tenm_same_side_vertical */
203 static double
tenm_same_side_vertical_temp(double p_x,double p_y,double a_x,double a_y,double b_x,double b_y,double on_line_x,double on_line_y)204 tenm_same_side_vertical_temp(double p_x, double p_y,
205 double a_x, double a_y, double b_x, double b_y,
206 double on_line_x, double on_line_y)
207 {
208 return (b_x - a_x) * p_x + (b_y - a_y) * p_y
209 -((b_x - a_x) * on_line_x + (b_y - a_y) * on_line_y);
210 }
211
212 /* optimized under the assumption that p and q are usually not collided */
213 int
tenm_collided_primitive(const tenm_primitive * p,const tenm_primitive * q)214 tenm_collided_primitive(const tenm_primitive *p,
215 const tenm_primitive *q)
216 {
217 const tenm_primitive *p_temp;
218 const tenm_primitive *q_temp;
219
220 if (p == NULL)
221 {
222 fprintf(stderr, "tenm_collided_primitive: p is NULL\n");
223 return 0;
224 }
225 if (q == NULL)
226 {
227 fprintf(stderr, "tenm_collided_primitive: q is NULL\n");
228 return 0;
229 }
230
231 switch (p->klass + q->klass)
232 {
233 case TENM_POINT + TENM_POINT:
234 return tenm_collided_point_point((const tenm_point *) p,
235 (const tenm_point *) q);
236 break;
237 case TENM_POINT + TENM_CIRCLE:
238 if (p->klass == TENM_POINT)
239 {
240 p_temp = p;
241 q_temp = q;
242 }
243 else if (q->klass == TENM_POINT)
244 {
245 p_temp = q;
246 q_temp = p;
247 }
248 else
249 {
250 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
251 "TENM_POINT + TENM_CIRCLE\n");
252 return 0;
253 }
254 return tenm_collided_point_circle((const tenm_point *) p_temp,
255 (const tenm_circle *) q_temp);
256 break;
257 case TENM_POINT + TENM_SEGMENT:
258 if (p->klass == TENM_POINT)
259 {
260 p_temp = p;
261 q_temp = q;
262 }
263 else if (q->klass == TENM_POINT)
264 {
265 p_temp = q;
266 q_temp = p;
267 }
268 else
269 {
270 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
271 "TENM_POINT + TENM_SEGMENT\n");
272 return 0;
273 }
274 return tenm_collided_point_segment((const tenm_point *) p_temp,
275 (const tenm_segment *) q_temp);
276 break;
277 case TENM_POINT + TENM_POLYGON:
278 if (p->klass == TENM_POINT)
279 {
280 p_temp = p;
281 q_temp = q;
282 }
283 else if (q->klass == TENM_POINT)
284 {
285 p_temp = q;
286 q_temp = p;
287 }
288 else
289 {
290 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
291 "TENM_POINT + TENM_POLYGON\n");
292 return 0;
293 }
294 return tenm_collided_point_polygon((const tenm_point *) p_temp,
295 (const tenm_polygon *) q_temp);
296 break;
297 case TENM_CIRCLE + TENM_CIRCLE:
298 return tenm_collided_circle_circle((const tenm_circle *) p,
299 (const tenm_circle *) q);
300 break;
301 case TENM_CIRCLE + TENM_SEGMENT:
302 if (p->klass == TENM_CIRCLE)
303 {
304 p_temp = p;
305 q_temp = q;
306 }
307 else if (q->klass == TENM_CIRCLE)
308 {
309 p_temp = q;
310 q_temp = p;
311 }
312 else
313 {
314 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
315 "TENM_CIRCLE + TENM_SEGMENT\n");
316 return 0;
317 }
318 return tenm_collided_circle_segment((const tenm_circle *) p_temp,
319 (const tenm_segment *) q_temp);
320 break;
321 case TENM_CIRCLE + TENM_POLYGON:
322 if (p->klass == TENM_CIRCLE)
323 {
324 p_temp = p;
325 q_temp = q;
326 }
327 else if (q->klass == TENM_CIRCLE)
328 {
329 p_temp = q;
330 q_temp = p;
331 }
332 else
333 {
334 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
335 "TENM_CIRCLE + TENM_POLYGON\n");
336 return 0;
337 }
338 return tenm_collided_circle_polygon((const tenm_circle *) p_temp,
339 (const tenm_polygon *) q_temp);
340 break;
341 case TENM_SEGMENT + TENM_SEGMENT:
342 return tenm_collided_segment_segment((const tenm_segment *) p,
343 (const tenm_segment *) q);
344 break;
345 case TENM_SEGMENT + TENM_POLYGON:
346 if (p->klass == TENM_SEGMENT)
347 {
348 p_temp = p;
349 q_temp = q;
350 }
351 else if (q->klass == TENM_SEGMENT)
352 {
353 p_temp = q;
354 q_temp = p;
355 }
356 else
357 {
358 fprintf(stderr, "tenm_collided_primitive: strange pointer found in "
359 "TENM_SEGMENT + TENM_POLYGON\n");
360 return 0;
361 }
362 return tenm_collided_segment_polygon((const tenm_segment *) p_temp,
363 (const tenm_polygon *) q_temp);
364 break;
365 case TENM_POLYGON + TENM_POLYGON:
366 return tenm_collided_polygon_polygon((const tenm_polygon *) p,
367 (const tenm_polygon *) q);
368 break;
369 default:
370 fprintf(stderr, "tenm_collided_primitive: strange combination of "
371 "primitives (%d and %d)\n", p->klass, q->klass);
372 return 0;
373 break;
374 }
375
376 return 0;
377 }
378
379 static int
tenm_collided_point_point(const tenm_point * p,const tenm_point * q)380 tenm_collided_point_point(const tenm_point *p,
381 const tenm_point *q)
382 {
383 return tenm_same_point(p->x, p->y, q->x, q->y);
384 }
385
386 static int
tenm_collided_point_circle(const tenm_point * p,const tenm_circle * q)387 tenm_collided_point_circle(const tenm_point *p,
388 const tenm_circle *q)
389 {
390 return tenm_point_nearer(p->x, p->y, q->center->x, q->center->y, q->r);
391 }
392
393 static int
tenm_collided_point_segment(const tenm_point * p,const tenm_segment * q)394 tenm_collided_point_segment(const tenm_point *p,
395 const tenm_segment *q)
396 {
397 /* assume that a point (really a pixel) is a circle whose diameter is 1 */
398 return tenm_collided_circle_segment2(p->x, p->y, 0.5,
399 q->a->x, q->a->y, q->b->x, q->b->y);
400 }
401
402 static int
tenm_collided_point_polygon(const tenm_point * p,const tenm_polygon * q)403 tenm_collided_point_polygon(const tenm_point *p,
404 const tenm_polygon *q)
405 {
406 /* I know that the best algorithm is O(n * log(n)), but it is hard
407 * to implement */
408 int i;
409 int j;
410 int k;
411 int l;
412
413 if (q->n <= 0)
414 {
415 fprintf(stderr, "tenm_collided_point_polygon: strange point number in q "
416 "(%d)\n", q->n);
417 return 0;
418 }
419 if (q->n == 1)
420 return tenm_same_point(p->x, p->y, q->v[0]->x, q->v[0]->y);
421 if (q->n == 2)
422 return tenm_collided_circle_segment2(p->x, p->y, 0.5,
423 q->v[0]->x, q->v[0]->y,
424 q->v[1]->x, q->v[1]->y);
425
426 for (i = 0; i < q->n; i++)
427 for (j = i + 1; j < q->n; j++)
428 {
429 for (k = 0; k < q->n; k++)
430 {
431 if (tenm_same_point(q->v[k]->x, q->v[k]->y, q->v[i]->x, q->v[i]->y))
432 continue;
433 if (tenm_same_point(q->v[k]->x, q->v[k]->y, q->v[j]->x, q->v[j]->y))
434 continue;
435
436 if (q->n >= 4)
437 {
438 for (l = 0;(l < q->n)&&((tenm_same_point(q->v[l]->x, q->v[l]->y,
439 q->v[i]->x, q->v[i]->y))
440 ||(tenm_same_point(q->v[l]->x, q->v[l]->y,
441 q->v[j]->x, q->v[j]->y))
442 ||(tenm_same_point(q->v[l]->x, q->v[l]->y,
443 q->v[k]->x, q->v[k]->y)));
444 l++)
445 ;
446
447 if ((l < q->n) && (! tenm_same_side(q->v[k]->x, q->v[k]->y,
448 q->v[l]->x, q->v[l]->y,
449 q->v[i]->x, q->v[i]->y,
450 q->v[j]->x, q->v[j]->y)))
451 break;
452 }
453
454 if (! tenm_same_side(p->x, p->y, q->v[k]->x, q->v[k]->y,
455 q->v[i]->x, q->v[i]->y, q->v[j]->x, q->v[j]->y))
456 return 0;
457 }
458 }
459 return 1;
460 }
461
462 static int
tenm_collided_circle_circle(const tenm_circle * p,const tenm_circle * q)463 tenm_collided_circle_circle(const tenm_circle *p,
464 const tenm_circle *q)
465 {
466 return tenm_point_nearer(p->center->x, p->center->y,
467 q->center->x, q->center->y, p->r + q->r);
468 }
469
470 static int
tenm_collided_circle_segment(const tenm_circle * p,const tenm_segment * q)471 tenm_collided_circle_segment(const tenm_circle *p,
472 const tenm_segment *q)
473 {
474 return tenm_collided_circle_segment2(p->center->x, p->center->y, p->r,
475 q->a->x, q->a->y, q->b->x, q->b->y);
476 }
477
478 static int
tenm_collided_circle_segment2(double p_x,double p_y,double p_r,double q_a_x,double q_a_y,double q_b_x,double q_b_y)479 tenm_collided_circle_segment2(double p_x, double p_y, double p_r,
480 double q_a_x, double q_a_y,
481 double q_b_x, double q_b_y)
482 {
483 if (tenm_point_nearer(p_x, p_y, q_a_x, q_a_y, p_r))
484 return 1;
485 if (tenm_point_nearer(p_x, p_y, q_b_x, q_b_y, p_r))
486 return 1;
487
488 if (! tenm_line_nearer(p_x, p_y,
489 q_a_x, q_a_y, q_b_x, q_b_y, p_r))
490 return 0;
491 if (tenm_same_side_vertical(q_a_x, q_a_y, q_b_x, q_b_y,
492 q_a_x, q_a_y, q_b_x, q_b_y,
493 p_x, p_y))
494 return 0;
495 return 1;
496 }
497
498 static int
tenm_collided_circle_polygon(const tenm_circle * p,const tenm_polygon * q)499 tenm_collided_circle_polygon(const tenm_circle *p,
500 const tenm_polygon *q)
501 {
502 int i;
503 int j;
504 int temp;
505
506 /* first, assume a sufficiently large rectangle */
507 temp = 1;
508 for (i = 0; i < q->n; i++)
509 if (p->center->x + p->r >= q->v[i]->x)
510 {
511 temp = 0;
512 break;
513 }
514 if (temp == 1)
515 return 0;
516
517 temp = 1;
518 for (i = 0; i < q->n; i++)
519 if (p->center->x - p->r <= q->v[i]->x)
520 {
521 temp = 0;
522 break;
523 }
524 if (temp == 1)
525 return 0;
526
527 temp = 1;
528 for (i = 0; i < q->n; i++)
529 if (p->center->y + p->r >= q->v[i]->y)
530 {
531 temp = 0;
532 break;
533 }
534 if (temp == 1)
535 return 0;
536
537 temp = 1;
538 for (i = 0; i < q->n; i++)
539 if (p->center->y - p->r <= q->v[i]->y)
540 {
541 temp = 0;
542 break;
543 }
544 if (temp == 1)
545 return 0;
546
547 /* now, the expensive check */
548 for (i = 0; i < q->n; i++)
549 for (j = i + 1; j < q->n; j++)
550 if (tenm_collided_circle_segment2(p->center->x, p->center->y, p->r,
551 q->v[i]->x, q->v[i]->y,
552 q->v[j]->x, q->v[j]->y))
553 return 1;
554
555 return tenm_collided_point_polygon(p->center, q);
556 }
557 static int
tenm_collided_segment_segment(const tenm_segment * p,const tenm_segment * q)558 tenm_collided_segment_segment(const tenm_segment *p,
559 const tenm_segment *q)
560 {
561 return tenm_collided_segment_segment2(p->a->x, p->a->y, p->b->x, p->b->y,
562 q->a->x, q->a->y, q->b->x, q->b->y);
563 }
564
565 static int
tenm_collided_segment_segment2(double p_a_x,double p_a_y,double p_b_x,double p_b_y,double q_a_x,double q_a_y,double q_b_x,double q_b_y)566 tenm_collided_segment_segment2(double p_a_x, double p_a_y,
567 double p_b_x, double p_b_y,
568 double q_a_x, double q_a_y,
569 double q_b_x, double q_b_y)
570 {
571 /* we need this point-on-segment checks first because tenm_same_side
572 * counts "on the line" as either side
573 */
574 if (tenm_collided_circle_segment2(p_a_x, p_a_y, 0.5,
575 q_a_x, q_a_y, q_b_x, q_b_y))
576 return 1;
577 if (tenm_collided_circle_segment2(p_b_x, p_b_y, 0.5,
578 q_a_x, q_a_y, q_b_x, q_b_y))
579 return 1;
580 if (tenm_collided_circle_segment2(q_a_x, q_a_y, 0.5,
581 p_a_x, p_a_y, p_b_x, p_b_y))
582 return 1;
583 if (tenm_collided_circle_segment2(q_b_x, q_b_y, 0.5,
584 p_a_x, p_a_y, p_b_x, p_b_y))
585 return 1;
586
587 if (tenm_same_side(p_a_x, p_a_y, p_b_x, p_b_y,
588 q_a_x, q_a_y, q_b_x, q_b_y))
589 return 0;
590 if (tenm_same_side(q_a_x, q_a_y, q_b_x, q_b_y,
591 p_a_x, p_a_y, p_b_x, p_b_y))
592 return 0;
593 return 1;
594 }
595
596 static int
tenm_collided_segment_polygon(const tenm_segment * p,const tenm_polygon * q)597 tenm_collided_segment_polygon(const tenm_segment *p,
598 const tenm_polygon *q)
599 {
600 int i;
601 int j;
602 int temp;
603
604 /* first, assume a sufficiently large rectangle */
605 temp = 1;
606 for (i = 0; i < q->n; i++)
607 {
608 if (p->a->x >= q->v[i]->x)
609 {
610 temp = 0;
611 break;
612 }
613 if (p->b->x >= q->v[i]->x)
614 {
615 temp = 0;
616 break;
617 }
618 }
619 if (temp == 1)
620 return 0;
621
622 temp = 1;
623 for (i = 0; i < q->n; i++)
624 {
625 if (p->a->x <= q->v[i]->x)
626 {
627 temp = 0;
628 break;
629 }
630 if (p->b->x <= q->v[i]->x)
631 {
632 temp = 0;
633 break;
634 }
635 }
636 if (temp == 1)
637 return 0;
638
639 temp = 1;
640 for (i = 0; i < q->n; i++)
641 {
642 if (p->a->y >= q->v[i]->y)
643 {
644 temp = 0;
645 break;
646 }
647 if (p->b->y >= q->v[i]->y)
648 {
649 temp = 0;
650 break;
651 }
652 }
653 if (temp == 1)
654 return 0;
655
656 temp = 1;
657 for (i = 0; i < q->n; i++)
658 {
659 if (p->a->y <= q->v[i]->y)
660 {
661 temp = 0;
662 break;
663 }
664 if (p->b->y <= q->v[i]->y)
665 {
666 temp = 0;
667 break;
668 }
669 }
670 if (temp == 1)
671 return 0;
672
673 /* now, the expensive check */
674 for (i = 0; i < q->n; i++)
675 for (j = i + 1; j < q->n; j++)
676 if (tenm_collided_segment_segment2(p->a->x, p->a->y,
677 p->b->x, p->b->y,
678 q->v[i]->x, q->v[i]->y,
679 q->v[j]->x, q->v[j]->y))
680 return 1;
681
682 if (tenm_collided_point_polygon(p->a, q))
683 return 1;
684 if (tenm_collided_point_polygon(p->b, q))
685 return 1;
686 return 0;
687 }
688
689 static int
tenm_collided_polygon_polygon(const tenm_polygon * p,const tenm_polygon * q)690 tenm_collided_polygon_polygon(const tenm_polygon *p, const tenm_polygon *q)
691 {
692 int i;
693 int j;
694 int k;
695 int l;
696 int temp;
697
698 /* first, assume a sufficiently large rectangle */
699 temp = 1;
700 for (i = 0; i < p->n; i++)
701 for (j = 0; j < q->n; j++)
702 if (p->v[i]->x >= q->v[j]->x)
703 {
704 temp = 0;
705 break;
706 }
707 if (temp == 1)
708 return 0;
709
710 temp = 1;
711 for (i = 0; i < p->n; i++)
712 for (j = 0; j < q->n; j++)
713 if (p->v[i]->x <= q->v[j]->x)
714 {
715 temp = 0;
716 break;
717 }
718 if (temp == 1)
719 return 0;
720
721 temp = 1;
722 for (i = 0; i < p->n; i++)
723 for (j = 0; j < q->n; j++)
724 if (p->v[i]->y >= q->v[j]->y)
725 {
726 temp = 0;
727 break;
728 }
729 if (temp == 1)
730 return 0;
731
732 temp = 1;
733 for (i = 0; i < p->n; i++)
734 for (j = 0; j < q->n; j++)
735 if (p->v[i]->y <= q->v[j]->y)
736 {
737 temp = 0;
738 break;
739 }
740 if (temp == 1)
741 return 0;
742
743 /* now, the expensive check */
744 for (i = 0; i < p->n; i++)
745 for (j = i + 1; j < p->n; j++)
746 for (k = 0; k < q->n; k++)
747 for (l = k + 1; l < q->n; l++)
748 if (tenm_collided_segment_segment2(p->v[i]->x, p->v[i]->y,
749 p->v[j]->x, p->v[j]->y,
750 q->v[k]->x, q->v[k]->y,
751 q->v[l]->x, q->v[l]->y))
752 return 1;
753
754 for (i = 0; i < p->n; i++)
755 if (tenm_collided_point_polygon(p->v[i], q))
756 return 1;
757 for (i = 0; i < q->n; i++)
758 if (tenm_collided_point_polygon(q->v[i], p))
759 return 1;
760 return 0;
761 }
762