![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tktrig.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Micropolis - Activity] / micropolis / src / tk|
Return to tktrig.c CVS log | Up to [Micropolis - Activity] / micropolis / src / tk |
1.1 ! root 1: /* ! 2: * tkTrig.c -- ! 3: * ! 4: * This file contains a collection of trigonometry utility ! 5: * routines that are used by Tk and in particular by the ! 6: * canvas code. It also has miscellaneous geometry functions ! 7: * used by canvases. ! 8: * ! 9: * Copyright 1992 Regents of the University of California. ! 10: * Permission to use, copy, modify, and distribute this ! 11: * software and its documentation for any purpose and without ! 12: * fee is hereby granted, provided that the above copyright ! 13: * notice appear in all copies. The University of California ! 14: * makes no representations about the suitability of this ! 15: * software for any purpose. It is provided "as is" without ! 16: * express or implied warranty. ! 17: */ ! 18: ! 19: #ifndef lint ! 20: static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTrig.c,v 1.8 92/08/24 09:24:14 ouster Exp $ SPRITE (Berkeley)"; ! 21: #endif ! 22: ! 23: #include <stdio.h> ! 24: #include <math.h> ! 25: #include "tkconfig.h" ! 26: #include "tkcanvas.h" ! 27: ! 28: #undef MIN ! 29: #define MIN(a,b) (((a) < (b)) ? (a) : (b)) ! 30: #undef MAX ! 31: #define MAX(a,b) (((a) > (b)) ? (a) : (b)) ! 32: #define PI 3.14159265358979323846 ! 33: ! 34: /* ! 35: *-------------------------------------------------------------- ! 36: * ! 37: * TkLineToPoint -- ! 38: * ! 39: * Compute the distance from a point to a finite line segment. ! 40: * ! 41: * Results: ! 42: * The return value is the distance from the line segment ! 43: * whose end-points are *end1Ptr and *end2Ptr to the point ! 44: * given by *pointPtr. ! 45: * ! 46: * Side effects: ! 47: * None. ! 48: * ! 49: *-------------------------------------------------------------- ! 50: */ ! 51: ! 52: double ! 53: TkLineToPoint(end1Ptr, end2Ptr, pointPtr) ! 54: double end1Ptr[2]; /* Coordinates of first end-point of line. */ ! 55: double end2Ptr[2]; /* Coordinates of second end-point of line. */ ! 56: double pointPtr[2]; /* Points to coords for point. */ ! 57: { ! 58: double x, y; ! 59: ! 60: /* ! 61: * Compute the point on the line that is closest to the ! 62: * point. This must be done separately for vertical edges, ! 63: * horizontal edges, and other edges. ! 64: */ ! 65: ! 66: if (end1Ptr[0] == end2Ptr[0]) { ! 67: ! 68: /* ! 69: * Vertical edge. ! 70: */ ! 71: ! 72: x = end1Ptr[0]; ! 73: if (end1Ptr[1] >= end2Ptr[1]) { ! 74: y = MIN(end1Ptr[1], pointPtr[1]); ! 75: y = MAX(y, end2Ptr[1]); ! 76: } else { ! 77: y = MIN(end2Ptr[1], pointPtr[1]); ! 78: y = MAX(y, end1Ptr[1]); ! 79: } ! 80: } else if (end1Ptr[1] == end2Ptr[1]) { ! 81: ! 82: /* ! 83: * Horizontal edge. ! 84: */ ! 85: ! 86: y = end1Ptr[1]; ! 87: if (end1Ptr[0] >= end2Ptr[0]) { ! 88: x = MIN(end1Ptr[0], pointPtr[0]); ! 89: x = MAX(x, end2Ptr[0]); ! 90: } else { ! 91: x = MIN(end2Ptr[0], pointPtr[0]); ! 92: x = MAX(x, end1Ptr[0]); ! 93: } ! 94: } else { ! 95: double m1, b1, m2, b2; ! 96: ! 97: /* ! 98: * The edge is neither horizontal nor vertical. Convert the ! 99: * edge to a line equation of the form y = m1*x + b1. Then ! 100: * compute a line perpendicular to this edge but passing ! 101: * through the point, also in the form y = m2*x + b2. ! 102: */ ! 103: ! 104: m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); ! 105: b1 = end1Ptr[1] - m1*end1Ptr[0]; ! 106: m2 = -1.0/m1; ! 107: b2 = pointPtr[1] - m2*pointPtr[0]; ! 108: x = (b2 - b1)/(m1 - m2); ! 109: y = m1*x + b1; ! 110: if (end1Ptr[0] > end2Ptr[0]) { ! 111: if (x > end1Ptr[0]) { ! 112: x = end1Ptr[0]; ! 113: y = end1Ptr[1]; ! 114: } else if (x < end2Ptr[0]) { ! 115: x = end2Ptr[0]; ! 116: y = end2Ptr[1]; ! 117: } ! 118: } else { ! 119: if (x > end2Ptr[0]) { ! 120: x = end2Ptr[0]; ! 121: y = end2Ptr[1]; ! 122: } else if (x < end1Ptr[0]) { ! 123: x = end1Ptr[0]; ! 124: y = end1Ptr[1]; ! 125: } ! 126: } ! 127: } ! 128: ! 129: /* ! 130: * Compute the distance to the closest point. ! 131: */ ! 132: ! 133: return hypot(pointPtr[0] - x, pointPtr[1] - y); ! 134: } ! 135: ! 136: /* ! 137: *-------------------------------------------------------------- ! 138: * ! 139: * TkLineToArea -- ! 140: * ! 141: * Determine whether a line lies entirely inside, entirely ! 142: * outside, or overlapping a given rectangular area. ! 143: * ! 144: * Results: ! 145: * -1 is returned if the line given by end1Ptr and end2Ptr ! 146: * is entirely outside the rectangle given by rectPtr. 0 is ! 147: * returned if the polygon overlaps the rectangle, and 1 is ! 148: * returned if the polygon is entirely inside the rectangle. ! 149: * ! 150: * Side effects: ! 151: * None. ! 152: * ! 153: *-------------------------------------------------------------- ! 154: */ ! 155: ! 156: int ! 157: TkLineToArea(end1Ptr, end2Ptr, rectPtr) ! 158: double end1Ptr[2]; /* X and y coordinates for one endpoint ! 159: * of line. */ ! 160: double end2Ptr[2]; /* X and y coordinates for other endpoint ! 161: * of line. */ ! 162: double rectPtr[4]; /* Points to coords for rectangle, in the ! 163: * order x1, y1, x2, y2. X1 must be no ! 164: * larger than x2, and y1 no larger than y2. */ ! 165: { ! 166: int inside1, inside2; ! 167: ! 168: /* ! 169: * First check the two points individually to see whether they ! 170: * are inside the rectangle or not. ! 171: */ ! 172: ! 173: inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2]) ! 174: && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]); ! 175: inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2]) ! 176: && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]); ! 177: if (inside1 != inside2) { ! 178: return 0; ! 179: } ! 180: if (inside1 & inside2) { ! 181: return 1; ! 182: } ! 183: ! 184: /* ! 185: * Both points are outside the rectangle, but still need to check ! 186: * for intersections between the line and the rectangle. Horizontal ! 187: * and vertical lines are particularly easy, so handle them ! 188: * separately. ! 189: */ ! 190: ! 191: if (end1Ptr[0] == end2Ptr[0]) { ! 192: /* ! 193: * Vertical line. ! 194: */ ! 195: ! 196: if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1])) ! 197: && (end1Ptr[0] >= rectPtr[0]) ! 198: && (end1Ptr[0] <= rectPtr[2])) { ! 199: return 0; ! 200: } ! 201: } else if (end1Ptr[1] == end2Ptr[1]) { ! 202: /* ! 203: * Horizontal line. ! 204: */ ! 205: ! 206: if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0])) ! 207: && (end1Ptr[1] >= rectPtr[1]) ! 208: && (end1Ptr[1] <= rectPtr[3])) { ! 209: return 0; ! 210: } ! 211: } else { ! 212: double m, x, y, low, high; ! 213: ! 214: /* ! 215: * Diagonal line. Compute slope of line and use ! 216: * for intersection checks against each of the ! 217: * sides of the rectangle: left, right, bottom, top. ! 218: */ ! 219: ! 220: m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); ! 221: if (end1Ptr[0] < end2Ptr[0]) { ! 222: low = end1Ptr[0]; high = end2Ptr[0]; ! 223: } else { ! 224: low = end2Ptr[0]; high = end1Ptr[0]; ! 225: } ! 226: ! 227: /* ! 228: * Left edge. ! 229: */ ! 230: ! 231: y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m; ! 232: if ((rectPtr[0] >= low) && (rectPtr[0] <= high) ! 233: && (y >= rectPtr[1]) && (y <= rectPtr[3])) { ! 234: return 0; ! 235: } ! 236: ! 237: /* ! 238: * Right edge. ! 239: */ ! 240: ! 241: y += (rectPtr[2] - rectPtr[0])*m; ! 242: if ((y >= rectPtr[1]) && (y <= rectPtr[3]) ! 243: && (rectPtr[2] >= low) && (rectPtr[2] <= high)) { ! 244: return 0; ! 245: } ! 246: ! 247: /* ! 248: * Bottom edge. ! 249: */ ! 250: ! 251: if (end1Ptr[1] < end2Ptr[1]) { ! 252: low = end1Ptr[1]; high = end2Ptr[1]; ! 253: } else { ! 254: low = end2Ptr[1]; high = end1Ptr[1]; ! 255: } ! 256: x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m; ! 257: if ((x >= rectPtr[0]) && (x <= rectPtr[2]) ! 258: && (rectPtr[1] >= low) && (rectPtr[1] <= high)) { ! 259: return 0; ! 260: } ! 261: ! 262: /* ! 263: * Top edge. ! 264: */ ! 265: ! 266: x += (rectPtr[3] - rectPtr[1])/m; ! 267: if ((x >= rectPtr[0]) && (x <= rectPtr[2]) ! 268: && (rectPtr[3] >= low) && (rectPtr[3] <= high)) { ! 269: return 0; ! 270: } ! 271: } ! 272: return -1; ! 273: } ! 274: ! 275: /* ! 276: *-------------------------------------------------------------- ! 277: * ! 278: * TkPolygonToPoint -- ! 279: * ! 280: * Compute the distance from a point to a polygon. ! 281: * ! 282: * Results: ! 283: * The return value is 0.0 if the point referred to by ! 284: * pointPtr is within the polygon referred to by polyPtr ! 285: * and numPoints. Otherwise the return value is the ! 286: * distance of the point from the polygon. ! 287: * ! 288: * Side effects: ! 289: * None. ! 290: * ! 291: *-------------------------------------------------------------- ! 292: */ ! 293: ! 294: double ! 295: TkPolygonToPoint(polyPtr, numPoints, pointPtr) ! 296: double *polyPtr; /* Points to an array coordinates for ! 297: * closed polygon: x0, y0, x1, y1, ... ! 298: * The polygon may be self-intersecting. */ ! 299: int numPoints; /* Total number of points at *polyPtr. */ ! 300: double *pointPtr; /* Points to coords for point. */ ! 301: { ! 302: double bestDist; /* Closest distance between point and ! 303: * any edge in polygon. */ ! 304: int intersections; /* Number of edges in the polygon that ! 305: * intersect a ray extending vertically ! 306: * upwards from the point to infinity. */ ! 307: int count; ! 308: register double *pPtr; ! 309: ! 310: /* ! 311: * Iterate through all of the edges in the polygon, updating ! 312: * bestDist and intersections. ! 313: * ! 314: * TRICKY POINT: when computing intersections, include left ! 315: * x-coordinate of line within its range, but not y-coordinate. ! 316: * Otherwise if the point lies exactly below a vertex we'll ! 317: * count it as two intersections. ! 318: */ ! 319: ! 320: bestDist = 1.0e40; ! 321: intersections = 0; ! 322: ! 323: for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) { ! 324: double x, y, dist; ! 325: ! 326: /* ! 327: * Compute the point on the current edge closest to the point ! 328: * and update the intersection count. This must be done ! 329: * separately for vertical edges, horizontal edges, and ! 330: * other edges. ! 331: */ ! 332: ! 333: if (pPtr[2] == pPtr[0]) { ! 334: ! 335: /* ! 336: * Vertical edge. ! 337: */ ! 338: ! 339: x = pPtr[0]; ! 340: if (pPtr[1] >= pPtr[3]) { ! 341: y = MIN(pPtr[1], pointPtr[1]); ! 342: y = MAX(y, pPtr[3]); ! 343: } else { ! 344: y = MIN(pPtr[3], pointPtr[1]); ! 345: y = MAX(y, pPtr[1]); ! 346: } ! 347: } else if (pPtr[3] == pPtr[1]) { ! 348: ! 349: /* ! 350: * Horizontal edge. ! 351: */ ! 352: ! 353: y = pPtr[1]; ! 354: if (pPtr[0] >= pPtr[2]) { ! 355: x = MIN(pPtr[0], pointPtr[0]); ! 356: x = MAX(x, pPtr[2]); ! 357: if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0]) ! 358: && (pointPtr[0] >= pPtr[2])) { ! 359: intersections++; ! 360: } ! 361: } else { ! 362: x = MIN(pPtr[2], pointPtr[0]); ! 363: x = MAX(x, pPtr[0]); ! 364: if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2]) ! 365: && (pointPtr[0] >= pPtr[0])) { ! 366: intersections++; ! 367: } ! 368: } ! 369: } else { ! 370: double m1, b1, m2, b2; ! 371: int lower; /* Non-zero means point below line. */ ! 372: ! 373: /* ! 374: * The edge is neither horizontal nor vertical. Convert the ! 375: * edge to a line equation of the form y = m1*x + b1. Then ! 376: * compute a line perpendicular to this edge but passing ! 377: * through the point, also in the form y = m2*x + b2. ! 378: */ ! 379: ! 380: m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]); ! 381: b1 = pPtr[1] - m1*pPtr[0]; ! 382: m2 = -1.0/m1; ! 383: b2 = pointPtr[1] - m2*pointPtr[0]; ! 384: x = (b2 - b1)/(m1 - m2); ! 385: y = m1*x + b1; ! 386: if (pPtr[0] > pPtr[2]) { ! 387: if (x > pPtr[0]) { ! 388: x = pPtr[0]; ! 389: y = pPtr[1]; ! 390: } else if (x < pPtr[2]) { ! 391: x = pPtr[2]; ! 392: y = pPtr[3]; ! 393: } ! 394: } else { ! 395: if (x > pPtr[2]) { ! 396: x = pPtr[2]; ! 397: y = pPtr[3]; ! 398: } else if (x < pPtr[0]) { ! 399: x = pPtr[0]; ! 400: y = pPtr[1]; ! 401: } ! 402: } ! 403: lower = (m1*pointPtr[0] + b1) > pointPtr[1]; ! 404: if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2])) ! 405: && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) { ! 406: intersections++; ! 407: } ! 408: } ! 409: ! 410: /* ! 411: * Compute the distance to the closest point, and see if that ! 412: * is the best distance seen so far. ! 413: */ ! 414: ! 415: dist = hypot(pointPtr[0] - x, pointPtr[1] - y); ! 416: if (dist < bestDist) { ! 417: bestDist = dist; ! 418: } ! 419: } ! 420: ! 421: /* ! 422: * We've processed all of the points. If the number of intersections ! 423: * is odd, the point is inside the polygon. ! 424: */ ! 425: ! 426: if (intersections & 0x1) { ! 427: return 0.0; ! 428: } ! 429: return bestDist; ! 430: } ! 431: ! 432: /* ! 433: *-------------------------------------------------------------- ! 434: * ! 435: * TkPolygonToArea -- ! 436: * ! 437: * Determine whether a polygon lies entirely inside, entirely ! 438: * outside, or overlapping a given rectangular area. ! 439: * ! 440: * Results: ! 441: * -1 is returned if the polygon given by polyPtr and numPoints ! 442: * is entirely outside the rectangle given by rectPtr. 0 is ! 443: * returned if the polygon overlaps the rectangle, and 1 is ! 444: * returned if the polygon is entirely inside the rectangle. ! 445: * ! 446: * Side effects: ! 447: * None. ! 448: * ! 449: *-------------------------------------------------------------- ! 450: */ ! 451: ! 452: int ! 453: TkPolygonToArea(polyPtr, numPoints, rectPtr) ! 454: double *polyPtr; /* Points to an array coordinates for ! 455: * closed polygon: x0, y0, x1, y1, ... ! 456: * The polygon may be self-intersecting. */ ! 457: int numPoints; /* Total number of points at *polyPtr. */ ! 458: register double *rectPtr; /* Points to coords for rectangle, in the ! 459: * order x1, y1, x2, y2. X1 and y1 must ! 460: * be lower-left corner. */ ! 461: { ! 462: int state; /* State of all edges seen so far (-1 means ! 463: * outside, 1 means inside, won't ever be ! 464: * 0). */ ! 465: int count; ! 466: register double *pPtr; ! 467: ! 468: /* ! 469: * Iterate over all of the edges of the polygon and test them ! 470: * against the rectangle. Can quit as soon as the state becomes ! 471: * "intersecting". ! 472: */ ! 473: ! 474: state = TkLineToArea(polyPtr, polyPtr+2, rectPtr); ! 475: if (state == 0) { ! 476: return 0; ! 477: } ! 478: for (pPtr = polyPtr+2, count = numPoints-1; count >= 2; ! 479: pPtr += 2, count--) { ! 480: if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) { ! 481: return 0; ! 482: } ! 483: } ! 484: ! 485: /* ! 486: * If all of the edges were inside the rectangle we're done. ! 487: * If all of the edges were outside, then the rectangle could ! 488: * still intersect the polygon (if it's entirely enclosed). ! 489: * Call TkPolygonToPoint to figure this out. ! 490: */ ! 491: ! 492: if (state == 1) { ! 493: return 1; ! 494: } ! 495: if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) { ! 496: return 0; ! 497: } ! 498: return -1; ! 499: } ! 500: ! 501: /* ! 502: *-------------------------------------------------------------- ! 503: * ! 504: * TkOvalToPoint -- ! 505: * ! 506: * Computes the distance from a given point to a given ! 507: * oval, in canvas units. ! 508: * ! 509: * Results: ! 510: * The return value is 0 if the point given by *pointPtr is ! 511: * inside the oval. If the point isn't inside the ! 512: * oval then the return value is approximately the distance ! 513: * from the point to the oval. If the oval is filled, then ! 514: * anywhere in the interior is considered "inside"; if ! 515: * the oval isn't filled, then "inside" means only the area ! 516: * occupied by the outline. ! 517: * ! 518: * Side effects: ! 519: * None. ! 520: * ! 521: *-------------------------------------------------------------- ! 522: */ ! 523: ! 524: /* ARGSUSED */ ! 525: double ! 526: TkOvalToPoint(ovalPtr, width, filled, pointPtr) ! 527: double ovalPtr[4]; /* Pointer to array of four coordinates ! 528: * (x1, y1, x2, y2) defining oval's bounding ! 529: * box. */ ! 530: double width; /* Width of outline for oval. */ ! 531: int filled; /* Non-zero means oval should be treated as ! 532: * filled; zero means only consider outline. */ ! 533: double pointPtr[2]; /* Coordinates of point. */ ! 534: { ! 535: double xDelta, yDelta, scaledDistance, distToOutline, distToCenter; ! 536: ! 537: /* ! 538: * Compute the distance between the center of the oval and the ! 539: * point in question, using a coordinate system where the oval ! 540: * has been transformed to a circle with unit radius. ! 541: */ ! 542: ! 543: xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0); ! 544: yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0); ! 545: distToCenter = hypot(xDelta, yDelta); ! 546: scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0), ! 547: yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0)); ! 548: ! 549: ! 550: /* ! 551: * If the scaled distance is greater than 1 then it means no ! 552: * hit. Compute the distance from the point to the edge of ! 553: * the circle, then scale this distance back to the original ! 554: * coordinate system. ! 555: * ! 556: * Note: this distance isn't completely accurate. It's only ! 557: * an approximation, and it can overestimate the correct ! 558: * distance when the oval is eccentric. ! 559: */ ! 560: ! 561: if (scaledDistance > 1.0) { ! 562: return (distToCenter/scaledDistance) * (scaledDistance - 1.0); ! 563: } ! 564: ! 565: /* ! 566: * Scaled distance less than 1 means the point is inside the ! 567: * outer edge of the oval. If this is a filled oval, then we ! 568: * have a hit. Otherwise, do the same computation as above ! 569: * (scale back to original coordinate system), but also check ! 570: * to see if the point is within the width of the outline. ! 571: */ ! 572: ! 573: if (filled) { ! 574: return 0.0; ! 575: } ! 576: distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance) ! 577: - width; ! 578: if (distToOutline < 0.0) { ! 579: return 0.0; ! 580: } ! 581: return distToOutline; ! 582: } ! 583: ! 584: /* ! 585: *-------------------------------------------------------------- ! 586: * ! 587: * TkOvalToArea -- ! 588: * ! 589: * Determine whether an oval lies entirely inside, entirely ! 590: * outside, or overlapping a given rectangular area. ! 591: * ! 592: * Results: ! 593: * -1 is returned if the oval described by ovalPtr is entirely ! 594: * outside the rectangle given by rectPtr. 0 is returned if the ! 595: * oval overlaps the rectangle, and 1 is returned if the oval ! 596: * is entirely inside the rectangle. ! 597: * ! 598: * Side effects: ! 599: * None. ! 600: * ! 601: *-------------------------------------------------------------- ! 602: */ ! 603: ! 604: int ! 605: TkOvalToArea(ovalPtr, rectPtr) ! 606: register double *ovalPtr; /* Points to coordinates definining the ! 607: * bounding rectangle for the oval: x1, y1, ! 608: * x2, y2. X1 must be less than x2 and y1 ! 609: * less than y2. */ ! 610: register double *rectPtr; /* Points to coords for rectangle, in the ! 611: * order x1, y1, x2, y2. X1 and y1 must ! 612: * be lower-left corner. */ ! 613: { ! 614: double centerX, centerY, radX, radY, deltaX, deltaY; ! 615: ! 616: /* ! 617: * First, see if oval is entirely inside rectangle or entirely ! 618: * outside rectangle. ! 619: */ ! 620: ! 621: if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2]) ! 622: && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) { ! 623: return 1; ! 624: } ! 625: if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2]) ! 626: || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) { ! 627: return -1; ! 628: } ! 629: ! 630: /* ! 631: * Next, go through the rectangle side by side. For each side ! 632: * of the rectangle, find the point on the side that is closest ! 633: * to the oval's center, and see if that point is inside the ! 634: * oval. If at least one such point is inside the oval, then ! 635: * the rectangle intersects the oval. ! 636: */ ! 637: ! 638: centerX = (ovalPtr[0] + ovalPtr[2])/2; ! 639: centerY = (ovalPtr[1] + ovalPtr[3])/2; ! 640: radX = (ovalPtr[2] - ovalPtr[0])/2; ! 641: radY = (ovalPtr[3] - ovalPtr[1])/2; ! 642: ! 643: deltaY = rectPtr[1] - centerY; ! 644: if (deltaY < 0.0) { ! 645: deltaY = centerY - rectPtr[3]; ! 646: if (deltaY < 0.0) { ! 647: deltaY = 0; ! 648: } ! 649: } ! 650: deltaY /= radY; ! 651: deltaY *= deltaY; ! 652: ! 653: /* ! 654: * Left side: ! 655: */ ! 656: ! 657: deltaX = (rectPtr[0] - centerX)/radX; ! 658: deltaX *= deltaX; ! 659: if ((deltaX + deltaY) <= 1.0) { ! 660: return 0; ! 661: } ! 662: ! 663: /* ! 664: * Right side: ! 665: */ ! 666: ! 667: deltaX = (rectPtr[2] - centerX)/radX; ! 668: deltaX *= deltaX; ! 669: if ((deltaX + deltaY) <= 1.0) { ! 670: return 0; ! 671: } ! 672: ! 673: deltaX = rectPtr[0] - centerX; ! 674: if (deltaX < 0.0) { ! 675: deltaX = centerX - rectPtr[2]; ! 676: if (deltaX < 0.0) { ! 677: deltaX = 0; ! 678: } ! 679: } ! 680: deltaX /= radX; ! 681: deltaX *= deltaX; ! 682: ! 683: /* ! 684: * Bottom side: ! 685: */ ! 686: ! 687: deltaY = (rectPtr[1] - centerY)/radY; ! 688: deltaY *= deltaY; ! 689: if ((deltaX + deltaY) < 1.0) { ! 690: return 0; ! 691: } ! 692: ! 693: /* ! 694: * Top side: ! 695: */ ! 696: ! 697: deltaY = (rectPtr[3] - centerY)/radY; ! 698: deltaY *= deltaY; ! 699: if ((deltaX + deltaY) < 1.0) { ! 700: return 0; ! 701: } ! 702: ! 703: return -1; ! 704: } ! 705: ! 706: /* ! 707: *-------------------------------------------------------------- ! 708: * ! 709: * TkIncludePoint -- ! 710: * ! 711: * Given a point and a generic canvas item header, expand ! 712: * the item's bounding box if needed to include the point. ! 713: * ! 714: * Results: ! 715: * None. ! 716: * ! 717: * Side effects: ! 718: * The boudn. ! 719: * ! 720: *-------------------------------------------------------------- ! 721: */ ! 722: ! 723: /* ARGSUSED */ ! 724: void ! 725: TkIncludePoint(canvasPtr, itemPtr, pointPtr) ! 726: Tk_Canvas *canvasPtr; /* Canvas containing item. */ ! 727: register Tk_Item *itemPtr; /* Item whose bounding box is ! 728: * being calculated. */ ! 729: double *pointPtr; /* Address of two doubles giving ! 730: * x and y coordinates of point. */ ! 731: { ! 732: int tmp; ! 733: ! 734: tmp = pointPtr[0] + 0.5; ! 735: if (tmp < itemPtr->x1) { ! 736: itemPtr->x1 = tmp; ! 737: } ! 738: if (tmp > itemPtr->x2) { ! 739: itemPtr->x2 = tmp; ! 740: } ! 741: tmp = pointPtr[1] + 0.5; ! 742: if (tmp < itemPtr->y1) { ! 743: itemPtr->y1 = tmp; ! 744: } ! 745: if (tmp > itemPtr->y2) { ! 746: itemPtr->y2 = tmp; ! 747: } ! 748: } ! 749: ! 750: /* ! 751: *-------------------------------------------------------------- ! 752: * ! 753: * TkBezierScreenPoints -- ! 754: * ! 755: * Given four control points, create a larger set of XPoints ! 756: * for a Bezier spline based on the points. ! 757: * ! 758: * Results: ! 759: * The array at *xPointPtr gets filled in with numSteps XPoints ! 760: * corresponding to the Bezier spline defined by the four ! 761: * control points. Note: no output point is generated for the ! 762: * first input point, but an output point *is* generated for ! 763: * the last input point. ! 764: * ! 765: * Side effects: ! 766: * None. ! 767: * ! 768: *-------------------------------------------------------------- ! 769: */ ! 770: ! 771: void ! 772: TkBezierScreenPoints(canvasPtr, control, numSteps, xPointPtr) ! 773: Tk_Canvas *canvasPtr; /* Canvas in which curve is to be ! 774: * drawn. */ ! 775: double control[]; /* Array of coordinates for four ! 776: * control points: x0, y0, x1, y1, ! 777: * ... x3 y3. */ ! 778: int numSteps; /* Number of curve points to ! 779: * generate. */ ! 780: register XPoint *xPointPtr; /* Where to put new points. */ ! 781: { ! 782: int i; ! 783: double u, u2, u3, t, t2, t3; ! 784: ! 785: for (i = 1; i <= numSteps; i++, xPointPtr++) { ! 786: t = ((double) i)/((double) numSteps); ! 787: t2 = t*t; ! 788: t3 = t2*t; ! 789: u = 1.0 - t; ! 790: u2 = u*u; ! 791: u3 = u2*u; ! 792: xPointPtr->x = SCREEN_X(canvasPtr, (control[0]*u3 ! 793: + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3)); ! 794: xPointPtr->y = SCREEN_Y(canvasPtr, (control[1]*u3 ! 795: + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3)); ! 796: } ! 797: } ! 798: ! 799: /* ! 800: *-------------------------------------------------------------- ! 801: * ! 802: * TkBezierPoints -- ! 803: * ! 804: * Given four control points, create a larger set of points ! 805: * for a Bezier spline based on the points. ! 806: * ! 807: * Results: ! 808: * The array at *coordPtr gets filled in with 2*numSteps ! 809: * coordinates, which correspond to the Bezier spline defined ! 810: * by the four control points. Note: no output point is ! 811: * generated for the first input point, but an output point ! 812: * *is* generated for the last input point. ! 813: * ! 814: * Side effects: ! 815: * None. ! 816: * ! 817: *-------------------------------------------------------------- ! 818: */ ! 819: ! 820: void ! 821: TkBezierPoints(control, numSteps, coordPtr) ! 822: double control[]; /* Array of coordinates for four ! 823: * control points: x0, y0, x1, y1, ! 824: * ... x3 y3. */ ! 825: int numSteps; /* Number of curve points to ! 826: * generate. */ ! 827: register double *coordPtr; /* Where to put new points. */ ! 828: { ! 829: int i; ! 830: double u, u2, u3, t, t2, t3; ! 831: ! 832: for (i = 1; i <= numSteps; i++, coordPtr += 2) { ! 833: t = ((double) i)/((double) numSteps); ! 834: t2 = t*t; ! 835: t3 = t2*t; ! 836: u = 1.0 - t; ! 837: u2 = u*u; ! 838: u3 = u2*u; ! 839: coordPtr[0] = control[0]*u3 ! 840: + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3; ! 841: coordPtr[1] = control[1]*u3 ! 842: + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3; ! 843: } ! 844: } ! 845: ! 846: /* ! 847: *-------------------------------------------------------------- ! 848: * ! 849: * TkMakeBezierCurve -- ! 850: * ! 851: * Given a set of points, create a new set of points that ! 852: * fit Bezier splines to the line segments connecting the ! 853: * original points. Produces output points in either of two ! 854: * forms. ! 855: * ! 856: * Results: ! 857: * Either or both of the xPoints or dblPoints arrays are filled ! 858: * in. The return value is the number of points placed in the ! 859: * arrays. Note: if the first and last points are the same, then ! 860: * a closed curve is generated. ! 861: * ! 862: * Side effects: ! 863: * None. ! 864: * ! 865: *-------------------------------------------------------------- ! 866: */ ! 867: ! 868: int ! 869: TkMakeBezierCurve(canvasPtr, pointPtr, numPoints, numSteps, xPoints, dblPoints) ! 870: Tk_Canvas *canvasPtr; /* Canvas in which curve is to be ! 871: * drawn. */ ! 872: double *pointPtr; /* Array of input coordinates: x0, ! 873: * y0, x1, y1, etc.. */ ! 874: int numPoints; /* Number of points at pointPtr. */ ! 875: int numSteps; /* Number of steps to use for each ! 876: * spline segments (determines ! 877: * smoothness of curve). */ ! 878: XPoint xPoints[]; /* Array of XPoints to fill in (e.g. ! 879: * for display. NULL means don't ! 880: * fill in any XPoints. */ ! 881: double dblPoints[]; /* Array of points to fill in as ! 882: * doubles, in the form x0, y0, ! 883: * x1, y1, .... NULL means don't ! 884: * fill in anything in this form. ! 885: * Caller must make sure that this ! 886: * array has enough space. */ ! 887: { ! 888: int closed, outputPoints, i; ! 889: int numCoords = numPoints*2; ! 890: double control[8]; ! 891: ! 892: /* ! 893: * If the curve is a closed one then generate a special spline ! 894: * that spans the last points and the first ones. Otherwise ! 895: * just put the first point into the output. ! 896: */ ! 897: ! 898: outputPoints = 0; ! 899: if ((pointPtr[0] == pointPtr[numCoords-2]) ! 900: && (pointPtr[1] == pointPtr[numCoords-1])) { ! 901: closed = 1; ! 902: control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0]; ! 903: control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1]; ! 904: control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0]; ! 905: control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1]; ! 906: control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2]; ! 907: control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3]; ! 908: control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; ! 909: control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; ! 910: if (xPoints != NULL) { ! 911: xPoints->x = SCREEN_X(canvasPtr, control[0]); ! 912: xPoints->y = SCREEN_Y(canvasPtr, control[1]); ! 913: TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints+1); ! 914: xPoints += numSteps+1; ! 915: } ! 916: if (dblPoints != NULL) { ! 917: dblPoints[0] = control[0]; ! 918: dblPoints[1] = control[1]; ! 919: TkBezierPoints(control, numSteps, dblPoints+2); ! 920: dblPoints += 2*(numSteps+1); ! 921: } ! 922: outputPoints += numSteps+1; ! 923: } else { ! 924: closed = 0; ! 925: if (xPoints != NULL) { ! 926: xPoints->x = SCREEN_X(canvasPtr, pointPtr[0]); ! 927: xPoints->y = SCREEN_Y(canvasPtr, pointPtr[1]); ! 928: xPoints += 1; ! 929: } ! 930: if (dblPoints != NULL) { ! 931: dblPoints[0] = pointPtr[0]; ! 932: dblPoints[1] = pointPtr[1]; ! 933: dblPoints += 2; ! 934: } ! 935: outputPoints += 1; ! 936: } ! 937: ! 938: for (i = 2; i < numPoints; i++, pointPtr += 2) { ! 939: /* ! 940: * Set up the first two control points. This is done ! 941: * differently for the first spline of an open curve ! 942: * than for other cases. ! 943: */ ! 944: ! 945: if ((i == 2) && !closed) { ! 946: control[0] = pointPtr[0]; ! 947: control[1] = pointPtr[1]; ! 948: control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2]; ! 949: control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3]; ! 950: } else { ! 951: control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; ! 952: control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; ! 953: control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2]; ! 954: control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3]; ! 955: } ! 956: ! 957: /* ! 958: * Set up the last two control points. This is done ! 959: * differently for the last spline of an open curve ! 960: * than for other cases. ! 961: */ ! 962: ! 963: if ((i == (numPoints-1)) && !closed) { ! 964: control[4] = .667*pointPtr[2] + .333*pointPtr[4]; ! 965: control[5] = .667*pointPtr[3] + .333*pointPtr[5]; ! 966: control[6] = pointPtr[4]; ! 967: control[7] = pointPtr[5]; ! 968: } else { ! 969: control[4] = .833*pointPtr[2] + .167*pointPtr[4]; ! 970: control[5] = .833*pointPtr[3] + .167*pointPtr[5]; ! 971: control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4]; ! 972: control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5]; ! 973: } ! 974: ! 975: /* ! 976: * If the first two points coincide, or if the last ! 977: * two points coincide, then generate a single ! 978: * straight-line segment by outputting the last control ! 979: * point. ! 980: */ ! 981: ! 982: if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3])) ! 983: || ((pointPtr[2] == pointPtr[4]) ! 984: && (pointPtr[3] == pointPtr[5]))) { ! 985: if (xPoints != NULL) { ! 986: xPoints[0].x = SCREEN_X(canvasPtr, control[6]); ! 987: xPoints[0].y = SCREEN_Y(canvasPtr, control[7]); ! 988: xPoints++; ! 989: } ! 990: if (dblPoints != NULL) { ! 991: dblPoints[0] = control[6]; ! 992: dblPoints[1] = control[7]; ! 993: dblPoints += 2; ! 994: } ! 995: outputPoints += 1; ! 996: continue; ! 997: } ! 998: ! 999: /* ! 1000: * Generate a Bezier spline using the control points. ! 1001: */ ! 1002: ! 1003: ! 1004: if (xPoints != NULL) { ! 1005: TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints); ! 1006: xPoints += numSteps; ! 1007: } ! 1008: if (dblPoints != NULL) { ! 1009: TkBezierPoints(control, numSteps, dblPoints); ! 1010: dblPoints += 2*numSteps; ! 1011: } ! 1012: outputPoints += numSteps; ! 1013: } ! 1014: return outputPoints; ! 1015: } ! 1016: ! 1017: /* ! 1018: *-------------------------------------------------------------- ! 1019: * ! 1020: * TkGetMiterPoints -- ! 1021: * ! 1022: * Given three points forming an angle, compute the ! 1023: * coordinates of the inside and outside points of ! 1024: * the mitered corner formed by a line of a given ! 1025: * width at that angle. ! 1026: * ! 1027: * Results: ! 1028: * If the angle formed by the three points is less than ! 1029: * 11 degrees then 0 is returned and m1 and m2 aren't ! 1030: * modified. Otherwise 1 is returned and the points at ! 1031: * m1 and m2 are filled in with the positions of the points ! 1032: * of the mitered corner. ! 1033: * ! 1034: * Side effects: ! 1035: * None. ! 1036: * ! 1037: *-------------------------------------------------------------- ! 1038: */ ! 1039: ! 1040: int ! 1041: TkGetMiterPoints(p1, p2, p3, width, m1, m2) ! 1042: double p1[]; /* Points to x- and y-coordinates of point ! 1043: * before vertex. */ ! 1044: double p2[]; /* Points to x- and y-coordinates of vertex ! 1045: * for mitered joint. */ ! 1046: double p3[]; /* Points to x- and y-coordinates of point ! 1047: * after vertex. */ ! 1048: double width; /* Width of line. */ ! 1049: double m1[]; /* Points to place to put "left" vertex ! 1050: * point (see as you face from p1 to p2). */ ! 1051: double m2[]; /* Points to place to put "right" vertex ! 1052: * point. */ ! 1053: { ! 1054: double theta1; /* Angle of segment p2-p1. */ ! 1055: double theta2; /* Angle of segment p2-p3. */ ! 1056: double theta; /* Angle between line segments (angle ! 1057: * of joint). */ ! 1058: double theta3; /* Angle that bisects theta1 and ! 1059: * theta2 and points to m1. */ ! 1060: double dist; /* Distance of miter points from p2. */ ! 1061: double deltaX, deltaY; /* X and y offsets cooresponding to ! 1062: * dist (fudge factors for bounding ! 1063: * box). */ ! 1064: static float elevenDegrees = (11.0*2.0*PI)/360.0; ! 1065: ! 1066: if (p2[1] == p1[1]) { ! 1067: theta1 = (p2[0] < p1[0]) ? 0 : PI; ! 1068: } else if (p2[0] == p1[0]) { ! 1069: theta1 = (p2[1] < p1[1]) ? PI/2.0 : -PI/2.0; ! 1070: } else { ! 1071: theta1 = atan2(p1[1] - p2[1], p1[0] - p2[0]); ! 1072: } ! 1073: if (p3[1] == p2[1]) { ! 1074: theta2 = (p3[0] > p2[0]) ? 0 : PI; ! 1075: } else if (p3[0] == p2[0]) { ! 1076: theta2 = (p3[1] > p2[1]) ? PI/2.0 : -PI/2.0; ! 1077: } else { ! 1078: theta2 = atan2(p3[1] - p2[1], p3[0] - p2[0]); ! 1079: } ! 1080: theta = theta1 - theta2; ! 1081: if (theta > PI) { ! 1082: theta -= 2*PI; ! 1083: } else if (theta < -PI) { ! 1084: theta += 2*PI; ! 1085: } ! 1086: if ((theta < elevenDegrees) && (theta > -elevenDegrees)) { ! 1087: return 0; ! 1088: } ! 1089: dist = 0.5*width/sin(0.5*theta); ! 1090: if (dist < 0.0) { ! 1091: dist = -dist; ! 1092: } ! 1093: ! 1094: /* ! 1095: * Compute theta3 (make sure that it points to the left when ! 1096: * looking from p1 to p2). ! 1097: */ ! 1098: ! 1099: theta3 = (theta1 + theta2)/2.0; ! 1100: if (sin(theta3 - (theta1 + PI)) < 0.0) { ! 1101: theta3 += PI; ! 1102: } ! 1103: deltaX = dist*cos(theta3); ! 1104: m1[0] = p2[0] + deltaX; ! 1105: m2[0] = p2[0] - deltaX; ! 1106: deltaY = dist*sin(theta3); ! 1107: m1[1] = p2[1] + deltaY; ! 1108: m2[1] = p2[1] - deltaY; ! 1109: return 1; ! 1110: } ! 1111: ! 1112: /* ! 1113: *-------------------------------------------------------------- ! 1114: * ! 1115: * TkGetButtPoints -- ! 1116: * ! 1117: * Given two points forming a line segment, compute the ! 1118: * coordinates of two endpoints of a rectangle formed by ! 1119: * bloating the line segment until it is width units wide. ! 1120: * ! 1121: * Results: ! 1122: * There is no return value. M1 and m2 are filled in to ! 1123: * correspond to m1 and m2 in the diagram below: ! 1124: * ! 1125: * ----------------* m1 ! 1126: * | ! 1127: * p1 *---------------* p2 ! 1128: * | ! 1129: * ----------------* m2 ! 1130: * ! 1131: * M1 and m2 will be W units apart, with p2 centered between ! 1132: * them and m1-m2 perpendicular to p1-p2. However, if ! 1133: * "project" is true then m1 and m2 will be as follows: ! 1134: * ! 1135: * -------------------* m1 ! 1136: * p2 | ! 1137: * p1 *---------------* | ! 1138: * | ! 1139: * -------------------* m2 ! 1140: * ! 1141: * In this case p2 will be width/2 units from the segment m1-m2. ! 1142: * ! 1143: * Side effects: ! 1144: * None. ! 1145: * ! 1146: *-------------------------------------------------------------- ! 1147: */ ! 1148: ! 1149: void ! 1150: TkGetButtPoints(p1, p2, width, project, m1, m2) ! 1151: double p1[]; /* Points to x- and y-coordinates of point ! 1152: * before vertex. */ ! 1153: double p2[]; /* Points to x- and y-coordinates of vertex ! 1154: * for mitered joint. */ ! 1155: double width; /* Width of line. */ ! 1156: int project; /* Non-zero means project p2 by an additional ! 1157: * width/2 before computing m1 and m2. */ ! 1158: double m1[]; /* Points to place to put "left" result ! 1159: * point, as you face from p1 to p2. */ ! 1160: double m2[]; /* Points to place to put "right" result ! 1161: * point. */ ! 1162: { ! 1163: double length; /* Length of p1-p2 segment. */ ! 1164: double deltaX, deltaY; /* Increments in coords. */ ! 1165: ! 1166: width *= 0.5; ! 1167: length = hypot(p2[0] - p1[0], p2[1] - p1[1]); ! 1168: if (length == 0.0) { ! 1169: m1[0] = m2[0] = p2[0]; ! 1170: m1[1] = m2[1] = p2[1]; ! 1171: } else { ! 1172: deltaX = -width * (p2[1] - p1[1]) / length; ! 1173: deltaY = width * (p2[0] - p1[0]) / length; ! 1174: m1[0] = p2[0] + deltaX; ! 1175: m2[0] = p2[0] - deltaX; ! 1176: m1[1] = p2[1] + deltaY; ! 1177: m2[1] = p2[1] - deltaY; ! 1178: if (project) { ! 1179: m1[0] += deltaY; ! 1180: m2[0] += deltaY; ! 1181: m1[1] -= deltaX; ! 1182: m2[1] -= deltaX; ! 1183: } ! 1184: } ! 1185: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.