1 #ifndef lint
2 static char *sccsid ="opqpoly.c (CWI) 1.1 85/03/01";
3 #endif
4 #include "ideal.h"
5 #include "y.tab.h"
6
7 extern float interalpha[INTERSIZE];
8 extern int internum;
9
opqpoly(edgelist,linelist,inlines,outlines,both)10 void opqpoly (edgelist, linelist, inlines, outlines, both)
11 EDGEPTR edgelist;
12 LINEPTR linelist;
13 LINEPTR *inlines, *outlines, *both;
14 {
15 LINEPTR linewalk, circlearc;
16 LINENODE nuin, nuout, nuboth;
17 LINEPTR inwalk, outwalk, bothwalk;
18 LINEPTR forfreeing;
19
20 inwalk = &nuin;
21 inwalk->next = NULL;
22 outwalk = &nuout;
23 outwalk->next = NULL;
24 bothwalk = &nuboth;
25 bothwalk->next = NULL;
26 linewalk = linelist;
27 while (linewalk) {
28 while (inwalk->next)
29 inwalk = inwalk->next;
30 while (outwalk->next)
31 outwalk = outwalk->next;
32 while (bothwalk->next)
33 bothwalk = bothwalk->next;
34 switch (linewalk->kind) {
35 case LINE:
36 polyline (
37 edgelist,
38 linewalk->x0,
39 linewalk->y0,
40 linewalk->x1,
41 linewalk->y1,
42 &inwalk->next,
43 &outwalk->next,
44 &bothwalk->next
45 );
46 forfreeing = linewalk;
47 linewalk = linewalk->next;
48 tryfree(forfreeing);
49 break;
50 case CIRCLE:
51 circlearc = angularc (
52 ((CIRCPTR) linewalk)->x0,
53 ((CIRCPTR) linewalk)->y0,
54 ((CIRCPTR) linewalk)->r,
55 0.0,
56 2.0*PI
57 );
58 circlearc->next = linewalk->next;
59 tryfree(linewalk);
60 linewalk = circlearc;
61 /* FALL THROUGH TO case arc */
62 case ARC:
63 polyarc (
64 edgelist,
65 ((ARCPTR) linewalk)->x0,
66 ((ARCPTR) linewalk)->y0,
67 ((ARCPTR) linewalk)->radius,
68 ((ARCPTR) linewalk)->theta1,
69 ((ARCPTR) linewalk)->theta2,
70 &inwalk->next,
71 &outwalk->next,
72 &bothwalk->next
73 );
74 forfreeing = linewalk;
75 linewalk = linewalk->next;
76 tryfree(forfreeing);
77 break;
78 case STRING:
79 /*
80 fprintf (stderr, "ideal: can't opaque over strings\n");
81 */
82 bothwalk->next = linewalk;
83 linewalk = linewalk->next;
84 bothwalk->next->next = NULL;
85 break;
86 case SPLINE:
87 /*
88 fprintf (stderr, "ideal: can't opaque over splines\n");
89 */
90 bothwalk->next = linewalk;
91 linewalk = linewalk->next;
92 bothwalk->next->next = NULL;
93 break;
94 default:
95 impossible ("opqpoly");
96 break;
97 } /* switch */
98 } /* while */
99 *inlines = nuin.next;
100 *outlines = nuout.next;
101 *both = nuboth.next;
102 } /* opqpoly */
103
polyline(edgelist,candx0,candy0,candx1,candy1,inlines,outlines,both)104 void polyline (edgelist, candx0,candy0, candx1,candy1, inlines, outlines, both)
105 EDGEPTR edgelist;
106 float candx0,candy0, candx1,candy1;
107 LINEPTR *inlines, *outlines, *both;
108 {
109 OPQPTR interwalk;
110 boolean inside, onedge;
111 LINENODE nuin, nuout;
112 LINEPTR inwalk, outwalk;
113 LINEPTR linewalk;
114 EDGEPTR prevedge, curedge;
115 OPQPTR alphalist;
116 float alpha, beta;
117 float gamma[2], theta[2];
118 boolean collinear;
119 boolean X, Y, Z, W;
120 int i;
121 double dummy, rem;
122
123 alphalist = (OPQPTR) NULL;
124 inwalk = &nuin;
125 inwalk->next = NULL;
126 outwalk = &nuout;
127 outwalk->next = NULL;
128 curedge = edgelist;
129 do {
130 if (curedge->fax == NULL) {
131 if (
132 llinter (
133 candx0, candy0,
134 candx1, candy1,
135 curedge->sx, curedge->sy,
136 curedge->ex, curedge->ey,
137 &alpha,
138 &beta,
139 &collinear
140 )
141 ) {
142 if (EPSILON < beta && beta < 1.0 - EPSILON)
143 curedge->code[0] = SIMPLE;
144 else if (fabs(beta) < EPSILON)
145 curedge->code[0] = AT0;
146 else if (fabs(1.0-beta) < EPSILON)
147 curedge->code[0] = AT1;
148 else
149 curedge->code[0] = UNUSED;
150 curedge->alpha[0] = alpha;
151 curedge->code[1] = UNUSED;
152 } else
153 if (collinear) {
154 if (fabs(candx1 - candx0) < EPSILON) {
155 curedge->alpha[0] = (curedge->sy - candy0)/(candy1 - candy0);
156 curedge->alpha[1] = (curedge->ey - candy0)/(candy1 - candy0);
157 } else {
158 curedge->alpha[0] = (curedge->sx - candx0)/(candx1 - candx0);
159 curedge->alpha[1] = (curedge->ex - candx0)/(candx1 - candx0);
160 }
161 if (curedge->alpha[0] < curedge->alpha[1]) {
162 curedge->code[0] = ON0;
163 curedge->code[1] = ON1;
164 } else {
165 curedge->code[0] = ON1;
166 curedge->code[1] = ON0;
167 }
168 } else
169 curedge->code[0] = curedge->code[1] = UNUSED;
170 } else if (curedge->fax->kind == ARC) {
171 if (
172 !lcinter (
173 candx0, candy0,
174 candx1, candy1,
175 curedge->fax->x0, curedge->fax->y0,
176 fabs(curedge->fax->radius),
177 &gamma[0], &theta[0],
178 &gamma[1], &theta[1]
179 )
180 ) {
181 curedge->code[0] = curedge->code[1] = UNUSED;
182 dprintf "line outside circle\n");
183 } else if (fabs(theta[0] - theta[1]) < EPSILON) {
184 if (fabs(theta[0] - curedge->fax->theta1) < EPSILON) {
185 curedge->alpha[0] = gamma[0];
186 curedge->code[0] = curedge->flipped?AT1:AT0;
187 dprintf "%d\n", curedge->code[0]);
188 } else if (fabs(theta[0] - curedge->fax->theta2) < EPSILON) {
189 curedge->alpha[0] = gamma[0];
190 curedge->code[0] = curedge->flipped?AT0:AT1;
191 dprintf "%d\n", curedge->code[0]);
192 } else {
193 curedge->code[0] = UNUSED;
194 dprintf "line tangent\n");
195 }
196 curedge->code[1] = UNUSED;
197 } else {
198 for (i = 0; i < 2; i ++) {
199 dprintf "disposition of %f\n", theta[i]);
200 if (curedge->fax->theta2 < 2.0*PI) {
201 if (theta[i] - curedge->fax->theta1 < -EPSILON
202 || curedge->fax->theta2 - theta[i] < -EPSILON) {
203 curedge->code[i] = UNUSED;
204 dprintf "intersection off arc\n");
205 continue;
206 }
207 }
208 if (curedge->fax->theta2 >= 2.0*PI) {
209 if (theta[i] - curedge->fax->theta1 < -EPSILON
210 && curedge->fax->theta2 - theta[i] < 2.0*PI - EPSILON) {
211 curedge->code[i] = UNUSED;
212 dprintf "intersection off arc\n");
213 continue;
214 }
215 }
216 rem = modf(fabs(theta[i] - curedge->fax->theta1)/(2*PI), &dummy);
217 dprintf "rem1 = %f\n", rem);
218 if (rem < EPSILON || fabs(1.0-rem) < EPSILON) {
219 curedge->alpha[i] = gamma[i];
220 curedge->code[i] = curedge->flipped?AT1:AT0;
221 dprintf "%d\n", curedge->code[i]);
222 continue;
223 }
224 rem = modf(fabs(theta[i] - curedge->fax->theta2)/(2*PI), &dummy);
225 dprintf "rem2 = %f\n", rem);
226 if (rem < EPSILON || fabs(1.0-rem) < EPSILON) {
227 curedge->alpha[i] = gamma[i];
228 curedge->code[i] = curedge->flipped?AT0:AT1;
229 dprintf "%d\n", curedge->code[i]);
230 continue;
231 }
232 dprintf "simple\n");
233 curedge->code[i] = SIMPLE;
234 curedge->alpha[i] = gamma[i];
235 }
236 }
237 } else
238 impossible ("polyline(A)");
239 curedge = curedge->next;
240 } while (curedge != edgelist);
241 if (dbg) {
242 curedge = edgelist;
243 do {
244 fprintf (stderr, "s (%f,%f); e (%f,%f)\n",
245 curedge->sx, curedge->sy,
246 curedge->ex, curedge->ey
247 );
248 fprintf (stderr, "st (%f,%f); et (%f,%f)\n",
249 curedge->stx, curedge->sty,
250 curedge->etx, curedge->ety
251 );
252 for (i = 0; i < POSSINTER; i ++)
253 fprintf (stderr, "%d %f\n",
254 curedge->code[i],
255 curedge->alpha[i]
256 );
257 curedge = curedge->next;
258 } while (curedge != edgelist);
259 }
260 prevedge = edgelist;
261 curedge = edgelist->next;
262 do {
263 for (i = 0; i < POSSINTER; i ++)
264 switch (curedge->code[i]) {
265 case UNUSED:
266 break;
267 case SIMPLE:
268 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
269 break;
270 case AT0:
271 dprintf "vertex intersection at (%f,%f)\n", curedge->sx, curedge->sy);
272 X = arecollinear(curedge->sx,curedge->sy,curedge->stx,curedge->sty,prevedge->etx,prevedge->ety);
273 Y = between(curedge->stx,curedge->sty,curedge->sx,curedge->sy,prevedge->etx,prevedge->ety);
274 Z = arecollinear(candx0,candy0,candx1,candy1,curedge->stx,curedge->sty);
275 dprintf "X=%d Y=%d Z=%d\n", X, Y, Z);
276 if (X && !Z) {
277 if (Y)
278 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
279 break;
280 }
281 if (X && Z) {
282 if (
283 llinter (
284 prevedge->sx, prevedge->sy,
285 curedge->ex, curedge->ey,
286 candx0, candy0,
287 candx1, candy1,
288 &alpha,
289 &beta,
290 &collinear
291 )
292 && (0.0 < alpha)
293 && (alpha < 1.0)
294 )
295 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
296 break;
297 }
298 if (!X) {
299 if (
300 llinter (
301 prevedge->etx, prevedge->ety,
302 curedge->stx, curedge->sty,
303 candx0, candy0,
304 candx1, candy1,
305 &alpha,
306 &beta,
307 &collinear
308 )
309 && (alpha > 0.0)
310 && (alpha < 1.0)
311 )
312 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
313 break;
314 }
315 impossible("polyline(II:AT0)");
316 break;
317 case AT1:
318 /* should be taken care of by next AT0 */
319 break;
320 case ON0:
321 case ON1:
322 X = arecollinear(prevedge->etx,prevedge->ety,curedge->sx,curedge->sy,curedge->next->stx,curedge->next->sty);
323 Y = llinter(
324 prevedge->etx,prevedge->ety,
325 curedge->next->stx,curedge->sty,
326 candx0,candy0,
327 candx1,candy1,
328 &alpha,
329 &beta,
330 &collinear
331 )
332 && (alpha > 0.0)
333 && (alpha < 1.0)
334 ;
335 Z = llinter (
336 prevedge->sx,prevedge->sy,
337 curedge->next->ex,curedge->next->ey,
338 candx0,candy0,
339 candx1,candy1,
340 &alpha,
341 &beta,
342 &collinear
343 )
344 && (alpha > 0.0)
345 && (alpha < 1.0)
346 ;
347 W = prevedge == curedge->next->next;
348 dprintf "X=%d Y=%d, Z=%d, W=%d\n", X, Y, Z, W);
349 if (!Y && W)
350 opqinsert((curedge->code[i] == ON0)?EXT0:EXT1, curedge->alpha[i], &alphalist);
351 else if (!X && Y)
352 opqinsert((curedge->code[i] == ON0)?INFL0:INFL1, curedge->alpha[i], &alphalist);
353 else if (X && Z)
354 opqinsert((curedge->code[i] == ON0)?INFL0:INFL1, curedge->alpha[i], &alphalist);
355 else
356 opqinsert((curedge->code[i] == ON0)?EXT0:EXT1, curedge->alpha[i], &alphalist);
357 break;
358 case TANGENT:
359 default:
360 impossible ("polyline(B)");
361 break;
362 }
363 prevedge = curedge;
364 curedge = curedge->next;
365 } while (prevedge != edgelist);
366 opqinsert(INHERIT, 0.0, &alphalist);
367 opqinsert(INHERIT, 1.0, &alphalist);
368 if (dbg) {
369 fprintf (stderr, "interalpha:\n");
370 for (interwalk = alphalist;
371 interwalk;
372 interwalk = interwalk->next)
373 fprintf (stderr, "%d %f, ", interwalk->code, interwalk->alpha);
374 fprintf (stderr, "\n");
375 }
376 inside = onedge = FALSE;
377 for (interwalk = alphalist; interwalk; interwalk = interwalk->next)
378 switch (interwalk->code) {
379 case SIMPLE:
380 interwalk->code = (!inside)?INBEGIN:OUTBEGIN;
381 inside = !inside;
382 break;
383 case EXT1:
384 interwalk->code = inside?INBEGIN:OUTBEGIN;
385 onedge = FALSE;
386 break;
387 case EXT0:
388 interwalk->code = ONBEGIN;
389 onedge = TRUE;
390 break;
391 case INFL1:
392 interwalk->code = (!inside)?INBEGIN:OUTBEGIN;
393 onedge = FALSE;
394 inside = !inside;
395 break;
396 case INFL0:
397 interwalk->code = ONBEGIN;
398 onedge = TRUE;
399 break;
400 case INHERIT:
401 case IGNORE:
402 interwalk->code = onedge?ONBEGIN:(inside?INBEGIN:OUTBEGIN);
403 break;
404 break;
405 default:
406 impossible("polyline(C)");
407 break;
408 }
409 if (dbg) {
410 fprintf (stderr, "interalpha:\n");
411 for (interwalk = alphalist;
412 interwalk;
413 interwalk = interwalk->next)
414 fprintf (stderr, "%d %f, ", interwalk->code, interwalk->alpha);
415 fprintf (stderr, "\n");
416 }
417 for (interwalk = alphalist; interwalk; interwalk = interwalk->next) {
418 linewalk = linegen (
419 candx0 + interwalk->alpha*(candx1 - candx0),
420 candy0 + interwalk->alpha*(candy1 - candy0),
421 candx0 + interwalk->next->alpha*(candx1 - candx0),
422 candy0 + interwalk->next->alpha*(candy1 - candy0)
423 );
424 if (
425 interwalk->alpha > -EPSILON
426 && interwalk->next
427 && interwalk->next->alpha < 1.0 + EPSILON
428 )
429 switch (interwalk->code) {
430 case INBEGIN:
431 inwalk->next = linewalk;
432 inwalk = inwalk->next;
433 break;
434 case OUTBEGIN:
435 outwalk->next = linewalk;
436 outwalk = outwalk->next;
437 break;
438 case ONBEGIN:
439 tryfree(linewalk);
440 break;
441 default:
442 impossible("polyline(D)");
443 break;
444 }
445 }
446 *inlines = nuin.next;
447 *outlines = nuout.next;
448 *both = NULL;
449 }
450
451 #define xtanp(x,y,r,t) x+r*cos(t)+sin(t)
452 #define ytanp(x,y,r,t) y+r*sin(t)-cos(t)
453 #define xtane(x,y,r,t) x+r*cos(t)-sin(t)
454 #define ytane(x,y,r,t) y+r*sin(t)+cos(t)
455
ptinpoly(edgelist,x,y)456 boolean ptinpoly (edgelist, x, y)
457 EDGEPTR edgelist;
458 float x, y;
459 {
460 LINEPTR inlines, outlines, both;
461 polyline (
462 edgelist,
463 x - 100*EPSILON, y - 100*EPSILON,
464 x + 100*EPSILON, y + 100*EPSILON,
465 &inlines, &outlines, &both
466 );
467 if (inlines) {
468 if (outlines || both)
469 impossible ("ptinpoly(A)");
470 else {
471 linefree(inlines);
472 dprintf "ptinpoly: TRUE\n");
473 return TRUE;
474 }
475 } else if (outlines) {
476 if (inlines || both)
477 impossible ("ptinpoly(B)");
478 else {
479 linefree(outlines);
480 dprintf "ptinpoly: FALSE\n");
481 return FALSE;
482 }
483 } else
484 impossible ("ptinpoly(C)");
485 }
486
polyarc(edgelist,x0,y0,radius,startang,endang,inlines,outlines,both)487 void polyarc (edgelist, x0,y0, radius, startang, endang, inlines, outlines, both)
488 EDGEPTR edgelist;
489 float x0, y0, radius, startang, endang;
490 LINEPTR *inlines, *outlines, *both;
491 {
492 OPQPTR interwalk;
493 boolean inside, onedge;
494 LINENODE nuin, nuout;
495 LINEPTR inwalk, outwalk;
496 LINEPTR linewalk;
497 EDGEPTR prevedge, curedge;
498 OPQPTR alphalist;
499 float alpha[2], beta[2], gamma[2], theta[2];
500 boolean collinear;
501 boolean X, Y, Z, W;
502 float stx, sty, etx, ety;
503 int i;
504 double dummy, rem;
505
506 alphalist = (OPQPTR) NULL;
507 inwalk = &nuin;
508 inwalk->next = NULL;
509 outwalk = &nuout;
510 outwalk->next = NULL;
511 curedge = edgelist;
512 do {
513 if (curedge->fax == NULL) {
514 if (
515 lcinter (
516 curedge->sx, curedge->sy,
517 curedge->ex, curedge->ey,
518 x0, y0,
519 radius,
520 &alpha[0], &theta[0],
521 &alpha[1], &theta[1]
522 )
523 ) {
524 if (fabs(theta[0] - theta[1]) < EPSILON) {
525 if (fabs(alpha[0]) < EPSILON)
526 curedge->code[0] = AT0;
527 else if (fabs(1.0-alpha[0]) < EPSILON)
528 curedge->code[0] = AT1;
529 else
530 curedge->code[0] = TANGENT;
531 curedge->alpha[0] = rprin(theta[0]);
532 curedge->code[1] = UNUSED;
533 } else {
534 for (i = 0; i < 2; i ++) {
535 if (EPSILON < alpha[i] && alpha[i] < 1.0 - EPSILON)
536 curedge->code[i] = SIMPLE;
537 else if (fabs(alpha[i]) < EPSILON)
538 curedge->code[i] = AT0;
539 else if (fabs(alpha[i] - 1.0) < EPSILON)
540 curedge->code[i] = AT1;
541 else
542 curedge->code[i] = UNUSED;
543 curedge->alpha[i] = rprin(theta[i]);
544 }
545 }
546 }
547 } else if (curedge->fax->kind == ARC) {
548 if (!ccinter (
549 x0, y0,
550 radius,
551 curedge->fax->x0, curedge->fax->y0,
552 curedge->fax->radius,
553 &gamma[0], &theta[0],
554 &gamma[1], &theta[1]
555 )
556 ) {
557 if (fabs(x0 - curedge->fax->x0) < EPSILON
558 && fabs(y0 - curedge->fax->y0) < EPSILON
559 && fabs(fabs(radius) - fabs(curedge->fax->radius)) < EPSILON
560 ) {
561 curedge->alpha[0] = rprin(curedge->fax->theta1);
562 curedge->alpha[1] = rprin(curedge->fax->theta2);
563 curedge->code[0] = ON0;
564 curedge->code[1] = ON1;
565 } else {
566 curedge->code[0] = curedge->code[1] = UNUSED;
567 }
568 } else if (fabs(theta[0] - theta[1]) < EPSILON) {
569 if (fabs(theta[0] - curedge->fax->theta1) < EPSILON)
570 curedge->code[0] = curedge->flipped?AT1:AT0;
571 else if (fabs(theta[0] - curedge->fax->theta2) < EPSILON)
572 curedge->code[0] = curedge->flipped?AT0:AT1;
573 else
574 curedge->code[0] = TANGENT;
575 curedge->alpha[0] = rprin(gamma[0]);
576 curedge->code[1] = UNUSED;
577 } else {
578 for (i = 0; i < 2; i ++) {
579 dprintf "disposition of %f\n", theta[i]);
580 if (curedge->fax->theta2 < 2.0*PI) {
581 if (theta[i] - curedge->fax->theta1 < -EPSILON
582 || curedge->fax->theta2 - theta[i] < -EPSILON) {
583 curedge->code[i] = UNUSED;
584 dprintf "intersection off arc\n");
585 continue;
586 }
587 }
588 if (curedge->fax->theta2 > 2.0*PI) {
589 if (theta[i] - curedge->fax->theta1 < -EPSILON
590 && curedge->fax->theta2 - theta[i] < 2.0*PI - EPSILON) {
591 curedge->code[i] = UNUSED;
592 dprintf "intersection off arc\n");
593 continue;
594 }
595 }
596 rem = modf(fabs(theta[i] - curedge->fax->theta1)/(2.0*PI), &dummy);
597 dprintf "rem1 = %f\n", rem);
598 if (rem < EPSILON || fabs(1.0 - rem) < EPSILON) {
599 curedge->alpha[i] = rprin(gamma[i]);
600 curedge->code[i] = curedge->flipped?AT1:AT0;
601 continue;
602 }
603 rem = modf(fabs(theta[i] - curedge->fax->theta2)/(2.0*PI), &dummy);
604 dprintf "rem2 = %f\n", rem);
605 if (rem < EPSILON || fabs(1.0 - rem) < EPSILON) {
606 curedge->alpha[i] = rprin(gamma[i]);
607 curedge->code[i] = curedge->flipped?AT0:AT1;
608 continue;
609 }
610 dprintf "simple\n");
611 curedge->code[i] = SIMPLE;
612 curedge->alpha[i] = rprin(gamma[i]);
613 }
614 }
615 } else {
616 impossible ("polyarc(D)");
617 }
618 curedge = curedge->next;
619 } while (curedge != edgelist);
620 if (dbg) {
621 curedge = edgelist;
622 do {
623 fprintf (stderr, "s (%f,%f); e (%f,%f)\n",
624 curedge->sx, curedge->sy,
625 curedge->ex, curedge->ey
626 );
627 fprintf (stderr, "st (%f,%f); et (%f,%f)\n",
628 curedge->stx, curedge->sty,
629 curedge->etx, curedge->ety
630 );
631 for (i = 0; i < POSSINTER; i ++)
632 fprintf (stderr, "%d %f\n",
633 curedge->code[i],
634 curedge->alpha[i]
635 );
636 curedge = curedge->next;
637 } while (curedge != edgelist);
638 }
639 prevedge = edgelist;
640 curedge = edgelist->next;
641 do {
642 for (i = 0; i < POSSINTER; i ++) {
643 stx = xtanp(x0,y0,radius,curedge->alpha[i]);
644 sty = ytanp(x0,y0,radius,curedge->alpha[i]);
645 etx = xtane(x0,y0,radius,curedge->alpha[i]);
646 ety = ytane(x0,y0,radius,curedge->alpha[i]);
647 switch (curedge->code[i]) {
648 case UNUSED:
649 break;
650 case SIMPLE:
651 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
652 break;
653 case AT0:
654 dprintf "vertex intersection at (%f,%f)\n", curedge->sx, curedge->sy);
655 X = arecollinear(curedge->sx,curedge->sy,curedge->stx,curedge->sty,prevedge->etx,prevedge->ety);
656 Y = between(curedge->stx,curedge->sty,curedge->sx,curedge->sy,prevedge->etx,prevedge->ety);
657 Z = arecollinear(stx,sty,etx,ety,curedge->stx, curedge->sty);
658 dprintf "X=%d Y=%d Z=%d\n", X, Y, Z);
659 if (X && !Z) {
660 if (Y)
661 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
662 break;
663 }
664 if (X && Z) {
665 if (
666 llinter (
667 prevedge->sx, prevedge->sy,
668 curedge->ex, curedge->ey,
669 stx, sty,
670 etx, ety,
671 &alpha[0],
672 &alpha[1],
673 &collinear
674 )
675 && (0.0 < alpha[0])
676 && (alpha[0] < 1.0)
677 )
678 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
679 break;
680 }
681 if (!X) {
682 if (
683 llinter (
684 prevedge->etx, prevedge->ety,
685 curedge->stx, curedge->sty,
686 stx, sty,
687 etx, ety,
688 &alpha[0],
689 &alpha[1],
690 &collinear
691 )
692 && (alpha[0] > 0.0)
693 && (alpha[0] < 1.0)
694 )
695 opqinsert(SIMPLE, curedge->alpha[i], &alphalist);
696 break;
697 }
698 impossible("polyline(II:AT0)");
699 break;
700 case AT1:
701 /* should be taken care of by next AT0 */
702 break;
703 case ON0:
704 case ON1:
705 X = hypot(prevedge->etx - x0, prevedge->ety - y0) > fabs(radius);
706 Y = hypot(curedge->next->stx - x0, curedge->next->sty - y0) > fabs(radius);
707 dprintf "X=%d Y=%d\n", X, Y);
708 Z = X && Y;
709 W = !X && !Y;
710 if (Z || W)
711 opqinsert((curedge->code[i] == ON0)?EXT0:EXT1, curedge->alpha[i], &alphalist);
712 else
713 opqinsert((curedge->code[i] == ON0)?INFL0:INFL1, curedge->alpha[i], &alphalist);
714 break;
715 case TANGENT:
716 opqinsert(IGNORE, curedge->alpha[i], &alphalist);
717 break;
718 default:
719 impossible ("polyline(B)");
720 break;
721 }
722 }
723 prevedge = curedge;
724 curedge = curedge->next;
725 } while (prevedge != edgelist);
726 opqinsert(INHERIT, rprin(startang), &alphalist);
727 opqinsert(INHERIT, rprin(endang), &alphalist);
728 if (dbg) {
729 fprintf (stderr, "interalpha:\n");
730 for (interwalk = alphalist;
731 interwalk;
732 interwalk = interwalk->next)
733 fprintf (stderr, "%d %f, ", interwalk->code, interwalk->alpha);
734 fprintf (stderr, "\n");
735 }
736 ((OPQPTR) tail((NAMEPTR) alphalist))->next = alphalist;
737 interwalk = alphalist;
738 onedge = FALSE;
739 do {
740 switch (interwalk->code) {
741 case EXT0:
742 alpha[0] = interwalk->alpha;
743 onedge = TRUE;
744 break;
745 case EXT1:
746 alpha[1] = interwalk->alpha;
747 onedge = TRUE;
748 break;
749 case INFL0:
750 alpha[0] = interwalk->alpha;
751 onedge = TRUE;
752 break;
753 case INFL1:
754 alpha[1] = interwalk->alpha;
755 onedge = TRUE;
756 break;
757 default:
758 break;
759 }
760 interwalk = interwalk->next;
761 } while (interwalk != alphalist);
762 if (onedge) {
763 rem = modf(fabs(alpha[0]-alpha[1])/(2.0*PI), &dummy);
764 if (rem < EPSILON || fabs(1.0-rem) < EPSILON)
765 return;
766 }
767 interwalk = alphalist;
768 do {
769 if (interwalk->code == EXT0 || interwalk->code == INFL0 || interwalk->code == INHERIT)
770 interwalk = interwalk->next;
771 else
772 break;
773 } while (interwalk != alphalist);
774 inside = ptinpoly (
775 edgelist,
776 x0 + fabs(radius)*cos((interwalk->alpha + interwalk->next->alpha)/2.0),
777 y0 + fabs(radius)*sin((interwalk->alpha + interwalk->next->alpha)/2.0)
778 );
779 dprintf "inside: %d\n", inside);
780 alphalist = interwalk->next;
781 interwalk = alphalist;
782 onedge = FALSE;
783 do {
784 switch (interwalk->code) {
785 case SIMPLE:
786 interwalk->code = (!inside)?INBEGIN:OUTBEGIN;
787 inside = !inside;
788 break;
789 case EXT1:
790 interwalk->code = inside?INBEGIN:OUTBEGIN;
791 onedge = FALSE;
792 break;
793 case EXT0:
794 interwalk->code = ONBEGIN;
795 onedge = TRUE;
796 break;
797 case INFL1:
798 interwalk->code = (!inside)?INBEGIN:OUTBEGIN;
799 inside = !inside;
800 onedge = FALSE;
801 break;
802 case INFL0:
803 interwalk->code = ONBEGIN;
804 onedge = TRUE;
805 break;
806 case INHERIT:
807 case IGNORE:
808 interwalk->code = onedge?ONBEGIN:(inside?INBEGIN:OUTBEGIN);
809 break;
810 default:
811 impossible("polyline(C)");
812 break;
813 }
814 interwalk = interwalk->next;
815 } while (interwalk != alphalist);
816 while (alphalist->alpha < alphalist->next->alpha)
817 alphalist = alphalist->next;
818 alphalist = alphalist->next;
819 if (dbg) {
820 fprintf (stderr, "interalpha:\n");
821 interwalk = alphalist;
822 do {
823 fprintf (stderr, "%d %f, ", interwalk->code, interwalk->alpha);
824 interwalk = interwalk->next;
825 } while (interwalk != alphalist);
826 fprintf (stderr, "\n");
827 }
828 interwalk = alphalist;
829 do {
830 if (interwalk->alpha > interwalk->next->alpha)
831 break;
832 if (endang < 2.0*PI + EPSILON) {
833 if (interwalk->alpha < startang - EPSILON || interwalk->alpha > endang + EPSILON) {
834 dprintf "arc rejected (A)\n");
835 interwalk = interwalk->next;
836 continue;
837 }
838 if (interwalk->next->alpha < startang - EPSILON || interwalk->next->alpha > endang + EPSILON) {
839 dprintf "arc rejected (B)\n");
840 interwalk = interwalk->next;
841 continue;
842 }
843 } else {
844 if (interwalk->alpha < startang - EPSILON && interwalk->alpha > endang + EPSILON - 2.0*PI) {
845 dprintf "arc rejected (C)\n");
846 interwalk = interwalk->next;
847 continue;
848 }
849 if (interwalk->next->alpha < startang - EPSILON && interwalk->next->alpha > endang + EPSILON - 2.0*PI) {
850 dprintf "arc rejected (D)\n");
851 interwalk = interwalk->next;
852 continue;
853 }
854 }
855 linewalk = angularc (
856 x0, y0,
857 radius,
858 interwalk->alpha,
859 interwalk->next->alpha
860 );
861 switch (interwalk->code) {
862 case INBEGIN:
863 inwalk->next = linewalk;
864 inwalk = inwalk->next;
865 break;
866 case OUTBEGIN:
867 outwalk->next = linewalk;
868 outwalk = outwalk->next;
869 break;
870 case ONBEGIN:
871 tryfree(linewalk);
872 break;
873 default:
874 impossible("polyline(D)");
875 break;
876 }
877 interwalk = interwalk->next;
878 } while (interwalk != alphalist);
879 *inlines = nuin.next;
880 *outlines = nuout.next;
881 *both = NULL;
882 }
883