/*  * 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. * *-------------------------------------------------------------- */doubleTkLineToPoint(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. * *-------------------------------------------------------------- */intTkLineToArea(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 */intTkThickPolyLineToArea(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. * *-------------------------------------------------------------- */doubleTkPolygonToPoint(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]);