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 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 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 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 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