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