graphicslib.java

来自「用applet实现很多应用小程序」· Java 代码 · 共 791 行 · 第 1/3 页

package prefuse.util;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Shape;
import java.awt.Stroke;
import java.awt.geom.AffineTransform;
import java.awt.geom.Ellipse2D;
import java.awt.geom.GeneralPath;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.geom.RectangularShape;
import java.awt.geom.RoundRectangle2D;

import prefuse.render.AbstractShapeRenderer;
import prefuse.visual.VisualItem;

/**
 * Library of useful computer graphics routines such as geometry routines
 * for computing the intersection of different shapes and rendering methods
 * for computing bounds and performing optimized drawing.
 * 
 * @author <a href="http://jheer.org">jeffrey heer</a>
 */
public class GraphicsLib {

    /** Indicates no intersection between shapes */
    public static final int NO_INTERSECTION = 0;
    /** Indicates intersection between shapes */
    public static final int COINCIDENT      = -1;
    /** Indicates two lines are parallel */
    public static final int PARALLEL        = -2;
    
    /**
     * Compute the intersection of two line segments.
     * @param a the first line segment
     * @param b the second line segment
     * @param intersect a Point in which to store the intersection point
     * @return the intersection code. One of {@link #NO_INTERSECTION},
     * {@link #COINCIDENT}, or {@link #PARALLEL}.
     */
    public static int intersectLineLine(Line2D a, Line2D b, Point2D intersect) {
        double a1x = a.getX1(), a1y = a.getY1();
        double a2x = a.getX2(), a2y = a.getY2();
        double b1x = b.getX1(), b1y = b.getY1();
        double b2x = b.getX2(), b2y = b.getY2();
        return intersectLineLine(a1x,a1y,a2x,a2y,b1x,b1y,b2x,b2y,intersect);
    }
    
    /**
     * Compute the intersection of two line segments.
     * @param a1x the x-coordinate of the first endpoint of the first line
     * @param a1y the y-coordinate of the first endpoint of the first line
     * @param a2x the x-coordinate of the second endpoint of the first line
     * @param a2y the y-coordinate of the second endpoint of the first line
     * @param b1x the x-coordinate of the first endpoint of the second line
     * @param b1y the y-coordinate of the first endpoint of the second line
     * @param b2x the x-coordinate of the second endpoint of the second line
     * @param b2y the y-coordinate of the second endpoint of the second line
     * @param intersect a Point in which to store the intersection point
     * @return the intersection code. One of {@link #NO_INTERSECTION},
     * {@link #COINCIDENT}, or {@link #PARALLEL}.
     */
    public static int intersectLineLine(double a1x, double a1y, double a2x,
        double a2y, double b1x, double b1y, double b2x, double b2y, 
        Point2D intersect)
    {
        double ua_t = (b2x-b1x)*(a1y-b1y)-(b2y-b1y)*(a1x-b1x);
        double ub_t = (a2x-a1x)*(a1y-b1y)-(a2y-a1y)*(a1x-b1x);
        double u_b  = (b2y-b1y)*(a2x-a1x)-(b2x-b1x)*(a2y-a1y);

        if ( u_b != 0 ) {
            double ua = ua_t / u_b;
            double ub = ub_t / u_b;

            if ( 0 <= ua && ua <= 1 && 0 <= ub && ub <= 1 ) {
                intersect.setLocation(a1x+ua*(a2x-a1x), a1y+ua*(a2y-a1y));
                return 1;
            } else {
                return NO_INTERSECTION;
            }
        } else {
            return ( ua_t == 0 || ub_t == 0 ? COINCIDENT : PARALLEL );
        }
    }

