tktrig.c

linux系统下的音频通信

/* 
 * 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]);