tkTrig.c revision 3f54fd611f536639ec30dd53c48e5ec1897cc7d9
/*
* 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.23 96/02/15 18:53:05
*/
#include "tkInt.h"
#include "tkCanvas.h"
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#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
{
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.
*/
/*
* Vertical edge.
*/
x = end1Ptr[0];
} else {
}
/*
* Horizontal edge.
*/
y = end1Ptr[1];
} else {
}
} else {
/*
* 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.
*/
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.
*/
}
/*
*--------------------------------------------------------------
*
* 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
* of line. */
* of line. */
* order x1, y1, x2, y2. X1 must be no
* larger than x2, and y1 no larger than y2. */
{
/*
* First check the two points individually to see whether they
* are inside the rectangle or not.
*/
return 0;
}
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.
*/
/*
* Vertical line.
*/
return 0;
}
/*
* Horizontal line.
*/
return 0;
}
} else {
/*
* Diagonal line. Compute slope of line and use
* for intersection checks against each of the
* sides of the rectangle: left, right, bottom, top.
*/
} else {
}
/*
* Left edge.
*/
return 0;
}
/*
* Right edge.
*/
return 0;
}
/*
* Bottom edge.
*/
} else {
}
return 0;
}
/*
* Top edge.
*/
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
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. */
{
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. */
inside = -1;
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;
/*
* If rounding is done around the first point of the edge
* then test a circular region around the point with the
* area.
*/
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.
*/
} else {
/*
* 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.
*/
return 0;
}
changedMiterToBevel = 0;
}
}
if (count == 2) {
changedMiterToBevel = 1;
poly+6);
}
} else {
}
return 0;
}
}
/*
* If caps are rounded, check the cap around the final point
* of the line.
*/
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
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;
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.
*/
/*
* Vertical edge.
*/
x = pPtr[0];
} else {
}
/*
* Horizontal edge.
*/
y = pPtr[1];
}
} else {
}
}
} else {
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.
*/
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];
}
}
}
}
/*
* Compute the distance to the closest point, and see if that
* is the best distance seen so far.
*/
}
}
/*
* 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
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".
*/
if (state == 0) {
return 0;
}
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;
}
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
* (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. */
{
/*
* 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.
*/
/*
* 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) {
}
/*
* 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) {
- 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.
*/
} else {
}
}
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
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. */
{
/*
* First, see if oval is entirely inside rectangle or entirely
* outside rectangle.
*/
return 1;
}
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.
*/
if (deltaY < 0.0) {
if (deltaY < 0.0) {
deltaY = 0;
}
}
/*
* Left side:
*/
return 0;
}
/*
* Right side:
*/
return 0;
}
if (deltaX < 0.0) {
if (deltaX < 0.0) {
deltaX = 0;
}
}
/*
* Bottom side:
*/
return 0;
}
/*
* Top side:
*/
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
* being calculated. */
double *pointPtr; /* Address of two doubles giving
* x and y coordinates of point. */
{
int 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
* drawn. */
double control[]; /* Array of coordinates for four
* control points: x0, y0, x1, y1,
* ... x3 y3. */
int numSteps; /* Number of curve points to
* generate. */
{
int i;
t = ((double) i)/((double) numSteps);
t2 = t*t;
u = 1.0 - t;
u2 = u*u;
}
}
/*
*--------------------------------------------------------------
*
* 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
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;
t = ((double) i)/((double) numSteps);
t2 = t*t;
u = 1.0 - t;
u2 = u*u;
}
}
/*
*--------------------------------------------------------------
*
* TkMakeBezierCurve --
*
* Given a set of points, create a new set of points that
* fit Bezier splines to the line segments connecting the
* original points. Produces output points in either of two
* forms.
*
* 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
* 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). */
* 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;
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;
closed = 1;
}
}
} else {
closed = 0;
xPoints += 1;
}
dblPoints += 2;
}
outputPoints += 1;
}
/*
* 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) {
} else {
}
/*
* Set up the last two control points. This is done
* differently for the last spline of an open curve
* than for other cases.
*/
} else {
}
/*
* 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.
*/
xPoints++;
}
dblPoints += 2;
}
outputPoints += 1;
continue;
}
/*
* Generate a Bezier spline using the control points.
*/
}
}
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
* Postscript is to be stored. */
* 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;
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.
*/
closed = 1;
} else {
closed = 0;
}
/*
* Cycle through all the remaining points in the curve, generating
* a curve section for each vertex in the linear path.
*/
/*
* 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) {
} else {
}
}
}
/*
*--------------------------------------------------------------
*
* 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
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. */
* dist (fudge factors for bounding
* box). */
} else {
}
} else {
}
}
return 0;
}
if (dist < 0.0) {
}
/*
* Compute theta3 (make sure that it points to the left when
* looking from p1 to p2).
*/
}
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
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. */
width *= 0.5;
if (length == 0.0) {
} else {
if (project) {
}
}
}