    /**
     * Compute the intersection of a line and a rectangle.
     * @param a1 the first endpoint of the line
     * @param a2 the second endpoint of the line
     * @param r the rectangle
     * @param pts a length 2 or greater array of points in which to store
     * the results 
     * @return the intersection code. One of {@link #NO_INTERSECTION},
     * {@link #COINCIDENT}, or {@link #PARALLEL}.
     */
    public static int intersectLineRectangle(Point2D a1, Point2D a2, Rectangle2D r, Point2D[] pts) {
        double a1x = a1.getX(), a1y = a1.getY();
        double a2x = a2.getX(), a2y = a2.getY();
        double mxx = r.getMaxX(), mxy = r.getMaxY();
        double mnx = r.getMinX(), mny = r.getMinY();
        
        if ( pts[0] == null ) pts[0] = new Point2D.Double();
        if ( pts[1] == null ) pts[1] = new Point2D.Double();
        
        int i = 0;
        if ( intersectLineLine(mnx,mny,mxx,mny,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( intersectLineLine(mxx,mny,mxx,mxy,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( i == 2 ) return i;
        if ( intersectLineLine(mxx,mxy,mnx,mxy,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( i == 2 ) return i;
        if ( intersectLineLine(mnx,mxy,mnx,mny,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        return i;
    }

    /**
     * Compute the intersection of a line and a rectangle.
     * @param l the line
     * @param r the rectangle
     * @param pts a length 2 or greater array of points in which to store
     * the results 
     * @return the intersection code. One of {@link #NO_INTERSECTION},
     * {@link #COINCIDENT}, or {@link #PARALLEL}.
     */
    public static int intersectLineRectangle(Line2D l, Rectangle2D r, Point2D[] pts) {
        double a1x = l.getX1(), a1y = l.getY1();
        double a2x = l.getX2(), a2y = l.getY2();
        double mxx = r.getMaxX(), mxy = r.getMaxY();
        double mnx = r.getMinX(), mny = r.getMinY();
        
        if ( pts[0] == null ) pts[0] = new Point2D.Double();
        if ( pts[1] == null ) pts[1] = new Point2D.Double();
        
        int i = 0;
        if ( intersectLineLine(mnx,mny,mxx,mny,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( intersectLineLine(mxx,mny,mxx,mxy,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( i == 2 ) return i;
        if ( intersectLineLine(mxx,mxy,mnx,mxy,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        if ( i == 2 ) return i;
        if ( intersectLineLine(mnx,mxy,mnx,mny,a1x,a1y,a2x,a2y,pts[i]) > 0 ) i++;
        return i;
    }
    
    /**
     * Computes the 2D convex hull of a set of points using Graham's
     * scanning algorithm. The algorithm has been implemented as described
     * in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
     * 
     * The running time of this algorithm is O(n log n), where n is
     * the number of input points.
     * 
     * @param pts the input points in [x0,y0,x1,y1,...] order
     * @param len the length of the pts array to consider (2 * #points)
     * @return the convex hull of the input points
     */
    public static double[] convexHull(double[] pts, int len) {
        if (len < 6) {
            throw new IllegalArgumentException(
                    "Input must have at least 3 points");
        }
        int plen = len/2-1;
        float[] angles = new float[plen];
        int[] idx    = new int[plen];
        int[] stack  = new int[len/2];
        return convexHull(pts, len, angles, idx, stack);
    }
    
    /**
     * Computes the 2D convex hull of a set of points using Graham's
     * scanning algorithm. The algorithm has been implemented as described
     * in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
     * 
     * The running time of this algorithm is O(n log n), where n is
     * the number of input points.
     * 
     * @param pts
     * @return the convex hull of the input points
     */
    public static double[] convexHull(double[] pts, int len, 
            float[] angles, int[] idx, int[] stack)
    {
        // check arguments
        int plen = len/2 - 1;
        if (len < 6) {
            throw new IllegalArgumentException(
                    "Input must have at least 3 points");
        }
        if (angles.length < plen || idx.length < plen || stack.length < len/2) {
            throw new IllegalArgumentException(
                    "Pre-allocated data structure too small");
        }
        
        int i0 = 0;
        // find the starting ref point: leftmost point with the minimum y coord
        for ( int i=2; i < len; i += 2 ) {
            if ( pts[i+1] < pts[i0+1] ) {
                i0 = i;
            } else if ( pts[i+1] == pts[i0+1] ) {
                i0 = (pts[i] < pts[i0] ? i : i0);
            }
        }
        
        // calculate polar angles from ref point and sort
        for ( int i=0, j=0; i < len; i+=2 ) {
            if ( i == i0 ) continue;
            angles[j] = (float)Math.atan2(pts[i+1]-pts[i0+1], pts[i]-pts[i0]);
            idx[j++]  = i;
        }
        ArrayLib.sort(angles,idx,plen);
        
        // toss out duplicated angles
        float angle = angles[0];
        int ti = 0, tj = idx[0];
        for ( int i=1; i<plen; i++ ) {
            int j = idx[i];
            if ( angle == angles[i] ) {
                // keep whichever angle corresponds to the most distant
                // point from the reference point
                double x1 = pts[tj]   - pts[i0];
                double y1 = pts[tj+1] - pts[i0+1];
                double x2 = pts[j]    - pts[i0];
                double y2 = pts[j+1]  - pts[i0+1];
                double d1 = x1*x1 + y1*y1;
                double d2 = x2*x2 + y2*y2;
                if ( d1 >= d2 ) {
                    idx[i] = -1;
                } else {
                    idx[ti] = -1;
                    angle = angles[i];
                    ti = i;
                    tj = j;
                }
            } else {
                angle = angles[i];
                ti = i;
                tj = j;
            }
        }
        
        // initialize our stack
        int sp = 0;
        stack[sp++] = i0;
        int j = 0;
        for ( int k=0; k<2; j++ ) {
            if ( idx[j] != -1 ) {
                stack[sp++] = idx[j];
                k++;
            }
        }
        
        // do graham's scan
        for ( ; j < plen; j++ ) {
            if ( idx[j] == -1 ) continue; // skip tossed out points
            while ( isNonLeft(i0, stack[sp-2], stack[sp-1], idx[j], pts) ) {
                sp--;
            }
            stack[sp++] = idx[j];
        }

        // construct the hull
        double[] hull = new double[2*sp];
        for ( int i=0; i<sp; i++ ) {