tk/generic/tkTrig.c

   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 (c) 1992-1994 The Regents of the University of California.
  10  * Copyright (c) 1994-1997 Sun Microsystems, Inc.
  11  *
  12  * See the file "license.terms" for information on usage and redistribution
  13  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  14  *
  15  * RCS: @(#) $Id$
  16  */
  17
  18 #include <stdio.h>
  19 #include "tkInt.h"
  20 #include "tkPort.h"
  21 #include "tkCanvas.h"
  22
  23 #undef MIN
  24 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
  25 #undef MAX
  26 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
  27 #ifndef PI
  28 #   define PI 3.14159265358979323846
  29 #endif /* PI */
  30 \f
  31 /*
  32  *--------------------------------------------------------------
  33  *
  34  * TkLineToPoint --
  35  *
  36  *      Compute the distance from a point to a finite line segment.
  37  *
  38  * Results:
  39  *      The return value is the distance from the line segment
  40  *      whose end-points are *end1Ptr and *end2Ptr to the point
  41  *      given by *pointPtr.
  42  *
  43  * Side effects:
  44  *      None.
  45  *
  46  *--------------------------------------------------------------
  47  */
  48
  49 double
  50 TkLineToPoint(end1Ptr, end2Ptr, pointPtr)
  51     double end1Ptr[2];          /* Coordinates of first end-point of line. */
  52     double end2Ptr[2];          /* Coordinates of second end-point of line. */
  53     double pointPtr[2];         /* Points to coords for point. */
  54 {
  55     double x, y;
  56
  57     /*
  58      * Compute the point on the line that is closest to the
  59      * point.  This must be done separately for vertical edges,
  60      * horizontal edges, and other edges.
  61      */
  62
  63     if (end1Ptr[0] == end2Ptr[0]) {
  64
  65         /*
  66          * Vertical edge.
  67          */
  68
  69         x = end1Ptr[0];
  70         if (end1Ptr[1] >= end2Ptr[1]) {
  71             y = MIN(end1Ptr[1], pointPtr[1]);
  72             y = MAX(y, end2Ptr[1]);
  73         } else {
  74             y = MIN(end2Ptr[1], pointPtr[1]);
  75             y = MAX(y, end1Ptr[1]);
  76         }
  77     } else if (end1Ptr[1] == end2Ptr[1]) {
  78
  79         /*
  80          * Horizontal edge.
  81          */
  82
  83         y = end1Ptr[1];
  84         if (end1Ptr[0] >= end2Ptr[0]) {
  85             x = MIN(end1Ptr[0], pointPtr[0]);
  86             x = MAX(x, end2Ptr[0]);
  87         } else {
  88             x = MIN(end2Ptr[0], pointPtr[0]);
  89             x = MAX(x, end1Ptr[0]);
  90         }
  91     } else {
  92         double m1, b1, m2, b2;
  93
  94         /*
  95          * The edge is neither horizontal nor vertical.  Convert the
  96          * edge to a line equation of the form y = m1*x + b1.  Then
  97          * compute a line perpendicular to this edge but passing
  98          * through the point, also in the form y = m2*x + b2.
  99          */
 100
 101         m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
 102         b1 = end1Ptr[1] - m1*end1Ptr[0];
 103         m2 = -1.0/m1;
 104         b2 = pointPtr[1] - m2*pointPtr[0];
 105         x = (b2 - b1)/(m1 - m2);
 106         y = m1*x + b1;
 107         if (end1Ptr[0] > end2Ptr[0]) {
 108             if (x > end1Ptr[0]) {
 109                 x = end1Ptr[0];
 110                 y = end1Ptr[1];
 111             } else if (x < end2Ptr[0]) {
 112                 x = end2Ptr[0];
 113                 y = end2Ptr[1];
 114             }
 115         } else {
 116             if (x > end2Ptr[0]) {
 117                 x = end2Ptr[0];
 118                 y = end2Ptr[1];
 119             } else if (x < end1Ptr[0]) {
 120                 x = end1Ptr[0];
 121                 y = end1Ptr[1];
 122             }
 123         }
 124     }
 125
 126     /*
 127      * Compute the distance to the closest point.
 128      */
 129
 130     return hypot(pointPtr[0] - x, pointPtr[1] - y);
 131 }
 132 \f
 133 /*
 134  *--------------------------------------------------------------
 135  *
 136  * TkLineToArea --
 137  *
 138  *      Determine whether a line lies entirely inside, entirely
 139  *      outside, or overlapping a given rectangular area.
 140  *
 141  * Results:
 142  *      -1 is returned if the line given by end1Ptr and end2Ptr
 143  *      is entirely outside the rectangle given by rectPtr.  0 is
 144  *      returned if the polygon overlaps the rectangle, and 1 is
 145  *      returned if the polygon is entirely inside the rectangle.
 146  *
 147  * Side effects:
 148  *      None.
 149  *
 150  *--------------------------------------------------------------
 151  */
 152
 153 int
 154 TkLineToArea(end1Ptr, end2Ptr, rectPtr)
 155     double end1Ptr[2];          /* X and y coordinates for one endpoint
 156                                  * of line. */
 157     double end2Ptr[2];          /* X and y coordinates for other endpoint
 158                                  * of line. */
 159     double rectPtr[4];          /* Points to coords for rectangle, in the
 160                                  * order x1, y1, x2, y2.  X1 must be no
 161                                  * larger than x2, and y1 no larger than y2. */
 162 {
 163     int inside1, inside2;
 164
 165     /*
 166      * First check the two points individually to see whether they
 167      * are inside the rectangle or not.
 168      */
 169
 170     inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2])
 171             && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]);
 172     inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2])
 173             && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]);
 174     if (inside1 != inside2) {
 175         return 0;
 176     }
 177     if (inside1 & inside2) {
 178         return 1;
 179     }
 180
 181     /*
 182      * Both points are outside the rectangle, but still need to check
 183      * for intersections between the line and the rectangle.  Horizontal
 184      * and vertical lines are particularly easy, so handle them
 185      * separately.
 186      */
 187
 188     if (end1Ptr[0] == end2Ptr[0]) {
 189         /*
 190          * Vertical line.
 191          */
 192
 193         if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1]))
 194                 && (end1Ptr[0] >= rectPtr[0])
 195                 && (end1Ptr[0] <= rectPtr[2])) {
 196             return 0;
 197         }
 198     } else if (end1Ptr[1] == end2Ptr[1]) {
 199         /*
 200          * Horizontal line.
 201          */
 202
 203         if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0]))
 204                 && (end1Ptr[1] >= rectPtr[1])
 205                 && (end1Ptr[1] <= rectPtr[3])) {
 206             return 0;
 207         }
 208     } else {
 209         double m, x, y, low, high;
 210
 211         /*
 212          * Diagonal line.  Compute slope of line and use
 213          * for intersection checks against each of the
 214          * sides of the rectangle: left, right, bottom, top.
 215          */
 216
 217         m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
 218         if (end1Ptr[0] < end2Ptr[0]) {
 219             low = end1Ptr[0];  high = end2Ptr[0];
 220         } else {
 221             low = end2Ptr[0]; high = end1Ptr[0];
 222         }
 223
 224         /*
 225          * Left edge.
 226          */
 227
 228         y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m;
 229         if ((rectPtr[0] >= low) && (rectPtr[0] <= high)
 230                 && (y >= rectPtr[1]) && (y <= rectPtr[3])) {
 231             return 0;
 232         }
 233
 234         /*
 235          * Right edge.
 236          */
 237
 238         y += (rectPtr[2] - rectPtr[0])*m;
 239         if ((y >= rectPtr[1]) && (y <= rectPtr[3])
 240                 && (rectPtr[2] >= low) && (rectPtr[2] <= high)) {
 241             return 0;
 242         }
 243
 244         /*
 245          * Bottom edge.
 246          */
 247
 248         if (end1Ptr[1] < end2Ptr[1]) {
 249             low = end1Ptr[1];  high = end2Ptr[1];
 250         } else {
 251             low = end2Ptr[1]; high = end1Ptr[1];
 252         }
 253         x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m;
 254         if ((x >= rectPtr[0]) && (x <= rectPtr[2])
 255                 && (rectPtr[1] >= low) && (rectPtr[1] <= high)) {
 256             return 0;
 257         }
 258
 259         /*
 260          * Top edge.
 261          */
 262
 263         x += (rectPtr[3] - rectPtr[1])/m;
 264         if ((x >= rectPtr[0]) && (x <= rectPtr[2])
 265                 && (rectPtr[3] >= low) && (rectPtr[3] <= high)) {
 266             return 0;
 267         }
 268     }
 269     return -1;
 270 }
 271 \f
 272 /*
 273  *--------------------------------------------------------------
 274  *
 275  * TkThickPolyLineToArea --
 276  *
 277  *      This procedure is called to determine whether a connected
 278  *      series of line segments lies entirely inside, entirely
 279  *      outside, or overlapping a given rectangular area.
 280  *
 281  * Results:
 282  *      -1 is returned if the lines are entirely outside the area,
 283  *      0 if they overlap, and 1 if they are entirely inside the
 284  *      given area.
 285  *
 286  * Side effects:
 287  *      None.
 288  *
 289  *--------------------------------------------------------------
 290  */
 291
 292         /* ARGSUSED */
 293 int
 294 TkThickPolyLineToArea(coordPtr, numPoints, width, capStyle, joinStyle, rectPtr)
 295     double *coordPtr;           /* Points to an array of coordinates for
 296                                  * the polyline:  x0, y0, x1, y1, ... */
 297     int numPoints;              /* Total number of points at *coordPtr. */
 298     double width;               /* Width of each line segment. */
 299     int capStyle;               /* How are end-points of polyline drawn?
 300                                  * CapRound, CapButt, or CapProjecting. */
 301     int joinStyle;              /* How are joints in polyline drawn?
 302                                  * JoinMiter, JoinRound, or JoinBevel. */
 303     double *rectPtr;            /* Rectangular area to check against. */
 304 {
 305     double radius, poly[10];
 306     int count;
 307     int changedMiterToBevel;    /* Non-zero means that a mitered corner
 308                                  * had to be treated as beveled after all
 309                                  * because the angle was < 11 degrees. */
 310     int inside;                 /* Tentative guess about what to return,
 311                                  * based on all points seen so far:  one
 312                                  * means everything seen so far was
 313                                  * inside the area;  -1 means everything
 314                                  * was outside the area.  0 means overlap
 315                                  * has been found. */
 316
 317     radius = width/2.0;
 318     inside = -1;
 319
 320     if ((coordPtr[0] >= rectPtr[0]) && (coordPtr[0] <= rectPtr[2])
 321             && (coordPtr[1] >= rectPtr[1]) && (coordPtr[1] <= rectPtr[3])) {
 322         inside = 1;
 323     }
 324
 325     /*
 326      * Iterate through all of the edges of the line, computing a polygon
 327      * for each edge and testing the area against that polygon.  In
 328      * addition, there are additional tests to deal with rounded joints
 329      * and caps.
 330      */
 331
 332     changedMiterToBevel = 0;
 333     for (count = numPoints; count >= 2; count--, coordPtr += 2) {
 334
 335         /*
 336          * If rounding is done around the first point of the edge
 337          * then test a circular region around the point with the
 338          * area.
 339          */
 340
 341         if (((capStyle == CapRound) && (count == numPoints))
 342                 || ((joinStyle == JoinRound) && (count != numPoints))) {
 343             poly[0] = coordPtr[0] - radius;
 344             poly[1] = coordPtr[1] - radius;
 345             poly[2] = coordPtr[0] + radius;
 346             poly[3] = coordPtr[1] + radius;
 347             if (TkOvalToArea(poly, rectPtr) != inside) {
 348                 return 0;
 349             }
 350         }
 351
 352         /*
 353          * Compute the polygonal shape corresponding to this edge,
 354          * consisting of two points for the first point of the edge
 355          * and two points for the last point of the edge.
 356          */
 357
 358         if (count == numPoints) {
 359             TkGetButtPoints(coordPtr+2, coordPtr, width,
 360                     capStyle == CapProjecting, poly, poly+2);
 361         } else if ((joinStyle == JoinMiter) && !changedMiterToBevel) {
 362             poly[0] = poly[6];
 363             poly[1] = poly[7];
 364             poly[2] = poly[4];
 365             poly[3] = poly[5];
 366         } else {
 367             TkGetButtPoints(coordPtr+2, coordPtr, width, 0, poly, poly+2);
 368
 369             /*
 370              * If the last joint was beveled, then also check a
 371              * polygon comprising the last two points of the previous
 372              * polygon and the first two from this polygon;  this checks
 373              * the wedges that fill the beveled joint.
 374              */
 375
 376             if ((joinStyle == JoinBevel) || changedMiterToBevel) {
 377                 poly[8] = poly[0];
 378                 poly[9] = poly[1];
 379                 if (TkPolygonToArea(poly, 5, rectPtr) != inside) {
 380                     return 0;
 381                 }
 382                 changedMiterToBevel = 0;
 383             }
 384         }
 385         if (count == 2) {
 386             TkGetButtPoints(coordPtr, coordPtr+2, width,
 387                     capStyle == CapProjecting, poly+4, poly+6);
 388         } else if (joinStyle == JoinMiter) {
 389             if (TkGetMiterPoints(coordPtr, coordPtr+2, coordPtr+4,
 390                     (double) width, poly+4, poly+6) == 0) {
 391                 changedMiterToBevel = 1;
 392                 TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4,
 393                         poly+6);
 394             }
 395         } else {
 396             TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4, poly+6);
 397         }
 398         poly[8] = poly[0];
 399         poly[9] = poly[1];
 400         if (TkPolygonToArea(poly, 5, rectPtr) != inside) {
 401             return 0;
 402         }
 403     }
 404
 405     /*
 406      * If caps are rounded, check the cap around the final point
 407      * of the line.
 408      */
 409
 410     if (capStyle == CapRound) {
 411         poly[0] = coordPtr[0] - radius;
 412         poly[1] = coordPtr[1] - radius;
 413         poly[2] = coordPtr[0] + radius;
 414         poly[3] = coordPtr[1] + radius;
 415         if (TkOvalToArea(poly, rectPtr) != inside) {
 416             return 0;
 417         }
 418     }
 419
 420     return inside;
 421 }
 422 \f
 423 /*
 424  *--------------------------------------------------------------
 425  *
 426  * TkPolygonToPoint --
 427  *
 428  *      Compute the distance from a point to a polygon.
 429  *
 430  * Results:
 431  *      The return value is 0.0 if the point referred to by
 432  *      pointPtr is within the polygon referred to by polyPtr
 433  *      and numPoints.  Otherwise the return value is the
 434  *      distance of the point from the polygon.
 435  *
 436  * Side effects:
 437  *      None.
 438  *
 439  *--------------------------------------------------------------
 440  */
 441
 442 double
 443 TkPolygonToPoint(polyPtr, numPoints, pointPtr)
 444     double *polyPtr;            /* Points to an array coordinates for
 445                                  * closed polygon:  x0, y0, x1, y1, ...
 446                                  * The polygon may be self-intersecting. */
 447     int numPoints;              /* Total number of points at *polyPtr. */
 448     double *pointPtr;           /* Points to coords for point. */
 449 {
 450     double bestDist;            /* Closest distance between point and
 451                                  * any edge in polygon. */
 452     int intersections;          /* Number of edges in the polygon that
 453                                  * intersect a ray extending vertically
 454                                  * upwards from the point to infinity. */
 455     int count;
 456     register double *pPtr;
 457
 458     /*
 459      * Iterate through all of the edges in the polygon, updating
 460      * bestDist and intersections.
 461      *
 462      * TRICKY POINT:  when computing intersections, include left
 463      * x-coordinate of line within its range, but not y-coordinate.
 464      * Otherwise if the point lies exactly below a vertex we'll
 465      * count it as two intersections.
 466      */
 467
 468     bestDist = 1.0e36;
 469     intersections = 0;
 470
 471     for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) {
 472         double x, y, dist;
 473
 474         /*
 475          * Compute the point on the current edge closest to the point
 476          * and update the intersection count.  This must be done
 477          * separately for vertical edges, horizontal edges, and
 478          * other edges.
 479          */
 480
 481         if (pPtr[2] == pPtr[0]) {
 482
 483             /*
 484              * Vertical edge.
 485              */
 486
 487             x = pPtr[0];
 488             if (pPtr[1] >= pPtr[3]) {
 489                 y = MIN(pPtr[1], pointPtr[1]);
 490                 y = MAX(y, pPtr[3]);
 491             } else {
 492                 y = MIN(pPtr[3], pointPtr[1]);
 493                 y = MAX(y, pPtr[1]);
 494             }
 495         } else if (pPtr[3] == pPtr[1]) {
 496
 497             /*
 498              * Horizontal edge.
 499              */
 500
 501             y = pPtr[1];
 502             if (pPtr[0] >= pPtr[2]) {
 503                 x = MIN(pPtr[0], pointPtr[0]);
 504                 x = MAX(x, pPtr[2]);
 505                 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0])
 506                         && (pointPtr[0] >= pPtr[2])) {
 507                     intersections++;
 508                 }
 509             } else {
 510                 x = MIN(pPtr[2], pointPtr[0]);
 511                 x = MAX(x, pPtr[0]);
 512                 if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2])
 513                         && (pointPtr[0] >= pPtr[0])) {
 514                     intersections++;
 515                 }
 516             }
 517         } else {
 518             double m1, b1, m2, b2;
 519             int lower;                  /* Non-zero means point below line. */
 520
 521             /*
 522              * The edge is neither horizontal nor vertical.  Convert the
 523              * edge to a line equation of the form y = m1*x + b1.  Then
 524              * compute a line perpendicular to this edge but passing
 525              * through the point, also in the form y = m2*x + b2.
 526              */
 527
 528             m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]);
 529             b1 = pPtr[1] - m1*pPtr[0];
 530             m2 = -1.0/m1;
 531             b2 = pointPtr[1] - m2*pointPtr[0];
 532             x = (b2 - b1)/(m1 - m2);
 533             y = m1*x + b1;
 534             if (pPtr[0] > pPtr[2]) {
 535                 if (x > pPtr[0]) {
 536                     x = pPtr[0];
 537                     y = pPtr[1];
 538                 } else if (x < pPtr[2]) {
 539                     x = pPtr[2];
 540                     y = pPtr[3];
 541                 }
 542             } else {
 543                 if (x > pPtr[2]) {
 544                     x = pPtr[2];
 545                     y = pPtr[3];
 546                 } else if (x < pPtr[0]) {
 547                     x = pPtr[0];
 548                     y = pPtr[1];
 549                 }
 550             }
 551             lower = (m1*pointPtr[0] + b1) > pointPtr[1];
 552             if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2]))
 553                     && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) {
 554                 intersections++;
 555             }
 556         }
 557
 558         /*
 559          * Compute the distance to the closest point, and see if that
 560          * is the best distance seen so far.
 561          */
 562
 563         dist = hypot(pointPtr[0] - x, pointPtr[1] - y);
 564         if (dist < bestDist) {
 565             bestDist = dist;
 566         }
 567     }
 568
 569     /*
 570      * We've processed all of the points.  If the number of intersections
 571      * is odd, the point is inside the polygon.
 572      */
 573
 574     if (intersections & 0x1) {
 575         return 0.0;
 576     }
 577     return bestDist;
 578 }
 579 \f
 580 /*
 581  *--------------------------------------------------------------
 582  *
 583  * TkPolygonToArea --
 584  *
 585  *      Determine whether a polygon lies entirely inside, entirely
 586  *      outside, or overlapping a given rectangular area.
 587  *
 588  * Results:
 589  *      -1 is returned if the polygon given by polyPtr and numPoints
 590  *      is entirely outside the rectangle given by rectPtr.  0 is
 591  *      returned if the polygon overlaps the rectangle, and 1 is
 592  *      returned if the polygon is entirely inside the rectangle.
 593  *
 594  * Side effects:
 595  *      None.
 596  *
 597  *--------------------------------------------------------------
 598  */
 599
 600 int
 601 TkPolygonToArea(polyPtr, numPoints, rectPtr)
 602     double *polyPtr;            /* Points to an array coordinates for
 603                                  * closed polygon:  x0, y0, x1, y1, ...
 604                                  * The polygon may be self-intersecting. */
 605     int numPoints;              /* Total number of points at *polyPtr. */
 606     register double *rectPtr;   /* Points to coords for rectangle, in the
 607                                  * order x1, y1, x2, y2.  X1 and y1 must
 608                                  * be lower-left corner. */
 609 {
 610     int state;                  /* State of all edges seen so far (-1 means
 611                                  * outside, 1 means inside, won't ever be
 612                                  * 0). */
 613     int count;
 614     register double *pPtr;
 615
 616     /*
 617      * Iterate over all of the edges of the polygon and test them
 618      * against the rectangle.  Can quit as soon as the state becomes
 619      * "intersecting".
 620      */
 621
 622     state = TkLineToArea(polyPtr, polyPtr+2, rectPtr);
 623     if (state == 0) {
 624         return 0;
 625     }
 626     for (pPtr = polyPtr+2, count = numPoints-1; count >= 2;
 627             pPtr += 2, count--) {
 628         if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) {
 629             return 0;
 630         }
 631     }
 632
 633     /*
 634      * If all of the edges were inside the rectangle we're done.
 635      * If all of the edges were outside, then the rectangle could
 636      * still intersect the polygon (if it's entirely enclosed).
 637      * Call TkPolygonToPoint to figure this out.
 638      */
 639
 640     if (state == 1) {
 641         return 1;
 642     }
 643     if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) {
 644         return 0;
 645     }
 646     return -1;
 647 }
 648 \f
 649 /*
 650  *--------------------------------------------------------------
 651  *
 652  * TkOvalToPoint --
 653  *
 654  *      Computes the distance from a given point to a given
 655  *      oval, in canvas units.
 656  *
 657  * Results:
 658  *      The return value is 0 if the point given by *pointPtr is
 659  *      inside the oval.  If the point isn't inside the
 660  *      oval then the return value is approximately the distance
 661  *      from the point to the oval.  If the oval is filled, then
 662  *      anywhere in the interior is considered "inside";  if
 663  *      the oval isn't filled, then "inside" means only the area
 664  *      occupied by the outline.
 665  *
 666  * Side effects:
 667  *      None.
 668  *
 669  *--------------------------------------------------------------
 670  */
 671
 672         /* ARGSUSED */
 673 double
 674 TkOvalToPoint(ovalPtr, width, filled, pointPtr)
 675     double ovalPtr[4];          /* Pointer to array of four coordinates
 676                                  * (x1, y1, x2, y2) defining oval's bounding
 677                                  * box. */
 678     double width;               /* Width of outline for oval. */
 679     int filled;                 /* Non-zero means oval should be treated as
 680                                  * filled;  zero means only consider outline. */
 681     double pointPtr[2];         /* Coordinates of point. */
 682 {
 683     double xDelta, yDelta, scaledDistance, distToOutline, distToCenter;
 684     double xDiam, yDiam;
 685
 686     /*
 687      * Compute the distance between the center of the oval and the
 688      * point in question, using a coordinate system where the oval
 689      * has been transformed to a circle with unit radius.
 690      */
 691
 692     xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0);
 693     yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0);
 694     distToCenter = hypot(xDelta, yDelta);
 695     scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0),
 696             yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0));
 697
 698
 699     /*
 700      * If the scaled distance is greater than 1 then it means no
 701      * hit.  Compute the distance from the point to the edge of
 702      * the circle, then scale this distance back to the original
 703      * coordinate system.
 704      *
 705      * Note: this distance isn't completely accurate.  It's only
 706      * an approximation, and it can overestimate the correct
 707      * distance when the oval is eccentric.
 708      */
 709
 710     if (scaledDistance > 1.0) {
 711         return (distToCenter/scaledDistance) * (scaledDistance - 1.0);
 712     }
 713
 714     /*
 715      * Scaled distance less than 1 means the point is inside the
 716      * outer edge of the oval.  If this is a filled oval, then we
 717      * have a hit.  Otherwise, do the same computation as above
 718      * (scale back to original coordinate system), but also check
 719      * to see if the point is within the width of the outline.
 720      */
 721
 722     if (filled) {
 723         return 0.0;
 724     }
 725     if (scaledDistance > 1E-10) {
 726         distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance)
 727                 - width;
 728     } else {
 729         /*
 730          * Avoid dividing by a very small number (it could cause an
 731          * arithmetic overflow).  This problem occurs if the point is
 732          * very close to the center of the oval.
 733          */
 734
 735         xDiam = ovalPtr[2] - ovalPtr[0];
 736         yDiam = ovalPtr[3] - ovalPtr[1];
 737         if (xDiam < yDiam) {
 738             distToOutline = (xDiam - width)/2;
 739         } else {
 740             distToOutline = (yDiam - width)/2;
 741         }
 742     }
 743
 744     if (distToOutline < 0.0) {
 745         return 0.0;
 746     }
 747     return distToOutline;
 748 }
 749 \f
 750 /*
 751  *--------------------------------------------------------------
 752  *
 753  * TkOvalToArea --
 754  *
 755  *      Determine whether an oval lies entirely inside, entirely
 756  *      outside, or overlapping a given rectangular area.
 757  *
 758  * Results:
 759  *      -1 is returned if the oval described by ovalPtr is entirely
 760  *      outside the rectangle given by rectPtr.  0 is returned if the
 761  *      oval overlaps the rectangle, and 1 is returned if the oval
 762  *      is entirely inside the rectangle.
 763  *
 764  * Side effects:
 765  *      None.
 766  *
 767  *--------------------------------------------------------------
 768  */
 769
 770 int
 771 TkOvalToArea(ovalPtr, rectPtr)
 772     register double *ovalPtr;   /* Points to coordinates definining the
 773                                  * bounding rectangle for the oval: x1, y1,
 774                                  * x2, y2.  X1 must be less than x2 and y1
 775                                  * less than y2. */
 776     register double *rectPtr;   /* Points to coords for rectangle, in the
 777                                  * order x1, y1, x2, y2.  X1 and y1 must
 778                                  * be lower-left corner. */
 779 {
 780     double centerX, centerY, radX, radY, deltaX, deltaY;
 781
 782     /*
 783      * First, see if oval is entirely inside rectangle or entirely
 784      * outside rectangle.
 785      */
 786
 787     if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2])
 788             && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) {
 789         return 1;
 790     }
 791     if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2])
 792             || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) {
 793         return -1;
 794     }
 795
 796     /*
 797      * Next, go through the rectangle side by side.  For each side
 798      * of the rectangle, find the point on the side that is closest
 799      * to the oval's center, and see if that point is inside the
 800      * oval.  If at least one such point is inside the oval, then
 801      * the rectangle intersects the oval.
 802      */
 803
 804     centerX = (ovalPtr[0] + ovalPtr[2])/2;
 805     centerY = (ovalPtr[1] + ovalPtr[3])/2;
 806     radX = (ovalPtr[2] - ovalPtr[0])/2;
 807     radY = (ovalPtr[3] - ovalPtr[1])/2;
 808
 809     deltaY = rectPtr[1] - centerY;
 810     if (deltaY < 0.0) {
 811         deltaY = centerY - rectPtr[3];
 812         if (deltaY < 0.0) {
 813             deltaY = 0;
 814         }
 815     }
 816     deltaY /= radY;
 817     deltaY *= deltaY;
 818
 819     /*
 820      * Left side:
 821      */
 822
 823     deltaX = (rectPtr[0] - centerX)/radX;
 824     deltaX *= deltaX;
 825     if ((deltaX + deltaY) <= 1.0) {
 826         return 0;
 827     }
 828
 829     /*
 830      * Right side:
 831      */
 832
 833     deltaX = (rectPtr[2] - centerX)/radX;
 834     deltaX *= deltaX;
 835     if ((deltaX + deltaY) <= 1.0) {
 836         return 0;
 837     }
 838
 839     deltaX = rectPtr[0] - centerX;
 840     if (deltaX < 0.0) {
 841         deltaX = centerX - rectPtr[2];
 842         if (deltaX < 0.0) {
 843             deltaX = 0;
 844         }
 845     }
 846     deltaX /= radX;
 847     deltaX *= deltaX;
 848
 849     /*
 850      * Bottom side:
 851      */
 852
 853     deltaY = (rectPtr[1] - centerY)/radY;
 854     deltaY *= deltaY;
 855     if ((deltaX + deltaY) < 1.0) {
 856         return 0;
 857     }
 858
 859     /*
 860      * Top side:
 861      */
 862
 863     deltaY = (rectPtr[3] - centerY)/radY;
 864     deltaY *= deltaY;
 865     if ((deltaX + deltaY) < 1.0) {
 866         return 0;
 867     }
 868
 869     return -1;
 870 }
 871 \f
 872 /*
 873  *--------------------------------------------------------------
 874  *
 875  * TkIncludePoint --
 876  *
 877  *      Given a point and a generic canvas item header, expand
 878  *      the item's bounding box if needed to include the point.
 879  *
 880  * Results:
 881  *      None.
 882  *
 883  * Side effects:
 884  *      The boudn.
 885  *
 886  *--------------------------------------------------------------
 887  */
 888
 889         /* ARGSUSED */
 890 void
 891 TkIncludePoint(itemPtr, pointPtr)
 892     register Tk_Item *itemPtr;          /* Item whose bounding box is
 893                                          * being calculated. */
 894     double *pointPtr;                   /* Address of two doubles giving
 895                                          * x and y coordinates of point. */
 896 {
 897     int tmp;
 898
 899     tmp = (int) (pointPtr[0] + 0.5);
 900     if (tmp < itemPtr->x1) {
 901         itemPtr->x1 = tmp;
 902     }
 903     if (tmp > itemPtr->x2) {
 904         itemPtr->x2 = tmp;
 905     }
 906     tmp = (int) (pointPtr[1] + 0.5);
 907     if (tmp < itemPtr->y1) {
 908         itemPtr->y1 = tmp;
 909     }
 910     if (tmp > itemPtr->y2) {
 911         itemPtr->y2 = tmp;
 912     }
 913 }
 914 \f
 915 /*
 916  *--------------------------------------------------------------
 917  *
 918  * TkBezierScreenPoints --
 919  *
 920  *      Given four control points, create a larger set of XPoints
 921  *      for a Bezier spline based on the points.
 922  *
 923  * Results:
 924  *      The array at *xPointPtr gets filled in with numSteps XPoints
 925  *      corresponding to the Bezier spline defined by the four
 926  *      control points.  Note:  no output point is generated for the
 927  *      first input point, but an output point *is* generated for
 928  *      the last input point.
 929  *
 930  * Side effects:
 931  *      None.
 932  *
 933  *--------------------------------------------------------------
 934  */
 935
 936 void
 937 TkBezierScreenPoints(canvas, control, numSteps, xPointPtr)
 938     Tk_Canvas canvas;                   /* Canvas in which curve is to be
 939                                          * drawn. */
 940     double control[];                   /* Array of coordinates for four
 941                                          * control points:  x0, y0, x1, y1,
 942                                          * ... x3 y3. */
 943     int numSteps;                       /* Number of curve points to
 944                                          * generate.  */
 945     register XPoint *xPointPtr;         /* Where to put new points. */
 946 {
 947     int i;
 948     double u, u2, u3, t, t2, t3;
 949
 950     for (i = 1; i <= numSteps; i++, xPointPtr++) {
 951         t = ((double) i)/((double) numSteps);
 952         t2 = t*t;
 953         t3 = t2*t;
 954         u = 1.0 - t;
 955         u2 = u*u;
 956         u3 = u2*u;
 957         Tk_CanvasDrawableCoords(canvas,
 958                 (control[0]*u3 + 3.0 * (control[2]*t*u2 + control[4]*t2*u)
 959                     + control[6]*t3),
 960                 (control[1]*u3 + 3.0 * (control[3]*t*u2 + control[5]*t2*u)
 961                     + control[7]*t3),
 962                 &xPointPtr->x, &xPointPtr->y);
 963     }
 964 }
 965 \f
 966 /*
 967  *--------------------------------------------------------------
 968  *
 969  * TkBezierPoints --
 970  *
 971  *      Given four control points, create a larger set of points
 972  *      for a Bezier spline based on the points.
 973  *
 974  * Results:
 975  *      The array at *coordPtr gets filled in with 2*numSteps
 976  *      coordinates, which correspond to the Bezier spline defined
 977  *      by the four control points.  Note:  no output point is
 978  *      generated for the first input point, but an output point
 979  *      *is* generated for the last input point.
 980  *
 981  * Side effects:
 982  *      None.
 983  *
 984  *--------------------------------------------------------------
 985  */
 986
 987 void
 988 TkBezierPoints(control, numSteps, coordPtr)
 989     double control[];                   /* Array of coordinates for four
 990                                          * control points:  x0, y0, x1, y1,
 991                                          * ... x3 y3. */
 992     int numSteps;                       /* Number of curve points to
 993                                          * generate.  */
 994     register double *coordPtr;          /* Where to put new points. */
 995 {
 996     int i;
 997     double u, u2, u3, t, t2, t3;
 998
 999     for (i = 1; i <= numSteps; i++, coordPtr += 2) {
1000         t = ((double) i)/((double) numSteps);
1001         t2 = t*t;
1002         t3 = t2*t;
1003         u = 1.0 - t;
1004         u2 = u*u;
1005         u3 = u2*u;
1006         coordPtr[0] = control[0]*u3
1007                 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3;
1008         coordPtr[1] = control[1]*u3
1009                 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3;
1010     }
1011 }
1012 \f
1013 /*
1014  *--------------------------------------------------------------
1015  *
1016  * TkMakeBezierCurve --
1017  *
1018  *      Given a set of points, create a new set of points that fit
1019  *      parabolic splines to the line segments connecting the original
1020  *      points.  Produces output points in either of two forms.
1021  *
1022  *      Note: in spite of this procedure's name, it does *not* generate
1023  *      Bezier curves.  Since only three control points are used for
1024  *      each curve segment, not four, the curves are actually just
1025  *      parabolic.
1026  *
1027  * Results:
1028  *      Either or both of the xPoints or dblPoints arrays are filled
1029  *      in.  The return value is the number of points placed in the
1030  *      arrays.  Note:  if the first and last points are the same, then
1031  *      a closed curve is generated.
1032  *
1033  * Side effects:
1034  *      None.
1035  *
1036  *--------------------------------------------------------------
1037  */
1038
1039 int
1040 TkMakeBezierCurve(canvas, pointPtr, numPoints, numSteps, xPoints, dblPoints)
1041     Tk_Canvas canvas;                   /* Canvas in which curve is to be
1042                                          * drawn. */
1043     double *pointPtr;                   /* Array of input coordinates:  x0,
1044                                          * y0, x1, y1, etc.. */
1045     int numPoints;                      /* Number of points at pointPtr. */
1046     int numSteps;                       /* Number of steps to use for each
1047                                          * spline segments (determines
1048                                          * smoothness of curve). */
1049     XPoint xPoints[];                   /* Array of XPoints to fill in (e.g.
1050                                          * for display.  NULL means don't
1051                                          * fill in any XPoints. */
1052     double dblPoints[];                 /* Array of points to fill in as
1053                                          * doubles, in the form x0, y0,
1054                                          * x1, y1, ....  NULL means don't
1055                                          * fill in anything in this form.
1056                                          * Caller must make sure that this
1057                                          * array has enough space. */
1058 {
1059     int closed, outputPoints, i;
1060     int numCoords = numPoints*2;
1061     double control[8];
1062
1063     /*
1064      * If the curve is a closed one then generate a special spline
1065      * that spans the last points and the first ones.  Otherwise
1066      * just put the first point into the output.
1067      */
1068
1069     if (!pointPtr) {
1070         /* Of pointPtr == NULL, this function returns an upper limit.
1071          * of the array size to store the coordinates. This can be
1072          * used to allocate storage, before the actual coordinates
1073          * are calculated. */
1074         return 1 + numPoints * numSteps;
1075     }
1076
1077     outputPoints = 0;
1078     if ((pointPtr[0] == pointPtr[numCoords-2])
1079             && (pointPtr[1] == pointPtr[numCoords-1])) {
1080         closed = 1;
1081         control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
1082         control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
1083         control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
1084         control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
1085         control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
1086         control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
1087         control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
1088         control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
1089         if (xPoints != NULL) {
1090             Tk_CanvasDrawableCoords(canvas, control[0], control[1],
1091                     &xPoints->x, &xPoints->y);
1092             TkBezierScreenPoints(canvas, control, numSteps, xPoints+1);
1093             xPoints += numSteps+1;
1094         }
1095         if (dblPoints != NULL) {
1096             dblPoints[0] = control[0];
1097             dblPoints[1] = control[1];
1098             TkBezierPoints(control, numSteps, dblPoints+2);
1099             dblPoints += 2*(numSteps+1);
1100         }
1101         outputPoints += numSteps+1;
1102     } else {
1103         closed = 0;
1104         if (xPoints != NULL) {
1105             Tk_CanvasDrawableCoords(canvas, pointPtr[0], pointPtr[1],
1106                     &xPoints->x, &xPoints->y);
1107             xPoints += 1;
1108         }
1109         if (dblPoints != NULL) {
1110             dblPoints[0] = pointPtr[0];
1111             dblPoints[1] = pointPtr[1];
1112             dblPoints += 2;
1113         }
1114         outputPoints += 1;
1115     }
1116
1117     for (i = 2; i < numPoints; i++, pointPtr += 2) {
1118         /*
1119          * Set up the first two control points.  This is done
1120          * differently for the first spline of an open curve
1121          * than for other cases.
1122          */
1123
1124         if ((i == 2) && !closed) {
1125             control[0] = pointPtr[0];
1126             control[1] = pointPtr[1];
1127             control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2];
1128             control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3];
1129         } else {
1130             control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
1131             control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
1132             control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2];
1133             control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3];
1134         }
1135
1136         /*
1137          * Set up the last two control points.  This is done
1138          * differently for the last spline of an open curve
1139          * than for other cases.
1140          */
1141
1142         if ((i == (numPoints-1)) && !closed) {
1143             control[4] = .667*pointPtr[2] + .333*pointPtr[4];
1144             control[5] = .667*pointPtr[3] + .333*pointPtr[5];
1145             control[6] = pointPtr[4];
1146             control[7] = pointPtr[5];
1147         } else {
1148             control[4] = .833*pointPtr[2] + .167*pointPtr[4];
1149             control[5] = .833*pointPtr[3] + .167*pointPtr[5];
1150             control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4];
1151             control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5];
1152         }
1153
1154         /*
1155          * If the first two points coincide, or if the last
1156          * two points coincide, then generate a single
1157          * straight-line segment by outputting the last control
1158          * point.
1159          */
1160
1161         if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3]))
1162                 || ((pointPtr[2] == pointPtr[4])
1163                 && (pointPtr[3] == pointPtr[5]))) {
1164             if (xPoints != NULL) {
1165                 Tk_CanvasDrawableCoords(canvas, control[6], control[7],
1166                         &xPoints[0].x, &xPoints[0].y);
1167                 xPoints++;
1168             }
1169             if (dblPoints != NULL) {
1170                 dblPoints[0] = control[6];
1171                 dblPoints[1] = control[7];
1172                 dblPoints += 2;
1173             }
1174             outputPoints += 1;
1175             continue;
1176         }
1177
1178         /*
1179          * Generate a Bezier spline using the control points.
1180          */
1181
1182
1183         if (xPoints != NULL) {
1184             TkBezierScreenPoints(canvas, control, numSteps, xPoints);
1185             xPoints += numSteps;
1186         }
1187         if (dblPoints != NULL) {
1188             TkBezierPoints(control, numSteps, dblPoints);
1189             dblPoints += 2*numSteps;
1190         }
1191         outputPoints += numSteps;
1192     }
1193     return outputPoints;
1194 }
1195 \f
1196 /*
1197  *--------------------------------------------------------------
1198  *
1199  * TkMakeBezierPostscript --
1200  *
1201  *      This procedure generates Postscript commands that create
1202  *      a path corresponding to a given Bezier curve.
1203  *
1204  * Results:
1205  *      None.  Postscript commands to generate the path are appended
1206  *      to the interp's result.
1207  *
1208  * Side effects:
1209  *      None.
1210  *
1211  *--------------------------------------------------------------
1212  */
1213
1214 void
1215 TkMakeBezierPostscript(interp, canvas, pointPtr, numPoints)
1216     Tcl_Interp *interp;                 /* Interpreter in whose result the
1217                                          * Postscript is to be stored. */
1218     Tk_Canvas canvas;                   /* Canvas widget for which the
1219                                          * Postscript is being generated. */
1220     double *pointPtr;                   /* Array of input coordinates:  x0,
1221                                          * y0, x1, y1, etc.. */
1222     int numPoints;                      /* Number of points at pointPtr. */
1223 {
1224     int closed, i;
1225     int numCoords = numPoints*2;
1226     double control[8];
1227     char buffer[200];
1228
1229     /*
1230      * If the curve is a closed one then generate a special spline
1231      * that spans the last points and the first ones.  Otherwise
1232      * just put the first point into the path.
1233      */
1234
1235     if ((pointPtr[0] == pointPtr[numCoords-2])
1236             && (pointPtr[1] == pointPtr[numCoords-1])) {
1237         closed = 1;
1238         control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
1239         control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
1240         control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
1241         control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
1242         control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
1243         control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
1244         control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
1245         control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
1246         sprintf(buffer, "%.15g %.15g moveto\n%.15g %.15g %.15g %.15g %.15g %.15g curveto\n",
1247                 control[0], Tk_CanvasPsY(canvas, control[1]),
1248                 control[2], Tk_CanvasPsY(canvas, control[3]),
1249                 control[4], Tk_CanvasPsY(canvas, control[5]),
1250                 control[6], Tk_CanvasPsY(canvas, control[7]));
1251     } else {
1252         closed = 0;
1253         control[6] = pointPtr[0];
1254         control[7] = pointPtr[1];
1255         sprintf(buffer, "%.15g %.15g moveto\n",
1256                 control[6], Tk_CanvasPsY(canvas, control[7]));
1257     }
1258     Tcl_AppendResult(interp, buffer, (char *) NULL);
1259
1260     /*
1261      * Cycle through all the remaining points in the curve, generating
1262      * a curve section for each vertex in the linear path.
1263      */
1264
1265     for (i = numPoints-2, pointPtr += 2; i > 0; i--, pointPtr += 2) {
1266         control[2] = 0.333*control[6] + 0.667*pointPtr[0];
1267         control[3] = 0.333*control[7] + 0.667*pointPtr[1];
1268
1269         /*
1270          * Set up the last two control points.  This is done
1271          * differently for the last spline of an open curve
1272          * than for other cases.
1273          */
1274
1275         if ((i == 1) && !closed) {
1276             control[6] = pointPtr[2];
1277             control[7] = pointPtr[3];
1278         } else {
1279             control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
1280             control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
1281         }
1282         control[4] = 0.333*control[6] + 0.667*pointPtr[0];
1283         control[5] = 0.333*control[7] + 0.667*pointPtr[1];
1284
1285         sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n",
1286                 control[2], Tk_CanvasPsY(canvas, control[3]),
1287                 control[4], Tk_CanvasPsY(canvas, control[5]),
1288                 control[6], Tk_CanvasPsY(canvas, control[7]));
1289         Tcl_AppendResult(interp, buffer, (char *) NULL);
1290     }
1291 }
1292 \f
1293 /*
1294  *--------------------------------------------------------------
1295  *
1296  * TkGetMiterPoints --
1297  *
1298  *      Given three points forming an angle, compute the
1299  *      coordinates of the inside and outside points of
1300  *      the mitered corner formed by a line of a given
1301  *      width at that angle.
1302  *
1303  * Results:
1304  *      If the angle formed by the three points is less than
1305  *      11 degrees then 0 is returned and m1 and m2 aren't
1306  *      modified.  Otherwise 1 is returned and the points at
1307  *      m1 and m2 are filled in with the positions of the points
1308  *      of the mitered corner.
1309  *
1310  * Side effects:
1311  *      None.
1312  *
1313  *--------------------------------------------------------------
1314  */
1315
1316 int
1317 TkGetMiterPoints(p1, p2, p3, width, m1, m2)
1318     double p1[];                /* Points to x- and y-coordinates of point
1319                                  * before vertex. */
1320     double p2[];                /* Points to x- and y-coordinates of vertex
1321                                  * for mitered joint. */
1322     double p3[];                /* Points to x- and y-coordinates of point
1323                                  * after vertex. */
1324     double width;               /* Width of line.  */
1325     double m1[];                /* Points to place to put "left" vertex
1326                                  * point (see as you face from p1 to p2). */
1327     double m2[];                /* Points to place to put "right" vertex
1328                                  * point. */
1329 {
1330     double theta1;              /* Angle of segment p2-p1. */
1331     double theta2;              /* Angle of segment p2-p3. */
1332     double theta;               /* Angle between line segments (angle
1333                                  * of joint). */
1334     double theta3;              /* Angle that bisects theta1 and
1335                                  * theta2 and points to m1. */
1336     double dist;                /* Distance of miter points from p2. */
1337     double deltaX, deltaY;      /* X and y offsets cooresponding to
1338                                  * dist (fudge factors for bounding
1339                                  * box). */
1340     double p1x, p1y, p2x, p2y, p3x, p3y;
1341     static double elevenDegrees = (11.0*2.0*PI)/360.0;
1342
1343     /*
1344      * Round the coordinates to integers to mimic what happens when the
1345      * line segments are displayed; without this code, the bounding box
1346      * of a mitered line can be miscomputed greatly.
1347      */
1348
1349     p1x = floor(p1[0]+0.5);
1350     p1y = floor(p1[1]+0.5);
1351     p2x = floor(p2[0]+0.5);
1352     p2y = floor(p2[1]+0.5);
1353     p3x = floor(p3[0]+0.5);
1354     p3y = floor(p3[1]+0.5);
1355
1356     if (p2y == p1y) {
1357         theta1 = (p2x < p1x) ? 0 : PI;
1358     } else if (p2x == p1x) {
1359         theta1 = (p2y < p1y) ? PI/2.0 : -PI/2.0;
1360     } else {
1361         theta1 = atan2(p1y - p2y, p1x - p2x);
1362     }
1363     if (p3y == p2y) {
1364         theta2 = (p3x > p2x) ? 0 : PI;
1365     } else if (p3x == p2x) {
1366         theta2 = (p3y > p2y) ? PI/2.0 : -PI/2.0;
1367     } else {
1368         theta2 = atan2(p3y - p2y, p3x - p2x);
1369     }
1370     theta = theta1 - theta2;
1371     if (theta > PI) {
1372         theta -= 2*PI;
1373     } else if (theta < -PI) {
1374         theta += 2*PI;
1375     }
1376     if ((theta < elevenDegrees) && (theta > -elevenDegrees)) {
1377         return 0;
1378     }
1379     dist = 0.5*width/sin(0.5*theta);
1380     if (dist < 0.0) {
1381         dist = -dist;
1382     }
1383
1384     /*
1385      * Compute theta3 (make sure that it points to the left when
1386      * looking from p1 to p2).
1387      */
1388
1389     theta3 = (theta1 + theta2)/2.0;
1390     if (sin(theta3 - (theta1 + PI)) < 0.0) {
1391         theta3 += PI;
1392     }
1393     deltaX = dist*cos(theta3);
1394     m1[0] = p2x + deltaX;
1395     m2[0] = p2x - deltaX;
1396     deltaY = dist*sin(theta3);
1397     m1[1] = p2y + deltaY;
1398     m2[1] = p2y - deltaY;
1399     return 1;
1400 }
1401 \f
1402 /*
1403  *--------------------------------------------------------------
1404  *
1405  * TkGetButtPoints --
1406  *
1407  *      Given two points forming a line segment, compute the
1408  *      coordinates of two endpoints of a rectangle formed by
1409  *      bloating the line segment until it is width units wide.
1410  *
1411  * Results:
1412  *      There is no return value.  M1 and m2 are filled in to
1413  *      correspond to m1 and m2 in the diagram below:
1414  *
1415  *                 ----------------* m1
1416  *                                 |
1417  *              p1 *---------------* p2
1418  *                                 |
1419  *                 ----------------* m2
1420  *
1421  *      M1 and m2 will be W units apart, with p2 centered between
1422  *      them and m1-m2 perpendicular to p1-p2.  However, if
1423  *      "project" is true then m1 and m2 will be as follows:
1424  *
1425  *                 -------------------* m1
1426  *                                p2  |
1427  *              p1 *---------------*  |
1428  *                                    |
1429  *                 -------------------* m2
1430  *
1431  *      In this case p2 will be width/2 units from the segment m1-m2.
1432  *
1433  * Side effects:
1434  *      None.
1435  *
1436  *--------------------------------------------------------------
1437  */
1438
1439 void
1440 TkGetButtPoints(p1, p2, width, project, m1, m2)
1441     double p1[];                /* Points to x- and y-coordinates of point
1442                                  * before vertex. */
1443     double p2[];                /* Points to x- and y-coordinates of vertex
1444                                  * for mitered joint. */
1445     double width;               /* Width of line.  */
1446     int project;                /* Non-zero means project p2 by an additional
1447                                  * width/2 before computing m1 and m2. */
1448     double m1[];                /* Points to place to put "left" result
1449                                  * point, as you face from p1 to p2. */
1450     double m2[];                /* Points to place to put "right" result
1451                                  * point. */
1452 {
1453     double length;              /* Length of p1-p2 segment. */
1454     double deltaX, deltaY;      /* Increments in coords. */
1455
1456     width *= 0.5;
1457     length = hypot(p2[0] - p1[0], p2[1] - p1[1]);
1458     if (length == 0.0) {
1459         m1[0] = m2[0] = p2[0];
1460         m1[1] = m2[1] = p2[1];
1461     } else {
1462         deltaX = -width * (p2[1] - p1[1]) / length;
1463         deltaY = width * (p2[0] - p1[0]) / length;
1464         m1[0] = p2[0] + deltaX;
1465         m2[0] = p2[0] - deltaX;
1466         m1[1] = p2[1] + deltaY;
1467         m2[1] = p2[1] - deltaY;
1468         if (project) {
1469             m1[0] += deltaY;
1470             m2[0] += deltaY;
1471             m1[1] -= deltaX;
1472             m2[1] -= deltaX;
1473         }
1474     }
1475 }
1476