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