diff options
Diffstat (limited to 'generic/tkTrig.c')
| -rw-r--r-- | generic/tkTrig.c | 1467 |
1 files changed, 1467 insertions, 0 deletions
diff --git a/generic/tkTrig.c b/generic/tkTrig.c new file mode 100644 index 0000000..52dd8ba --- /dev/null +++ b/generic/tkTrig.c @@ -0,0 +1,1467 @@ +/* + * tkTrig.c -- + * + * This file contains a collection of trigonometry utility + * routines that are used by Tk and in particular by the + * canvas code. It also has miscellaneous geometry functions + * used by canvases. + * + * Copyright (c) 1992-1994 The Regents of the University of California. + * Copyright (c) 1994 Sun Microsystems, Inc. + * + * See the file "license.terms" for information on usage and redistribution + * of this file, and for a DISCLAIMER OF ALL WARRANTIES. + * + * SCCS: @(#) tkTrig.c 1.27 97/03/07 11:34:35 + */ + +#include <stdio.h> +#include "tkInt.h" +#include "tkPort.h" +#include "tkCanvas.h" + +#undef MIN +#define MIN(a,b) (((a) < (b)) ? (a) : (b)) +#undef MAX +#define MAX(a,b) (((a) > (b)) ? (a) : (b)) +#ifndef PI +# define PI 3.14159265358979323846 +#endif /* PI */ + +/* + *-------------------------------------------------------------- + * + * TkLineToPoint -- + * + * Compute the distance from a point to a finite line segment. + * + * Results: + * The return value is the distance from the line segment + * whose end-points are *end1Ptr and *end2Ptr to the point + * given by *pointPtr. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +double +TkLineToPoint(end1Ptr, end2Ptr, pointPtr) + double end1Ptr[2]; /* Coordinates of first end-point of line. */ + double end2Ptr[2]; /* Coordinates of second end-point of line. */ + double pointPtr[2]; /* Points to coords for point. */ +{ + double x, y; + + /* + * Compute the point on the line that is closest to the + * point. This must be done separately for vertical edges, + * horizontal edges, and other edges. + */ + + if (end1Ptr[0] == end2Ptr[0]) { + + /* + * Vertical edge. + */ + + x = end1Ptr[0]; + if (end1Ptr[1] >= end2Ptr[1]) { + y = MIN(end1Ptr[1], pointPtr[1]); + y = MAX(y, end2Ptr[1]); + } else { + y = MIN(end2Ptr[1], pointPtr[1]); + y = MAX(y, end1Ptr[1]); + } + } else if (end1Ptr[1] == end2Ptr[1]) { + + /* + * Horizontal edge. + */ + + y = end1Ptr[1]; + if (end1Ptr[0] >= end2Ptr[0]) { + x = MIN(end1Ptr[0], pointPtr[0]); + x = MAX(x, end2Ptr[0]); + } else { + x = MIN(end2Ptr[0], pointPtr[0]); + x = MAX(x, end1Ptr[0]); + } + } else { + double m1, b1, m2, b2; + + /* + * The edge is neither horizontal nor vertical. Convert the + * edge to a line equation of the form y = m1*x + b1. Then + * compute a line perpendicular to this edge but passing + * through the point, also in the form y = m2*x + b2. + */ + + m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); + b1 = end1Ptr[1] - m1*end1Ptr[0]; + m2 = -1.0/m1; + b2 = pointPtr[1] - m2*pointPtr[0]; + x = (b2 - b1)/(m1 - m2); + y = m1*x + b1; + if (end1Ptr[0] > end2Ptr[0]) { + if (x > end1Ptr[0]) { + x = end1Ptr[0]; + y = end1Ptr[1]; + } else if (x < end2Ptr[0]) { + x = end2Ptr[0]; + y = end2Ptr[1]; + } + } else { + if (x > end2Ptr[0]) { + x = end2Ptr[0]; + y = end2Ptr[1]; + } else if (x < end1Ptr[0]) { + x = end1Ptr[0]; + y = end1Ptr[1]; + } + } + } + + /* + * Compute the distance to the closest point. + */ + + return hypot(pointPtr[0] - x, pointPtr[1] - y); +} + +/* + *-------------------------------------------------------------- + * + * TkLineToArea -- + * + * Determine whether a line lies entirely inside, entirely + * outside, or overlapping a given rectangular area. + * + * Results: + * -1 is returned if the line given by end1Ptr and end2Ptr + * is entirely outside the rectangle given by rectPtr. 0 is + * returned if the polygon overlaps the rectangle, and 1 is + * returned if the polygon is entirely inside the rectangle. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +int +TkLineToArea(end1Ptr, end2Ptr, rectPtr) + double end1Ptr[2]; /* X and y coordinates for one endpoint + * of line. */ + double end2Ptr[2]; /* X and y coordinates for other endpoint + * of line. */ + double rectPtr[4]; /* Points to coords for rectangle, in the + * order x1, y1, x2, y2. X1 must be no + * larger than x2, and y1 no larger than y2. */ +{ + int inside1, inside2; + + /* + * First check the two points individually to see whether they + * are inside the rectangle or not. + */ + + inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2]) + && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]); + inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2]) + && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]); + if (inside1 != inside2) { + return 0; + } + if (inside1 & inside2) { + return 1; + } + + /* + * Both points are outside the rectangle, but still need to check + * for intersections between the line and the rectangle. Horizontal + * and vertical lines are particularly easy, so handle them + * separately. + */ + + if (end1Ptr[0] == end2Ptr[0]) { + /* + * Vertical line. + */ + + if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1])) + && (end1Ptr[0] >= rectPtr[0]) + && (end1Ptr[0] <= rectPtr[2])) { + return 0; + } + } else if (end1Ptr[1] == end2Ptr[1]) { + /* + * Horizontal line. + */ + + if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0])) + && (end1Ptr[1] >= rectPtr[1]) + && (end1Ptr[1] <= rectPtr[3])) { + return 0; + } + } else { + double m, x, y, low, high; + + /* + * Diagonal line. Compute slope of line and use + * for intersection checks against each of the + * sides of the rectangle: left, right, bottom, top. + */ + + m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]); + if (end1Ptr[0] < end2Ptr[0]) { + low = end1Ptr[0]; high = end2Ptr[0]; + } else { + low = end2Ptr[0]; high = end1Ptr[0]; + } + + /* + * Left edge. + */ + + y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m; + if ((rectPtr[0] >= low) && (rectPtr[0] <= high) + && (y >= rectPtr[1]) && (y <= rectPtr[3])) { + return 0; + } + + /* + * Right edge. + */ + + y += (rectPtr[2] - rectPtr[0])*m; + if ((y >= rectPtr[1]) && (y <= rectPtr[3]) + && (rectPtr[2] >= low) && (rectPtr[2] <= high)) { + return 0; + } + + /* + * Bottom edge. + */ + + if (end1Ptr[1] < end2Ptr[1]) { + low = end1Ptr[1]; high = end2Ptr[1]; + } else { + low = end2Ptr[1]; high = end1Ptr[1]; + } + x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m; + if ((x >= rectPtr[0]) && (x <= rectPtr[2]) + && (rectPtr[1] >= low) && (rectPtr[1] <= high)) { + return 0; + } + + /* + * Top edge. + */ + + x += (rectPtr[3] - rectPtr[1])/m; + if ((x >= rectPtr[0]) && (x <= rectPtr[2]) + && (rectPtr[3] >= low) && (rectPtr[3] <= high)) { + return 0; + } + } + return -1; +} + +/* + *-------------------------------------------------------------- + * + * TkThickPolyLineToArea -- + * + * This procedure is called to determine whether a connected + * series of line segments lies entirely inside, entirely + * outside, or overlapping a given rectangular area. + * + * Results: + * -1 is returned if the lines are entirely outside the area, + * 0 if they overlap, and 1 if they are entirely inside the + * given area. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + + /* ARGSUSED */ +int +TkThickPolyLineToArea(coordPtr, numPoints, width, capStyle, joinStyle, rectPtr) + double *coordPtr; /* Points to an array of coordinates for + * the polyline: x0, y0, x1, y1, ... */ + int numPoints; /* Total number of points at *coordPtr. */ + double width; /* Width of each line segment. */ + int capStyle; /* How are end-points of polyline drawn? + * CapRound, CapButt, or CapProjecting. */ + int joinStyle; /* How are joints in polyline drawn? + * JoinMiter, JoinRound, or JoinBevel. */ + double *rectPtr; /* Rectangular area to check against. */ +{ + double radius, poly[10]; + int count; + int changedMiterToBevel; /* Non-zero means that a mitered corner + * had to be treated as beveled after all + * because the angle was < 11 degrees. */ + int inside; /* Tentative guess about what to return, + * based on all points seen so far: one + * means everything seen so far was + * inside the area; -1 means everything + * was outside the area. 0 means overlap + * has been found. */ + + radius = width/2.0; + inside = -1; + + if ((coordPtr[0] >= rectPtr[0]) && (coordPtr[0] <= rectPtr[2]) + && (coordPtr[1] >= rectPtr[1]) && (coordPtr[1] <= rectPtr[3])) { + inside = 1; + } + + /* + * Iterate through all of the edges of the line, computing a polygon + * for each edge and testing the area against that polygon. In + * addition, there are additional tests to deal with rounded joints + * and caps. + */ + + changedMiterToBevel = 0; + for (count = numPoints; count >= 2; count--, coordPtr += 2) { + + /* + * If rounding is done around the first point of the edge + * then test a circular region around the point with the + * area. + */ + + if (((capStyle == CapRound) && (count == numPoints)) + || ((joinStyle == JoinRound) && (count != numPoints))) { + poly[0] = coordPtr[0] - radius; + poly[1] = coordPtr[1] - radius; + poly[2] = coordPtr[0] + radius; + poly[3] = coordPtr[1] + radius; + if (TkOvalToArea(poly, rectPtr) != inside) { + return 0; + } + } + + /* + * Compute the polygonal shape corresponding to this edge, + * consisting of two points for the first point of the edge + * and two points for the last point of the edge. + */ + + if (count == numPoints) { + TkGetButtPoints(coordPtr+2, coordPtr, width, + capStyle == CapProjecting, poly, poly+2); + } else if ((joinStyle == JoinMiter) && !changedMiterToBevel) { + poly[0] = poly[6]; + poly[1] = poly[7]; + poly[2] = poly[4]; + poly[3] = poly[5]; + } else { + TkGetButtPoints(coordPtr+2, coordPtr, width, 0, poly, poly+2); + + /* + * If the last joint was beveled, then also check a + * polygon comprising the last two points of the previous + * polygon and the first two from this polygon; this checks + * the wedges that fill the beveled joint. + */ + + if ((joinStyle == JoinBevel) || changedMiterToBevel) { + poly[8] = poly[0]; + poly[9] = poly[1]; + if (TkPolygonToArea(poly, 5, rectPtr) != inside) { + return 0; + } + changedMiterToBevel = 0; + } + } + if (count == 2) { + TkGetButtPoints(coordPtr, coordPtr+2, width, + capStyle == CapProjecting, poly+4, poly+6); + } else if (joinStyle == JoinMiter) { + if (TkGetMiterPoints(coordPtr, coordPtr+2, coordPtr+4, + (double) width, poly+4, poly+6) == 0) { + changedMiterToBevel = 1; + TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4, + poly+6); + } + } else { + TkGetButtPoints(coordPtr, coordPtr+2, width, 0, poly+4, poly+6); + } + poly[8] = poly[0]; + poly[9] = poly[1]; + if (TkPolygonToArea(poly, 5, rectPtr) != inside) { + return 0; + } + } + + /* + * If caps are rounded, check the cap around the final point + * of the line. + */ + + if (capStyle == CapRound) { + poly[0] = coordPtr[0] - radius; + poly[1] = coordPtr[1] - radius; + poly[2] = coordPtr[0] + radius; + poly[3] = coordPtr[1] + radius; + if (TkOvalToArea(poly, rectPtr) != inside) { + return 0; + } + } + + return inside; +} + +/* + *-------------------------------------------------------------- + * + * TkPolygonToPoint -- + * + * Compute the distance from a point to a polygon. + * + * Results: + * The return value is 0.0 if the point referred to by + * pointPtr is within the polygon referred to by polyPtr + * and numPoints. Otherwise the return value is the + * distance of the point from the polygon. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +double +TkPolygonToPoint(polyPtr, numPoints, pointPtr) + double *polyPtr; /* Points to an array coordinates for + * closed polygon: x0, y0, x1, y1, ... + * The polygon may be self-intersecting. */ + int numPoints; /* Total number of points at *polyPtr. */ + double *pointPtr; /* Points to coords for point. */ +{ + double bestDist; /* Closest distance between point and + * any edge in polygon. */ + int intersections; /* Number of edges in the polygon that + * intersect a ray extending vertically + * upwards from the point to infinity. */ + int count; + register double *pPtr; + + /* + * Iterate through all of the edges in the polygon, updating + * bestDist and intersections. + * + * TRICKY POINT: when computing intersections, include left + * x-coordinate of line within its range, but not y-coordinate. + * Otherwise if the point lies exactly below a vertex we'll + * count it as two intersections. + */ + + bestDist = 1.0e36; + intersections = 0; + + for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) { + double x, y, dist; + + /* + * Compute the point on the current edge closest to the point + * and update the intersection count. This must be done + * separately for vertical edges, horizontal edges, and + * other edges. + */ + + if (pPtr[2] == pPtr[0]) { + + /* + * Vertical edge. + */ + + x = pPtr[0]; + if (pPtr[1] >= pPtr[3]) { + y = MIN(pPtr[1], pointPtr[1]); + y = MAX(y, pPtr[3]); + } else { + y = MIN(pPtr[3], pointPtr[1]); + y = MAX(y, pPtr[1]); + } + } else if (pPtr[3] == pPtr[1]) { + + /* + * Horizontal edge. + */ + + y = pPtr[1]; + if (pPtr[0] >= pPtr[2]) { + x = MIN(pPtr[0], pointPtr[0]); + x = MAX(x, pPtr[2]); + if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0]) + && (pointPtr[0] >= pPtr[2])) { + intersections++; + } + } else { + x = MIN(pPtr[2], pointPtr[0]); + x = MAX(x, pPtr[0]); + if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2]) + && (pointPtr[0] >= pPtr[0])) { + intersections++; + } + } + } else { + double m1, b1, m2, b2; + int lower; /* Non-zero means point below line. */ + + /* + * The edge is neither horizontal nor vertical. Convert the + * edge to a line equation of the form y = m1*x + b1. Then + * compute a line perpendicular to this edge but passing + * through the point, also in the form y = m2*x + b2. + */ + + m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]); + b1 = pPtr[1] - m1*pPtr[0]; + m2 = -1.0/m1; + b2 = pointPtr[1] - m2*pointPtr[0]; + x = (b2 - b1)/(m1 - m2); + y = m1*x + b1; + if (pPtr[0] > pPtr[2]) { + if (x > pPtr[0]) { + x = pPtr[0]; + y = pPtr[1]; + } else if (x < pPtr[2]) { + x = pPtr[2]; + y = pPtr[3]; + } + } else { + if (x > pPtr[2]) { + x = pPtr[2]; + y = pPtr[3]; + } else if (x < pPtr[0]) { + x = pPtr[0]; + y = pPtr[1]; + } + } + lower = (m1*pointPtr[0] + b1) > pointPtr[1]; + if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2])) + && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) { + intersections++; + } + } + + /* + * Compute the distance to the closest point, and see if that + * is the best distance seen so far. + */ + + dist = hypot(pointPtr[0] - x, pointPtr[1] - y); + if (dist < bestDist) { + bestDist = dist; + } + } + + /* + * We've processed all of the points. If the number of intersections + * is odd, the point is inside the polygon. + */ + + if (intersections & 0x1) { + return 0.0; + } + return bestDist; +} + +/* + *-------------------------------------------------------------- + * + * TkPolygonToArea -- + * + * Determine whether a polygon lies entirely inside, entirely + * outside, or overlapping a given rectangular area. + * + * Results: + * -1 is returned if the polygon given by polyPtr and numPoints + * is entirely outside the rectangle given by rectPtr. 0 is + * returned if the polygon overlaps the rectangle, and 1 is + * returned if the polygon is entirely inside the rectangle. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +int +TkPolygonToArea(polyPtr, numPoints, rectPtr) + double *polyPtr; /* Points to an array coordinates for + * closed polygon: x0, y0, x1, y1, ... + * The polygon may be self-intersecting. */ + int numPoints; /* Total number of points at *polyPtr. */ + register double *rectPtr; /* Points to coords for rectangle, in the + * order x1, y1, x2, y2. X1 and y1 must + * be lower-left corner. */ +{ + int state; /* State of all edges seen so far (-1 means + * outside, 1 means inside, won't ever be + * 0). */ + int count; + register double *pPtr; + + /* + * Iterate over all of the edges of the polygon and test them + * against the rectangle. Can quit as soon as the state becomes + * "intersecting". + */ + + state = TkLineToArea(polyPtr, polyPtr+2, rectPtr); + if (state == 0) { + return 0; + } + for (pPtr = polyPtr+2, count = numPoints-1; count >= 2; + pPtr += 2, count--) { + if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) { + return 0; + } + } + + /* + * If all of the edges were inside the rectangle we're done. + * If all of the edges were outside, then the rectangle could + * still intersect the polygon (if it's entirely enclosed). + * Call TkPolygonToPoint to figure this out. + */ + + if (state == 1) { + return 1; + } + if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) { + return 0; + } + return -1; +} + +/* + *-------------------------------------------------------------- + * + * TkOvalToPoint -- + * + * Computes the distance from a given point to a given + * oval, in canvas units. + * + * Results: + * The return value is 0 if the point given by *pointPtr is + * inside the oval. If the point isn't inside the + * oval then the return value is approximately the distance + * from the point to the oval. If the oval is filled, then + * anywhere in the interior is considered "inside"; if + * the oval isn't filled, then "inside" means only the area + * occupied by the outline. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + + /* ARGSUSED */ +double +TkOvalToPoint(ovalPtr, width, filled, pointPtr) + double ovalPtr[4]; /* Pointer to array of four coordinates + * (x1, y1, x2, y2) defining oval's bounding + * box. */ + double width; /* Width of outline for oval. */ + int filled; /* Non-zero means oval should be treated as + * filled; zero means only consider outline. */ + double pointPtr[2]; /* Coordinates of point. */ +{ + double xDelta, yDelta, scaledDistance, distToOutline, distToCenter; + double xDiam, yDiam; + + /* + * Compute the distance between the center of the oval and the + * point in question, using a coordinate system where the oval + * has been transformed to a circle with unit radius. + */ + + xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0); + yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0); + distToCenter = hypot(xDelta, yDelta); + scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0), + yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0)); + + + /* + * If the scaled distance is greater than 1 then it means no + * hit. Compute the distance from the point to the edge of + * the circle, then scale this distance back to the original + * coordinate system. + * + * Note: this distance isn't completely accurate. It's only + * an approximation, and it can overestimate the correct + * distance when the oval is eccentric. + */ + + if (scaledDistance > 1.0) { + return (distToCenter/scaledDistance) * (scaledDistance - 1.0); + } + + /* + * Scaled distance less than 1 means the point is inside the + * outer edge of the oval. If this is a filled oval, then we + * have a hit. Otherwise, do the same computation as above + * (scale back to original coordinate system), but also check + * to see if the point is within the width of the outline. + */ + + if (filled) { + return 0.0; + } + if (scaledDistance > 1E-10) { + distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance) + - width; + } else { + /* + * Avoid dividing by a very small number (it could cause an + * arithmetic overflow). This problem occurs if the point is + * very close to the center of the oval. + */ + + xDiam = ovalPtr[2] - ovalPtr[0]; + yDiam = ovalPtr[3] - ovalPtr[1]; + if (xDiam < yDiam) { + distToOutline = (xDiam - width)/2; + } else { + distToOutline = (yDiam - width)/2; + } + } + + if (distToOutline < 0.0) { + return 0.0; + } + return distToOutline; +} + +/* + *-------------------------------------------------------------- + * + * TkOvalToArea -- + * + * Determine whether an oval lies entirely inside, entirely + * outside, or overlapping a given rectangular area. + * + * Results: + * -1 is returned if the oval described by ovalPtr is entirely + * outside the rectangle given by rectPtr. 0 is returned if the + * oval overlaps the rectangle, and 1 is returned if the oval + * is entirely inside the rectangle. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +int +TkOvalToArea(ovalPtr, rectPtr) + register double *ovalPtr; /* Points to coordinates definining the + * bounding rectangle for the oval: x1, y1, + * x2, y2. X1 must be less than x2 and y1 + * less than y2. */ + register double *rectPtr; /* Points to coords for rectangle, in the + * order x1, y1, x2, y2. X1 and y1 must + * be lower-left corner. */ +{ + double centerX, centerY, radX, radY, deltaX, deltaY; + + /* + * First, see if oval is entirely inside rectangle or entirely + * outside rectangle. + */ + + if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2]) + && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) { + return 1; + } + if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2]) + || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) { + return -1; + } + + /* + * Next, go through the rectangle side by side. For each side + * of the rectangle, find the point on the side that is closest + * to the oval's center, and see if that point is inside the + * oval. If at least one such point is inside the oval, then + * the rectangle intersects the oval. + */ + + centerX = (ovalPtr[0] + ovalPtr[2])/2; + centerY = (ovalPtr[1] + ovalPtr[3])/2; + radX = (ovalPtr[2] - ovalPtr[0])/2; + radY = (ovalPtr[3] - ovalPtr[1])/2; + + deltaY = rectPtr[1] - centerY; + if (deltaY < 0.0) { + deltaY = centerY - rectPtr[3]; + if (deltaY < 0.0) { + deltaY = 0; + } + } + deltaY /= radY; + deltaY *= deltaY; + + /* + * Left side: + */ + + deltaX = (rectPtr[0] - centerX)/radX; + deltaX *= deltaX; + if ((deltaX + deltaY) <= 1.0) { + return 0; + } + + /* + * Right side: + */ + + deltaX = (rectPtr[2] - centerX)/radX; + deltaX *= deltaX; + if ((deltaX + deltaY) <= 1.0) { + return 0; + } + + deltaX = rectPtr[0] - centerX; + if (deltaX < 0.0) { + deltaX = centerX - rectPtr[2]; + if (deltaX < 0.0) { + deltaX = 0; + } + } + deltaX /= radX; + deltaX *= deltaX; + + /* + * Bottom side: + */ + + deltaY = (rectPtr[1] - centerY)/radY; + deltaY *= deltaY; + if ((deltaX + deltaY) < 1.0) { + return 0; + } + + /* + * Top side: + */ + + deltaY = (rectPtr[3] - centerY)/radY; + deltaY *= deltaY; + if ((deltaX + deltaY) < 1.0) { + return 0; + } + + return -1; +} + +/* + *-------------------------------------------------------------- + * + * TkIncludePoint -- + * + * Given a point and a generic canvas item header, expand + * the item's bounding box if needed to include the point. + * + * Results: + * None. + * + * Side effects: + * The boudn. + * + *-------------------------------------------------------------- + */ + + /* ARGSUSED */ +void +TkIncludePoint(itemPtr, pointPtr) + register Tk_Item *itemPtr; /* Item whose bounding box is + * being calculated. */ + double *pointPtr; /* Address of two doubles giving + * x and y coordinates of point. */ +{ + int tmp; + + tmp = (int) (pointPtr[0] + 0.5); + if (tmp < itemPtr->x1) { + itemPtr->x1 = tmp; + } + if (tmp > itemPtr->x2) { + itemPtr->x2 = tmp; + } + tmp = (int) (pointPtr[1] + 0.5); + if (tmp < itemPtr->y1) { + itemPtr->y1 = tmp; + } + if (tmp > itemPtr->y2) { + itemPtr->y2 = tmp; + } +} + +/* + *-------------------------------------------------------------- + * + * TkBezierScreenPoints -- + * + * Given four control points, create a larger set of XPoints + * for a Bezier spline based on the points. + * + * Results: + * The array at *xPointPtr gets filled in with numSteps XPoints + * corresponding to the Bezier spline defined by the four + * control points. Note: no output point is generated for the + * first input point, but an output point *is* generated for + * the last input point. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +void +TkBezierScreenPoints(canvas, control, numSteps, xPointPtr) + Tk_Canvas canvas; /* Canvas in which curve is to be + * drawn. */ + double control[]; /* Array of coordinates for four + * control points: x0, y0, x1, y1, + * ... x3 y3. */ + int numSteps; /* Number of curve points to + * generate. */ + register XPoint *xPointPtr; /* Where to put new points. */ +{ + int i; + double u, u2, u3, t, t2, t3; + + for (i = 1; i <= numSteps; i++, xPointPtr++) { + t = ((double) i)/((double) numSteps); + t2 = t*t; + t3 = t2*t; + u = 1.0 - t; + u2 = u*u; + u3 = u2*u; + Tk_CanvasDrawableCoords(canvas, + (control[0]*u3 + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + + control[6]*t3), + (control[1]*u3 + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + + control[7]*t3), + &xPointPtr->x, &xPointPtr->y); + } +} + +/* + *-------------------------------------------------------------- + * + * TkBezierPoints -- + * + * Given four control points, create a larger set of points + * for a Bezier spline based on the points. + * + * Results: + * The array at *coordPtr gets filled in with 2*numSteps + * coordinates, which correspond to the Bezier spline defined + * by the four control points. Note: no output point is + * generated for the first input point, but an output point + * *is* generated for the last input point. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +void +TkBezierPoints(control, numSteps, coordPtr) + double control[]; /* Array of coordinates for four + * control points: x0, y0, x1, y1, + * ... x3 y3. */ + int numSteps; /* Number of curve points to + * generate. */ + register double *coordPtr; /* Where to put new points. */ +{ + int i; + double u, u2, u3, t, t2, t3; + + for (i = 1; i <= numSteps; i++, coordPtr += 2) { + t = ((double) i)/((double) numSteps); + t2 = t*t; + t3 = t2*t; + u = 1.0 - t; + u2 = u*u; + u3 = u2*u; + coordPtr[0] = control[0]*u3 + + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3; + coordPtr[1] = control[1]*u3 + + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3; + } +} + +/* + *-------------------------------------------------------------- + * + * TkMakeBezierCurve -- + * + * Given a set of points, create a new set of points that fit + * parabolic splines to the line segments connecting the original + * points. Produces output points in either of two forms. + * + * Note: in spite of this procedure's name, it does *not* generate + * Bezier curves. Since only three control points are used for + * each curve segment, not four, the curves are actually just + * parabolic. + * + * Results: + * Either or both of the xPoints or dblPoints arrays are filled + * in. The return value is the number of points placed in the + * arrays. Note: if the first and last points are the same, then + * a closed curve is generated. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +int +TkMakeBezierCurve(canvas, pointPtr, numPoints, numSteps, xPoints, dblPoints) + Tk_Canvas canvas; /* Canvas in which curve is to be + * drawn. */ + double *pointPtr; /* Array of input coordinates: x0, + * y0, x1, y1, etc.. */ + int numPoints; /* Number of points at pointPtr. */ + int numSteps; /* Number of steps to use for each + * spline segments (determines + * smoothness of curve). */ + XPoint xPoints[]; /* Array of XPoints to fill in (e.g. + * for display. NULL means don't + * fill in any XPoints. */ + double dblPoints[]; /* Array of points to fill in as + * doubles, in the form x0, y0, + * x1, y1, .... NULL means don't + * fill in anything in this form. + * Caller must make sure that this + * array has enough space. */ +{ + int closed, outputPoints, i; + int numCoords = numPoints*2; + double control[8]; + + /* + * If the curve is a closed one then generate a special spline + * that spans the last points and the first ones. Otherwise + * just put the first point into the output. + */ + + outputPoints = 0; + if ((pointPtr[0] == pointPtr[numCoords-2]) + && (pointPtr[1] == pointPtr[numCoords-1])) { + closed = 1; + control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0]; + control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1]; + control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0]; + control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1]; + control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2]; + control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3]; + control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; + control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; + if (xPoints != NULL) { + Tk_CanvasDrawableCoords(canvas, control[0], control[1], + &xPoints->x, &xPoints->y); + TkBezierScreenPoints(canvas, control, numSteps, xPoints+1); + xPoints += numSteps+1; + } + if (dblPoints != NULL) { + dblPoints[0] = control[0]; + dblPoints[1] = control[1]; + TkBezierPoints(control, numSteps, dblPoints+2); + dblPoints += 2*(numSteps+1); + } + outputPoints += numSteps+1; + } else { + closed = 0; + if (xPoints != NULL) { + Tk_CanvasDrawableCoords(canvas, pointPtr[0], pointPtr[1], + &xPoints->x, &xPoints->y); + xPoints += 1; + } + if (dblPoints != NULL) { + dblPoints[0] = pointPtr[0]; + dblPoints[1] = pointPtr[1]; + dblPoints += 2; + } + outputPoints += 1; + } + + for (i = 2; i < numPoints; i++, pointPtr += 2) { + /* + * Set up the first two control points. This is done + * differently for the first spline of an open curve + * than for other cases. + */ + + if ((i == 2) && !closed) { + control[0] = pointPtr[0]; + control[1] = pointPtr[1]; + control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2]; + control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3]; + } else { + control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; + control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; + control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2]; + control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3]; + } + + /* + * Set up the last two control points. This is done + * differently for the last spline of an open curve + * than for other cases. + */ + + if ((i == (numPoints-1)) && !closed) { + control[4] = .667*pointPtr[2] + .333*pointPtr[4]; + control[5] = .667*pointPtr[3] + .333*pointPtr[5]; + control[6] = pointPtr[4]; + control[7] = pointPtr[5]; + } else { + control[4] = .833*pointPtr[2] + .167*pointPtr[4]; + control[5] = .833*pointPtr[3] + .167*pointPtr[5]; + control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4]; + control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5]; + } + + /* + * If the first two points coincide, or if the last + * two points coincide, then generate a single + * straight-line segment by outputting the last control + * point. + */ + + if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3])) + || ((pointPtr[2] == pointPtr[4]) + && (pointPtr[3] == pointPtr[5]))) { + if (xPoints != NULL) { + Tk_CanvasDrawableCoords(canvas, control[6], control[7], + &xPoints[0].x, &xPoints[0].y); + xPoints++; + } + if (dblPoints != NULL) { + dblPoints[0] = control[6]; + dblPoints[1] = control[7]; + dblPoints += 2; + } + outputPoints += 1; + continue; + } + + /* + * Generate a Bezier spline using the control points. + */ + + + if (xPoints != NULL) { + TkBezierScreenPoints(canvas, control, numSteps, xPoints); + xPoints += numSteps; + } + if (dblPoints != NULL) { + TkBezierPoints(control, numSteps, dblPoints); + dblPoints += 2*numSteps; + } + outputPoints += numSteps; + } + return outputPoints; +} + +/* + *-------------------------------------------------------------- + * + * TkMakeBezierPostscript -- + * + * This procedure generates Postscript commands that create + * a path corresponding to a given Bezier curve. + * + * Results: + * None. Postscript commands to generate the path are appended + * to interp->result. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +void +TkMakeBezierPostscript(interp, canvas, pointPtr, numPoints) + Tcl_Interp *interp; /* Interpreter in whose result the + * Postscript is to be stored. */ + Tk_Canvas canvas; /* Canvas widget for which the + * Postscript is being generated. */ + double *pointPtr; /* Array of input coordinates: x0, + * y0, x1, y1, etc.. */ + int numPoints; /* Number of points at pointPtr. */ +{ + int closed, i; + int numCoords = numPoints*2; + double control[8]; + char buffer[200]; + + /* + * If the curve is a closed one then generate a special spline + * that spans the last points and the first ones. Otherwise + * just put the first point into the path. + */ + + if ((pointPtr[0] == pointPtr[numCoords-2]) + && (pointPtr[1] == pointPtr[numCoords-1])) { + closed = 1; + control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0]; + control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1]; + control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0]; + control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1]; + control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2]; + control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3]; + control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; + control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; + sprintf(buffer, "%.15g %.15g moveto\n%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", + control[0], Tk_CanvasPsY(canvas, control[1]), + control[2], Tk_CanvasPsY(canvas, control[3]), + control[4], Tk_CanvasPsY(canvas, control[5]), + control[6], Tk_CanvasPsY(canvas, control[7])); + } else { + closed = 0; + control[6] = pointPtr[0]; + control[7] = pointPtr[1]; + sprintf(buffer, "%.15g %.15g moveto\n", + control[6], Tk_CanvasPsY(canvas, control[7])); + } + Tcl_AppendResult(interp, buffer, (char *) NULL); + + /* + * Cycle through all the remaining points in the curve, generating + * a curve section for each vertex in the linear path. + */ + + for (i = numPoints-2, pointPtr += 2; i > 0; i--, pointPtr += 2) { + control[2] = 0.333*control[6] + 0.667*pointPtr[0]; + control[3] = 0.333*control[7] + 0.667*pointPtr[1]; + + /* + * Set up the last two control points. This is done + * differently for the last spline of an open curve + * than for other cases. + */ + + if ((i == 1) && !closed) { + control[6] = pointPtr[2]; + control[7] = pointPtr[3]; + } else { + control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2]; + control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3]; + } + control[4] = 0.333*control[6] + 0.667*pointPtr[0]; + control[5] = 0.333*control[7] + 0.667*pointPtr[1]; + + sprintf(buffer, "%.15g %.15g %.15g %.15g %.15g %.15g curveto\n", + control[2], Tk_CanvasPsY(canvas, control[3]), + control[4], Tk_CanvasPsY(canvas, control[5]), + control[6], Tk_CanvasPsY(canvas, control[7])); + Tcl_AppendResult(interp, buffer, (char *) NULL); + } +} + +/* + *-------------------------------------------------------------- + * + * TkGetMiterPoints -- + * + * Given three points forming an angle, compute the + * coordinates of the inside and outside points of + * the mitered corner formed by a line of a given + * width at that angle. + * + * Results: + * If the angle formed by the three points is less than + * 11 degrees then 0 is returned and m1 and m2 aren't + * modified. Otherwise 1 is returned and the points at + * m1 and m2 are filled in with the positions of the points + * of the mitered corner. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +int +TkGetMiterPoints(p1, p2, p3, width, m1, m2) + double p1[]; /* Points to x- and y-coordinates of point + * before vertex. */ + double p2[]; /* Points to x- and y-coordinates of vertex + * for mitered joint. */ + double p3[]; /* Points to x- and y-coordinates of point + * after vertex. */ + double width; /* Width of line. */ + double m1[]; /* Points to place to put "left" vertex + * point (see as you face from p1 to p2). */ + double m2[]; /* Points to place to put "right" vertex + * point. */ +{ + double theta1; /* Angle of segment p2-p1. */ + double theta2; /* Angle of segment p2-p3. */ + double theta; /* Angle between line segments (angle + * of joint). */ + double theta3; /* Angle that bisects theta1 and + * theta2 and points to m1. */ + double dist; /* Distance of miter points from p2. */ + double deltaX, deltaY; /* X and y offsets cooresponding to + * dist (fudge factors for bounding + * box). */ + double p1x, p1y, p2x, p2y, p3x, p3y; + static double elevenDegrees = (11.0*2.0*PI)/360.0; + + /* + * Round the coordinates to integers to mimic what happens when the + * line segments are displayed; without this code, the bounding box + * of a mitered line can be miscomputed greatly. + */ + + p1x = floor(p1[0]+0.5); + p1y = floor(p1[1]+0.5); + p2x = floor(p2[0]+0.5); + p2y = floor(p2[1]+0.5); + p3x = floor(p3[0]+0.5); + p3y = floor(p3[1]+0.5); + + if (p2y == p1y) { + theta1 = (p2x < p1x) ? 0 : PI; + } else if (p2x == p1x) { + theta1 = (p2y < p1y) ? PI/2.0 : -PI/2.0; + } else { + theta1 = atan2(p1y - p2y, p1x - p2x); + } + if (p3y == p2y) { + theta2 = (p3x > p2x) ? 0 : PI; + } else if (p3x == p2x) { + theta2 = (p3y > p2y) ? PI/2.0 : -PI/2.0; + } else { + theta2 = atan2(p3y - p2y, p3x - p2x); + } + theta = theta1 - theta2; + if (theta > PI) { + theta -= 2*PI; + } else if (theta < -PI) { + theta += 2*PI; + } + if ((theta < elevenDegrees) && (theta > -elevenDegrees)) { + return 0; + } + dist = 0.5*width/sin(0.5*theta); + if (dist < 0.0) { + dist = -dist; + } + + /* + * Compute theta3 (make sure that it points to the left when + * looking from p1 to p2). + */ + + theta3 = (theta1 + theta2)/2.0; + if (sin(theta3 - (theta1 + PI)) < 0.0) { + theta3 += PI; + } + deltaX = dist*cos(theta3); + m1[0] = p2x + deltaX; + m2[0] = p2x - deltaX; + deltaY = dist*sin(theta3); + m1[1] = p2y + deltaY; + m2[1] = p2y - deltaY; + return 1; +} + +/* + *-------------------------------------------------------------- + * + * TkGetButtPoints -- + * + * Given two points forming a line segment, compute the + * coordinates of two endpoints of a rectangle formed by + * bloating the line segment until it is width units wide. + * + * Results: + * There is no return value. M1 and m2 are filled in to + * correspond to m1 and m2 in the diagram below: + * + * ----------------* m1 + * | + * p1 *---------------* p2 + * | + * ----------------* m2 + * + * M1 and m2 will be W units apart, with p2 centered between + * them and m1-m2 perpendicular to p1-p2. However, if + * "project" is true then m1 and m2 will be as follows: + * + * -------------------* m1 + * p2 | + * p1 *---------------* | + * | + * -------------------* m2 + * + * In this case p2 will be width/2 units from the segment m1-m2. + * + * Side effects: + * None. + * + *-------------------------------------------------------------- + */ + +void +TkGetButtPoints(p1, p2, width, project, m1, m2) + double p1[]; /* Points to x- and y-coordinates of point + * before vertex. */ + double p2[]; /* Points to x- and y-coordinates of vertex + * for mitered joint. */ + double width; /* Width of line. */ + int project; /* Non-zero means project p2 by an additional + * width/2 before computing m1 and m2. */ + double m1[]; /* Points to place to put "left" result + * point, as you face from p1 to p2. */ + double m2[]; /* Points to place to put "right" result + * point. */ +{ + double length; /* Length of p1-p2 segment. */ + double deltaX, deltaY; /* Increments in coords. */ + + width *= 0.5; + length = hypot(p2[0] - p1[0], p2[1] - p1[1]); + if (length == 0.0) { + m1[0] = m2[0] = p2[0]; + m1[1] = m2[1] = p2[1]; + } else { + deltaX = -width * (p2[1] - p1[1]) / length; + deltaY = width * (p2[0] - p1[0]) / length; + m1[0] = p2[0] + deltaX; + m2[0] = p2[0] - deltaX; + m1[1] = p2[1] + deltaY; + m2[1] = p2[1] - deltaY; + if (project) { + m1[0] += deltaY; + m2[0] += deltaY; + m1[1] -= deltaX; + m2[1] -= deltaX; + } + } +} |