home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Tcl-Tk 8.0 / Pre-installed version / tk8.0 / generic / tkTrig.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-15  |  39.7 KB  |  1,468 lines  |  [TEXT/CWIE]
  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 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.  * SCCS: @(#) tkTrig.c 1.27 97/03/07 11:34:35
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.     outputPoints = 0;
  1070.     if ((pointPtr[0] == pointPtr[numCoords-2])
  1071.         && (pointPtr[1] == pointPtr[numCoords-1])) {
  1072.     closed = 1;
  1073.     control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
  1074.     control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
  1075.     control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
  1076.     control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
  1077.     control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
  1078.     control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
  1079.     control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  1080.     control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  1081.     if (xPoints != NULL) {
  1082.         Tk_CanvasDrawableCoords(canvas, control[0], control[1],
  1083.             &xPoints->x, &xPoints->y);
  1084.         TkBezierScreenPoints(canvas, control, numSteps, xPoints+1);
  1085.         xPoints += numSteps+1;
  1086.     }
  1087.     if (dblPoints != NULL) {
  1088.         dblPoints[0] = control[0];
  1089.         dblPoints[1] = control[1];
  1090.         TkBezierPoints(control, numSteps, dblPoints+2);
  1091.         dblPoints += 2*(numSteps+1);
  1092.     }
  1093.     outputPoints += numSteps+1;
  1094.     } else {
  1095.     closed = 0;
  1096.     if (xPoints != NULL) {
  1097.         Tk_CanvasDrawableCoords(canvas, pointPtr[0], pointPtr[1],
  1098.             &xPoints->x, &xPoints->y);
  1099.         xPoints += 1;
  1100.     }
  1101.     if (dblPoints != NULL) {
  1102.         dblPoints[0] = pointPtr[0];
  1103.         dblPoints[1] = pointPtr[1];
  1104.         dblPoints += 2;
  1105.     }
  1106.     outputPoints += 1;
  1107.     }
  1108.  
  1109.     for (i = 2; i < numPoints; i++, pointPtr += 2) {
  1110.     /*
  1111.      * Set up the first two control points.  This is done
  1112.      * differently for the first spline of an open curve
  1113.      * than for other cases.
  1114.      */
  1115.  
  1116.     if ((i == 2) && !closed) {
  1117.         control[0] = pointPtr[0];
  1118.         control[1] = pointPtr[1];
  1119.         control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2];
  1120.         control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3];
  1121.     } else {
  1122.         control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  1123.         control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  1124.         control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2];
  1125.         control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3];
  1126.     }
  1127.  
  1128.     /*
  1129.      * Set up the last two control points.  This is done
  1130.      * differently for the last spline of an open curve
  1131.      * than for other cases.
  1132.      */
  1133.  
  1134.     if ((i == (numPoints-1)) && !closed) {
  1135.         control[4] = .667*pointPtr[2] + .333*pointPtr[4];
  1136.         control[5] = .667*pointPtr[3] + .333*pointPtr[5];
  1137.         control[6] = pointPtr[4];
  1138.         control[7] = pointPtr[5];
  1139.     } else {
  1140.         control[4] = .833*pointPtr[2] + .167*pointPtr[4];
  1141.         control[5] = .833*pointPtr[3] + .167*pointPtr[5];
  1142.         control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4];
  1143.         control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5];
  1144.     }
  1145.  
  1146.     /*
  1147.      * If the first two points coincide, or if the last
  1148.      * two points coincide, then generate a single
  1149.      * straight-line segment by outputting the last control
  1150.      * point.
  1151.      */
  1152.  
  1153.     if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3]))
  1154.         || ((pointPtr[2] == pointPtr[4])
  1155.         && (pointPtr[3] == pointPtr[5]))) {
  1156.         if (xPoints != NULL) {
  1157.         Tk_CanvasDrawableCoords(canvas, control[6], control[7],
  1158.             &xPoints[0].x, &xPoints[0].y);
  1159.         xPoints++;
  1160.         }
  1161.         if (dblPoints != NULL) {
  1162.         dblPoints[0] = control[6];
  1163.         dblPoints[1] = control[7];
  1164.         dblPoints += 2;
  1165.         }
  1166.         outputPoints += 1;
  1167.         continue;
  1168.     }
  1169.  
  1170.     /*
  1171.      * Generate a Bezier spline using the control points.
  1172.      */
  1173.  
  1174.  
  1175.     if (xPoints != NULL) {
  1176.         TkBezierScreenPoints(canvas, control, numSteps, xPoints);
  1177.         xPoints += numSteps;
  1178.     }
  1179.     if (dblPoints != NULL) {
  1180.         TkBezierPoints(control, numSteps, dblPoints);
  1181.         dblPoints += 2*numSteps;
  1182.     }
  1183.     outputPoints += numSteps;
  1184.     }
  1185.     return outputPoints;
  1186. }
  1187.  
  1188. /*
  1189.  *--------------------------------------------------------------
  1190.  *
  1191.  * TkMakeBezierPostscript --
  1192.  *
  1193.  *    This procedure generates Postscript commands that create
  1194.  *    a path corresponding to a given Bezier curve.
  1195.  *
  1196.  * Results:
  1197.  *    None.  Postscript commands to generate the path are appended
  1198.  *    to interp->result.
  1199.  *
  1200.  * Side effects:
  1201.  *    None.
  1202.  *
  1203.  *--------------------------------------------------------------
  1204.  */
  1205.  
  1206. void
  1207. TkMakeBezierPostscript(interp, canvas, pointPtr, numPoints)
  1208.     Tcl_Interp *interp;            /* Interpreter in whose result the
  1209.                      * Postscript is to be stored. */
  1210.     Tk_Canvas canvas;            /* Canvas widget for which the
  1211.                      * Postscript is being generated. */
  1212.     double *pointPtr;            /* Array of input coordinates:  x0,
  1213.                      * y0, x1, y1, etc.. */
  1214.     int numPoints;            /* Number of points at pointPtr. */
  1215. {
  1216.     int closed, i;
  1217.     int numCoords = numPoints*2;
  1218.     double control[8];
  1219.     char buffer[200];
  1220.  
  1221.     /*
  1222.      * If the curve is a closed one then generate a special spline
  1223.      * that spans the last points and the first ones.  Otherwise
  1224.      * just put the first point into the path.
  1225.      */
  1226.  
  1227.     if ((pointPtr[0] == pointPtr[numCoords-2])
  1228.         && (pointPtr[1] == pointPtr[numCoords-1])) {
  1229.     closed = 1;
  1230.     control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
  1231.     control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
  1232.     control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
  1233.     control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
  1234.     control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
  1235.     control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
  1236.     control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  1237.     control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  1238.     sprintf(buffer, "%.15g %.15g moveto\n%.15g %.15g %.15g %.15g %.15g %.15g curveto\n",
  1239.         control[0], Tk_CanvasPsY(canvas, control[1]),
  1240.         control[2], Tk_CanvasPsY(canvas, control[3]),
  1241.         control[4], Tk_CanvasPsY(canvas, control[5]),
  1242.         control[6], Tk_CanvasPsY(canvas, control[7]));
  1243.     } else {
  1244.     closed = 0;
  1245.     control[6] = pointPtr[0];
  1246.     control[7] = pointPtr[1];
  1247.     sprintf(buffer, "%.15g %.15g moveto\n",
  1248.         control[6], Tk_CanvasPsY(canvas, control[7]));
  1249.     }
  1250.     Tcl_AppendResult(interp, buffer, (char *) NULL);
  1251.  
  1252.     /*
  1253.      * Cycle through all the remaining points in the curve, generating
  1254.      * a curve section for each vertex in the linear path.
  1255.      */
  1256.  
  1257.     for (i = numPoints-2, pointPtr += 2; i > 0; i--, pointPtr += 2) {
  1258.     control[2] = 0.333*control[6] + 0.667*pointPtr[0];
  1259.     control[3] = 0.333*control[7] + 0.667*pointPtr[1];
  1260.  
  1261.     /*
  1262.      * Set up the last two control points.  This is done
  1263.      * differently for the last spline of an open curve
  1264.      * than for other cases.
  1265.      */
  1266.  
  1267.     if ((i == 1) && !closed) {
  1268.         control[6] = pointPtr[2];
  1269.         control[7] = pointPtr[3];
  1270.     } else {
  1271.         control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  1272.         control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  1273.     }
  1274.     control[4] = 0.333*control[6] + 0.667*pointPtr[0];
  1275.     control[5] = 0.333*control[7] + 0.667*pointPtr[1];
  1276.  
  1277.     sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n",
  1278.         control[2], Tk_CanvasPsY(canvas, control[3]),
  1279.         control[4], Tk_CanvasPsY(canvas, control[5]),
  1280.         control[6], Tk_CanvasPsY(canvas, control[7]));
  1281.     Tcl_AppendResult(interp, buffer, (char *) NULL);
  1282.     }
  1283. }
  1284.  
  1285. /*
  1286.  *--------------------------------------------------------------
  1287.  *
  1288.  * TkGetMiterPoints --
  1289.  *
  1290.  *    Given three points forming an angle, compute the
  1291.  *    coordinates of the inside and outside points of
  1292.  *    the mitered corner formed by a line of a given
  1293.  *    width at that angle.
  1294.  *
  1295.  * Results:
  1296.  *    If the angle formed by the three points is less than
  1297.  *    11 degrees then 0 is returned and m1 and m2 aren't
  1298.  *    modified.  Otherwise 1 is returned and the points at
  1299.  *    m1 and m2 are filled in with the positions of the points
  1300.  *    of the mitered corner.
  1301.  *
  1302.  * Side effects:
  1303.  *    None.
  1304.  *
  1305.  *--------------------------------------------------------------
  1306.  */
  1307.  
  1308. int
  1309. TkGetMiterPoints(p1, p2, p3, width, m1, m2)
  1310.     double p1[];        /* Points to x- and y-coordinates of point
  1311.                  * before vertex. */
  1312.     double p2[];        /* Points to x- and y-coordinates of vertex
  1313.                  * for mitered joint. */
  1314.     double p3[];        /* Points to x- and y-coordinates of point
  1315.                  * after vertex. */
  1316.     double width;        /* Width of line.  */
  1317.     double m1[];        /* Points to place to put "left" vertex
  1318.                  * point (see as you face from p1 to p2). */
  1319.     double m2[];        /* Points to place to put "right" vertex
  1320.                  * point. */
  1321. {
  1322.     double theta1;        /* Angle of segment p2-p1. */
  1323.     double theta2;        /* Angle of segment p2-p3. */
  1324.     double theta;        /* Angle between line segments (angle
  1325.                  * of joint). */
  1326.     double theta3;        /* Angle that bisects theta1 and
  1327.                  * theta2 and points to m1. */
  1328.     double dist;        /* Distance of miter points from p2. */
  1329.     double deltaX, deltaY;    /* X and y offsets cooresponding to
  1330.                  * dist (fudge factors for bounding
  1331.                  * box). */
  1332.     double p1x, p1y, p2x, p2y, p3x, p3y;
  1333.     static double elevenDegrees = (11.0*2.0*PI)/360.0;
  1334.  
  1335.     /*
  1336.      * Round the coordinates to integers to mimic what happens when the
  1337.      * line segments are displayed; without this code, the bounding box
  1338.      * of a mitered line can be miscomputed greatly.
  1339.      */
  1340.  
  1341.     p1x = floor(p1[0]+0.5);
  1342.     p1y = floor(p1[1]+0.5);
  1343.     p2x = floor(p2[0]+0.5);
  1344.     p2y = floor(p2[1]+0.5);
  1345.     p3x = floor(p3[0]+0.5);
  1346.     p3y = floor(p3[1]+0.5);
  1347.  
  1348.     if (p2y == p1y) {
  1349.     theta1 = (p2x < p1x) ? 0 : PI;
  1350.     } else if (p2x == p1x) {
  1351.     theta1 = (p2y < p1y) ? PI/2.0 : -PI/2.0;
  1352.     } else {
  1353.     theta1 = atan2(p1y - p2y, p1x - p2x);
  1354.     }
  1355.     if (p3y == p2y) {
  1356.     theta2 = (p3x > p2x) ? 0 : PI;
  1357.     } else if (p3x == p2x) {
  1358.     theta2 = (p3y > p2y) ? PI/2.0 : -PI/2.0;
  1359.     } else {
  1360.     theta2 = atan2(p3y - p2y, p3x - p2x);
  1361.     }
  1362.     theta = theta1 - theta2;
  1363.     if (theta > PI) {
  1364.     theta -= 2*PI;
  1365.     } else if (theta < -PI) {
  1366.     theta += 2*PI;
  1367.     }
  1368.     if ((theta < elevenDegrees) && (theta > -elevenDegrees)) {
  1369.     return 0;
  1370.     }
  1371.     dist = 0.5*width/sin(0.5*theta);
  1372.     if (dist < 0.0) {
  1373.     dist = -dist;
  1374.     }
  1375.  
  1376.     /*
  1377.      * Compute theta3 (make sure that it points to the left when
  1378.      * looking from p1 to p2).
  1379.      */
  1380.  
  1381.     theta3 = (theta1 + theta2)/2.0;
  1382.     if (sin(theta3 - (theta1 + PI)) < 0.0) {
  1383.     theta3 += PI;
  1384.     }
  1385.     deltaX = dist*cos(theta3);
  1386.     m1[0] = p2x + deltaX;
  1387.     m2[0] = p2x - deltaX;
  1388.     deltaY = dist*sin(theta3);
  1389.     m1[1] = p2y + deltaY;
  1390.     m2[1] = p2y - deltaY;
  1391.     return 1;
  1392. }
  1393.  
  1394. /*
  1395.  *--------------------------------------------------------------
  1396.  *
  1397.  * TkGetButtPoints --
  1398.  *
  1399.  *    Given two points forming a line segment, compute the
  1400.  *    coordinates of two endpoints of a rectangle formed by
  1401.  *    bloating the line segment until it is width units wide.
  1402.  *
  1403.  * Results:
  1404.  *    There is no return value.  M1 and m2 are filled in to
  1405.  *    correspond to m1 and m2 in the diagram below:
  1406.  *
  1407.  *           ----------------* m1
  1408.  *                   |
  1409.  *        p1 *---------------* p2
  1410.  *                   |
  1411.  *           ----------------* m2
  1412.  *
  1413.  *    M1 and m2 will be W units apart, with p2 centered between
  1414.  *    them and m1-m2 perpendicular to p1-p2.  However, if
  1415.  *    "project" is true then m1 and m2 will be as follows:
  1416.  *
  1417.  *           -------------------* m1
  1418.  *                  p2  |
  1419.  *        p1 *---------------*  |
  1420.  *                      |
  1421.  *           -------------------* m2
  1422.  *
  1423.  *    In this case p2 will be width/2 units from the segment m1-m2.
  1424.  *
  1425.  * Side effects:
  1426.  *    None.
  1427.  *
  1428.  *--------------------------------------------------------------
  1429.  */
  1430.  
  1431. void
  1432. TkGetButtPoints(p1, p2, width, project, m1, m2)
  1433.     double p1[];        /* Points to x- and y-coordinates of point
  1434.                  * before vertex. */
  1435.     double p2[];        /* Points to x- and y-coordinates of vertex
  1436.                  * for mitered joint. */
  1437.     double width;        /* Width of line.  */
  1438.     int project;        /* Non-zero means project p2 by an additional
  1439.                  * width/2 before computing m1 and m2. */
  1440.     double m1[];        /* Points to place to put "left" result
  1441.                  * point, as you face from p1 to p2. */
  1442.     double m2[];        /* Points to place to put "right" result
  1443.                  * point. */
  1444. {
  1445.     double length;        /* Length of p1-p2 segment. */
  1446.     double deltaX, deltaY;    /* Increments in coords. */
  1447.  
  1448.     width *= 0.5;
  1449.     length = hypot(p2[0] - p1[0], p2[1] - p1[1]);
  1450.     if (length == 0.0) {
  1451.     m1[0] = m2[0] = p2[0];
  1452.     m1[1] = m2[1] = p2[1];
  1453.     } else {
  1454.     deltaX = -width * (p2[1] - p1[1]) / length;
  1455.     deltaY = width * (p2[0] - p1[0]) / length;
  1456.     m1[0] = p2[0] + deltaX;
  1457.     m2[0] = p2[0] - deltaX;
  1458.     m1[1] = p2[1] + deltaY;
  1459.     m2[1] = p2[1] - deltaY;
  1460.     if (project) {
  1461.         m1[0] += deltaY;
  1462.         m2[0] += deltaY;
  1463.         m1[1] -= deltaX;
  1464.         m2[1] -= deltaX;
  1465.     }
  1466.     }
  1467. }
  1468.