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