Java/2D Graphics GUI/Geometry

Материал из Java эксперт
Перейти к: навигация, поиск

Collection of geometry utility methods

 
/*
 * (C) 2004 - Geotechnical Software Services
 * 
 * This code is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public 
 * License as published by the Free Software Foundation; either 
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This code is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public 
 * License along with this program; if not, write to the Free 
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, 
 * MA  02111-1307, USA.
 */
//package no.geosoft.cc.geometry;

/**
 * Collection of geometry utility methods. All methods are static.
 * 
 * @author 
 */   
public final class Geometry
{
  /**
   * Return true if c is between a and b.
   */
  private static boolean isBetween (int a, int b, int c)
  {
    return b > a ? c >= a && c <= b : c >= b && c <= a;
  }

  
  /**
   * Return true if c is between a and b.
   */
  private static boolean isBetween (double a, double b, double c)
  {
    return b > a ? c >= a && c <= b : c >= b && c <= a;
  }

  
  /**
   * Check if two double precision numbers are "equal", i.e. close enough
   * to a given limit.
   * 
   * @param a      First number to check
   * @param b      Second number to check   
   * @param limit  The definition of "equal".
   * @return       True if the twho numbers are "equal", false otherwise
   */
  private static boolean equals (double a, double b, double limit)
  {
    return Math.abs (a - b) < limit;
  }

  
  /**
   * Check if two double precision numbers are "equal", i.e. close enough
   * to a prespecified limit.
   * 
   * @param a  First number to check
   * @param b  Second number to check   
   * @return   True if the twho numbers are "equal", false otherwise
   */
  private static boolean equals (double a, double b)
  {
    return equals (a, b, 1.0e-5);
  }
  
  
  /**
   * Return smallest of four numbers.
   * 
   * @param a  First number to find smallest among.
   * @param b  Second number to find smallest among.
   * @param c  Third number to find smallest among.
   * @param d  Fourth number to find smallest among.   
   * @return   Smallest of a, b, c and d.
   */
  private static double min (double a, double b, double c, double d)
  {
    return Math.min (Math.min (a, b), Math.min (c, d));
  }

  
  /**
   * Return largest of four numbers.
   * 
   * @param a  First number to find largest among.
   * @param b  Second number to find largest among.
   * @param c  Third number to find largest among.
   * @param d  Fourth number to find largest among.   
   * @return   Largest of a, b, c and d.
   */
  private static double max (double a, double b, double c, double d)
  {
    return Math.max (Math.max (a, b), Math.max (c, d));
  }

  
  /**
   * Check if a specified point is inside a specified rectangle.
   * 
   * @param x0, y0, x1, y1  Upper left and lower right corner of rectangle
   *                        (inclusive)
   * @param x,y             Point to check.
   * @return                True if the point is inside the rectangle,
   *                        false otherwise.
   */
  public static boolean isPointInsideRectangle (int x0, int y0, int x1, int y1,
                                                int x, int y)
  {
    return x >= x0 && x < x1 && y >= y0 && y < y1;
  }
  
  
  
  /**
   * Check if a given point is inside a given (complex) polygon.
   * 
   * @param x, y            Polygon.
   * @param pointX, pointY  Point to check.
   * @return  True if the given point is inside the polygon, false otherwise.
   */
  public static boolean isPointInsidePolygon (double[] x, double[] y,
                                              double pointX, double pointY)
  {
    boolean  isInside = false;
    int nPoints = x.length;
    
    int j = 0;
    for (int i = 0; i < nPoints; i++) {
      j++;
      if (j == nPoints) j = 0;
      
      if (y[i] < pointY && y[j] >= pointY || y[j] < pointY && y[i] >= pointY) {
        if (x[i] + (pointY - y[i]) / (y[j] - y[i]) * (x[j] - x[i]) < pointX) {
          isInside = !isInside;
        }
      }
    }
    
    return isInside;
  }

  
  /**
   * Check if a given point is inside a given polygon. Integer domain.
   *
   * @param x, y            Polygon.
   * @param pointX, pointY  Point to check.
   * @return  True if the given point is inside the polygon, false otherwise.
   */
  public static boolean isPointInsidePolygon (int[] x, int[] y,
                                              int pointX, int pointY)
  {
    boolean  isInside = false;
    int nPoints = x.length;
    
    int j = 0;
    for (int i = 0; i < nPoints; i++) {
      j++;
      if (j == nPoints) j = 0;
      
      if (y[i] < pointY && y[j] >= pointY || y[j] < pointY && y[i] >= pointY) {
        if (x[i] + (double) (pointY - y[i]) / (double) (y[j] - y[i]) *
            (x[j] - x[i]) < pointX) {
          isInside = !isInside;
        }
      }
    }
    
    return isInside;
  }
  
  
  
  /**
   * Find the point on the line p0,p1 [x,y,z] a given fraction from p0.
   * Fraction of 0.0 whould give back p0, 1.0 give back p1, 0.5 returns
   * midpoint of line p0,p1 and so on. F
   * raction can be >1 and it can be negative to return any point on the
   * line specified by p0,p1.
   * 
   * @param p0              First coordinale of line [x,y,z].
   * @param p0              Second coordinale of line [x,y,z].   
   * @param fractionFromP0  Point we are looking for coordinates of
   * @param p               Coordinate of point we are looking for
   */
  public static double[] computePointOnLine (double[] p0, double[] p1, 
                                             double fractionFromP0)
  {
    double[] p = new double[3];
    p[0] = p0[0] + fractionFromP0 * (p1[0] - p0[0]);
    p[1] = p0[1] + fractionFromP0 * (p1[1] - p0[1]);
    p[2] = p0[2] + fractionFromP0 * (p1[2] - p0[2]);  
    return p;
  }
  

  /**
   * Find the point on the line defined by x0,y0,x1,y1 a given fraction
   * from x0,y0. 2D version of method above..
   * 
   * @param  x0, y0         First point defining the line
   * @param  x1, y1         Second point defining the line
   * @param  fractionFrom0  Distance from (x0,y0)
   * @return x, y           Coordinate of point we are looking for
   */
  public static double[] computePointOnLine (double x0, double y0,
                                             double x1, double y1,
                                             double fractionFrom0)
  {
    double[] p0 = {x0, y0, 0.0};
    double[] p1 = {x1, y1, 0.0};
    double[] p = Geometry.ruputePointOnLine (p0, p1, fractionFrom0);
    double[] r = {p[0], p[1]};
    return r;
  }

  /**
   * Extend a given line segment to a specified length.
   * 
   * @param p0, p1    Line segment to extend [x,y,z].
   * @param toLength  Length of new line segment.
   * @param anchor    Specifies the fixed point during extension.
   *                  If anchor is 0.0, p0 is fixed and p1 is adjusted.
   *                  If anchor is 1.0, p1 is fixed and p0 is adjusted.
   *                  If anchor is 0.5, the line is adjusted equally in each
   *                  direction and so on.
   */
  public static void extendLine (double[] p0, double[] p1, double toLength,
                                 double anchor)
  {
    double[] p = Geometry.ruputePointOnLine (p0, p1, anchor);
    
    double length0 = toLength * anchor;
    double length1 = toLength * (1.0 - anchor);
    
    Geometry.extendLine (p, p0, length0);
    Geometry.extendLine (p, p1, length1);
  }

  /**
   * Extend a given line segment to a given length and holding the first
   * point of the line as fixed.
   * 
   * @param p0, p1  Line segment to extend. p0 is fixed during extension
   * @param length  Length of new line segment.
   */
  public static void extendLine (double[] p0, double[] p1, double toLength)
  {
    double oldLength = Geometry.length (p0, p1);
    double lengthFraction = oldLength != 0.0 ? toLength / oldLength : 0.0;
    
    p1[0] = p0[0] + (p1[0] - p0[0]) * lengthFraction;
    p1[1] = p0[1] + (p1[1] - p0[1]) * lengthFraction;
    p1[2] = p0[2] + (p1[2] - p0[2]) * lengthFraction;  
  }

  /**
   * Return the length of a vector.
   * 
   * @param v  Vector to compute length of [x,y,z].
   * @return   Length of vector.
   */
  public static double length (double[] v)
  {
    return Math.sqrt (v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
  }

  /**
   * Compute distance between two points.
   * 
   * @param p0, p1  Points to compute distance between [x,y,z].
   * @return        Distance between points.
   */
  public static double length (double[] p0, double[] p1)
  {
    double[] v = Geometry.createVector (p0, p1);
    return length (v);
  }
  
  /**
   * Compute the length of the line from (x0,y0) to (x1,y1)
   * 
   * @param x0, y0  First line end point.
   * @param x1, y1  Second line end point.
   * @return        Length of line from (x0,y0) to (x1,y1).
   */
  public static double length (int x0, int y0, int x1, int y1)
  {
    return Geometry.length ((double) x0, (double) y0,
                            (double) x1, (double) y1);
  }

  /**
   * Compute the length of the line from (x0,y0) to (x1,y1)
   * 
   * @param x0, y0  First line end point.
   * @param x1, y1  Second line end point.
   * @return        Length of line from (x0,y0) to (x1,y1).
   */
  public static double length (double x0, double y0, double x1, double y1)
  {
    double dx = x1 - x0;
    double dy = y1 - y0;
  
    return Math.sqrt (dx*dx + dy*dy);
  }

  /**
   * Compute the length of a polyline.
   * 
   * @param x, y     Arrays of x,y coordinates
   * @param nPoints  Number of elements in the above.
   * @param isClosed True if this is a closed polygon, false otherwise
   * @return         Length of polyline defined by x, y and nPoints.
   */
  public static double length (int[] x, int[] y, boolean isClosed)
  {
    double length = 0.0;
    int nPoints = x.length;
    for (int i = 0; i < nPoints-1; i++)
      length += Geometry.length (x[i], y[i], x[i+1], y[i+1]);
    // Add last leg if this is a polygon
    if (isClosed && nPoints > 1)
      length += Geometry.length (x[nPoints-1], y[nPoints-1], x[0], y[0]);
    return length;
  }

  /**
   * Return distance bwetween the line defined by (x0,y0) and (x1,y1)
   * and the point (x,y).
   * Ref: http://astronomy.swin.edu.au/pbourke/geometry/pointline/
   * The 3D case should be similar.
   *
   * @param  x0, y0  First point of line.
   * @param  x1, y1  Second point of line.
   * @param  x, y,   Point to consider.
   * @return         Distance from x,y down to the (extended) line defined
   *                 by x0, y0, x1, y1.
   */
  public static double distance (int x0, int y0, int x1, int y1,
                                 int x, int y)
  {
    // If x0,y0,x1,y1 is same point, we return distance to that point
    double length = Geometry.length (x0, y0, x1, y1);
    if (length == 0.0)
      return Geometry.length (x0, y0, x, y);
    // If u is [0,1] then (xp,yp) is on the line segment (x0,y0),(x1,y1).
    double u = ((x - x0) * (x1 - x0) + (y - y0) * (y1 - y0)) /
               (length * length);
    // This is the intersection point of the normal.
    // TODO: Might consider returning this as well.
    double xp = x0 + u * (x1 - x0);
    double yp = y0 + u * (y1 - y0);
    length = Geometry.length (xp, yp, x, y);
    return length;
  }
  
  
  
  /**
   * Find the angle between twree points. P0 is center point
   * 
   * @param p0, p1, p2  Three points finding angle between [x,y,z].
   * @return            Angle (in radians) between given points.
   */
  public static double computeAngle (double[] p0, double[] p1, double[] p2)
  {
    double[] v0 = Geometry.createVector (p0, p1);
    double[] v1 = Geometry.createVector (p0, p2);
    double dotProduct = Geometry.ruputeDotProduct (v0, v1);
    double length1 = Geometry.length (v0);
    double length2 = Geometry.length (v1);
    double denominator = length1 * length2;
    
    double product = denominator != 0.0 ? dotProduct / denominator : 0.0;
  
    double angle = Math.acos (product);
    return angle;
  }

  /**
   * Compute the dot product (a scalar) between two vectors.
   * 
   * @param v0, v1  Vectors to compute dot product between [x,y,z].
   * @return        Dot product of given vectors.
   */
  public static double computeDotProduct (double[] v0, double[] v1)
  {
    return v0[0] * v1[0] + v0[1] * v1[1] + v0[2] * v1[2];
  }

  /**
   * Compute the cross product (a vector) of two vectors.
   * 
   * @param v0, v1        Vectors to compute cross product between [x,y,z].
   * @param crossProduct  Cross product of specified vectors [x,y,z].
   */
  public static double[] computeCrossProduct (double[] v0, double[] v1)
  {
    double crossProduct[] = new double[3];
    
    crossProduct[0] = v0[1] * v1[2] - v0[2] * v1[1];
    crossProduct[1] = v0[2] * v1[0] - v0[0] * v1[2];
    crossProduct[2] = v0[0] * v1[1] - v0[1] * v1[0];
    return crossProduct;
  }

  /**
   * Construct the vector specified by two points.
   * 
   * @param  p0, p1  Points the construct vector between [x,y,z].
   * @return v       Vector from p0 to p1 [x,y,z].
   */
  public static double[] createVector (double[] p0, double[] p1)
  {
    double v[] = {p1[0] - p0[0], p1[1] - p0[1], p1[2] - p0[2]};
    return v;
  }

  
  /**
   * Check if two points are on the same side of a given line.
   * Algorithm from Sedgewick page 350.
   * 
   * @param x0, y0, x1, y1  The line.
   * @param px0, py0        First point.
   * @param px1, py1        Second point.
   * @return                <0 if points on opposite sides.
   *                        =0 if one of the points is exactly on the line
   *                        >0 if points on same side.
   */
  private static int sameSide (double x0, double y0, double x1, double y1,
                              double px0, double py0, double px1, double py1)
  {
    int  sameSide = 0;
    
    double dx  = x1  - x0;
    double dy  = y1  - y0;
    double dx1 = px0 - x0;
    double dy1 = py0 - y0;
    double dx2 = px1 - x1;
    double dy2 = py1 - y1;
    // Cross product of the vector from the endpoint of the line to the point
    double c1 = dx * dy1 - dy * dx1;
    double c2 = dx * dy2 - dy * dx2;
    if (c1 != 0 && c2 != 0)
      sameSide = c1 < 0 != c2 < 0 ? -1 : 1;
    else if (dx == 0 && dx1 == 0 && dx2 == 0)
      sameSide = !isBetween (y0, y1, py0) && !isBetween (y0, y1, py1) ? 1 : 0;
    else if (dy == 0 && dy1 == 0 && dy2 == 0)
      sameSide = !isBetween (x0, x1, px0) && !isBetween (x0, x1, px1) ? 1 : 0;
    return sameSide;
  }
  
  
  /**
   * Check if two points are on the same side of a given line. Integer domain.
   * 
   * @param x0, y0, x1, y1  The line.
   * @param px0, py0        First point.
   * @param px1, py1        Second point.
   * @return                <0 if points on opposite sides.
   *                        =0 if one of the points is exactly on the line
   *                        >0 if points on same side.
   */
  private static int sameSide (int x0, int y0, int x1, int y1,
                               int px0, int py0, int px1, int py1)
  {
    return sameSide ((double) x0, (double) y0, (double) x1, (double) y1,
                     (double) px0, (double) py0, (double) px1, (double) py1);
  }
  
  
  /**
   * Check if two line segments intersects. Integer domain.
   * 
   * @param x0, y0, x1, y1  End points of first line to check.
   * @param x2, yy, x3, y3  End points of second line to check.
   * @return                True if the two lines intersects.
   */
  public static boolean isLineIntersectingLine (int x0, int y0, int x1, int y1,
                                                int x2, int y2, int x3, int y3)
  {
    int s1 = Geometry.sameSide (x0, y0, x1, y1, x2, y2, x3, y3);
    int s2 = Geometry.sameSide (x2, y2, x3, y3, x0, y0, x1, y1);
    
    return s1 <= 0 && s2 <= 0;
  }
  
  
  
  /**
   * Check if a specified line intersects a specified rectangle.
   * Integer domain.
   * 
   * @param lx0, ly0        1st end point of line
   * @param ly1, ly1        2nd end point of line
   * @param x0, y0, x1, y1  Upper left and lower right corner of rectangle
   *                        (inclusive).
   * @return                True if the line intersects the rectangle,
   *                        false otherwise.
   */
  public static boolean isLineIntersectingRectangle (int lx0, int ly0,
                                                     int lx1, int ly1,
                                                     int x0, int y0,
                                                     int x1, int y1)
  {
    // Is one of the line endpoints inside the rectangle
    if (Geometry.isPointInsideRectangle (x0, y0, x1, y1, lx0, ly0) ||
        Geometry.isPointInsideRectangle (x0, y0, x1, y1, lx1, ly1))
      return true;
    // If it intersects it goes through. Need to check three sides only.
    // Check against top rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y0, x1, y0))
      return true;
    // Check against left rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y0, x0, y1))
      return true;
    // Check against bottom rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y1, x1, y1))
      return true;
    return false;
  }
  
  
  /**
   * Check if a specified polyline intersects a specified rectangle.
   * Integer domain.
   * 
   * @param x, y            Polyline to check.
   * @param x0, y0, x1, y1  Upper left and lower left corner of rectangle
   *                        (inclusive).
   * @return                True if the polyline intersects the rectangle,
   *                        false otherwise.
   */
  public static boolean isPolylineIntersectingRectangle (int[] x, int[] y,
                                                         int x0, int y0,
                                                         int x1, int y1)
  {
    if (x.length == 0) return false;
    
    if (Geometry.isPointInsideRectangle (x[0], y[0], x0, y0, x1, y1))
      return true;
    
    else if (x.length == 1)
      return false;
    
    for (int i = 1; i < x.length; i++) {
      if (x[i-1] != x[i] || y[i-1] != y[i])
        if (Geometry.isLineIntersectingRectangle (x[i-1], y[i-1],
                                                  x[i], y[i],
                                                  x0, y0, x1, y1))
          return true;
    }
    return false;
  }

  /**
   * Check if a specified polygon intersects a specified rectangle.
   * Integer domain.
   * 
   * @param x   X coordinates of polyline.
   * @param y   Y coordinates of polyline.   
   * @param x0  X of upper left corner of rectangle.
   * @param y0  Y of upper left corner of rectangle.   
   * @param x1  X of lower right corner of rectangle.
   * @param y1  Y of lower right corner of rectangle.   
   * @return    True if the polyline intersects the rectangle, false otherwise.
   */
  public static boolean isPolygonIntersectingRectangle (int[] x, int[] y,
                                                        int x0, int y0,
                                                        int x1, int y1)
  {
    int n = x.length;
    
    if (n == 0)
      return false;
    
    if (n == 1)
      return Geometry.isPointInsideRectangle (x0, y0, x1, y1, x[0], y[0]);
    
    //
    // If the polyline constituting the polygon intersects the rectangle
    // the polygon does too.
    //
    if (Geometry.isPolylineIntersectingRectangle (x, y, x0, y0, x1, y1))
      return true;
  
    // Check last leg as well
    if (Geometry.isLineIntersectingRectangle (x[n-2], y[n-2], x[n-1], y[n-1],
                                              x0, y0, x1, y1))
      return true;
    //
    // The rectangle and polygon are now completely including each other
    // or separate.
    //
    if (Geometry.isPointInsidePolygon (x, y, x0, y0) ||
        Geometry.isPointInsideRectangle (x0, y0, x1, y1, x[0], y[0]))
      return true;
  
    // Separate
    return false;
  }
  
  
  /**
   * Compute the area of the specfied polygon.
   * 
   * @param x  X coordinates of polygon.
   * @param y  Y coordinates of polygon.   
   * @return   Area of specified polygon.
   */
  public static double computePolygonArea (double[] x, double[] y)
  {
    int n = x.length;
    
    double area = 0.0;
    for (int i = 0; i < n - 1; i++)
      area += (x[i] * y[i+1]) - (x[i+1] * y[i]);
    area += (x[n-1] * y[0]) - (x[0] * y[n-1]);    
    area *= 0.5;
    return area;
  }

  
  /**
   * Compute the area of the specfied polygon.
   * 
   * @param xy  Geometry of polygon [x,y,...]
   * @return    Area of specified polygon.
   */
  public static double computePolygonArea (double[] xy)
  {
    int n = xy.length;
    
    double area = 0.0;
    for (int i = 0; i < n - 2; i += 2)
      area += (xy[i] * xy[i+3]) - (xy[i+2] * xy[i+1]);
    area += (xy[xy.length-2] * xy[1]) - (xy[0] * xy[xy.length-1]);    
    area *= 0.5;
    return area;
  }
  
  /**
   * Compute centorid (center of gravity) of specified polygon.
   * 
   * @param x  X coordinates of polygon.
   * @param y  Y coordinates of polygon.   
   * @return   Centroid [x,y] of specified polygon.
   */
  public static double[] computePolygonCentroid (double[] x, double[] y)
  {
    double cx = 0.0;
    double cy = 0.0;
    int n = x.length;
    for (int i = 0; i < n - 1; i++) {
      double a = x[i] * y[i+1] - x[i+1] * y[i];
      cx += (x[i] + x[i+1]) * a;
      cy += (y[i] + y[i+1]) * a;
    }
    double a = x[n-1] * y[0] - x[0] * y[n-1];
    cx += (x[n-1] + x[0]) * a;
    cy += (y[n-1] + y[0]) * a;
      
    double area = Geometry.ruputePolygonArea (x, y);
    cx /= 6 * area;
    cy /= 6 * area;    
    
    return new double[] {cx, cy};
  }  
  
  
  /**
   * Find the 3D extent of a polyline.
   * 
   * @param x        X coordinates of polyline.
   * @param y        Y coordinates of polyline.
   * @param z        Z coordinates of polyline.
   *                 May be null if this is a 2D case.
   * @param xExtent  Will upon return contain [xMin,xMax].
   * @param yExtent  Will upon return contain [xMin,xMax].
   * @param zExtent  Will upon return contain [xMin,xMax]. Unused (may be
   *                 set to null) if z is null.
   */
  public static void findPolygonExtent (double[] x, double[] y, double[] z,
                                        double[] xExtent,
                                        double[] yExtent,
                                        double[] zExtent)
  {
    double xMin = +Double.MAX_VALUE;
    double xMax = -Double.MAX_VALUE;
    
    double yMin = +Double.MAX_VALUE;
    double yMax = -Double.MAX_VALUE;
    
    double zMin = +Double.MAX_VALUE;
    double zMax = -Double.MAX_VALUE;
    
    for (int i = 0; i < x.length; i++) {
      if (x[i] < xMin) xMin = x[i];
      if (x[i] > xMax) xMax = x[i];    
      if (y[i] < yMin) yMin = y[i];
      if (y[i] > yMax) yMax = y[i];    
      if (z != null) {
        if (z[i] < zMin) zMin = z[i];
        if (z[i] > zMax) zMax = z[i];
      }
    }
    
    xExtent[0] = xMin;
    xExtent[1] = xMax;
    
    yExtent[0] = yMin;
    yExtent[1] = yMax;
    if (z != null) {
      zExtent[0] = zMin;
      zExtent[1] = zMax;
    }
  }

  /**
   * Find the extent of a polygon. 
   * 
   * @param x        X coordinates of polygon.
   * @param y        Y coordinates of polygon.   
   * @param xExtent  Will upon return contain [xMin, xMax]
   * @param yExtent  Will upon return contain [yMin, yMax]   
   */
  public static void findPolygonExtent (int[] x, int[] y,
                                        int[] xExtent,  // xMin, xMax
                                        int[] yExtent)  // yMin, yMax
  {
    int xMin = + Integer.MAX_VALUE;
    int xMax = - Integer.MAX_VALUE;
    
    int yMin = + Integer.MAX_VALUE;
    int yMax = - Integer.MAX_VALUE;
    
    for (int i = 0; i < x.length; i++) {
      if (x[i] < xMin) xMin = x[i];
      if (x[i] > xMax) xMax = x[i];    
      
      if (y[i] < yMin) yMin = y[i];
      if (y[i] > yMax) yMax = y[i];    
    }
    xExtent[0] = xMin;
    xExtent[1] = xMax;
    
    yExtent[0] = yMin;
    yExtent[1] = yMax;
  }

  /**
   * Compute the intersection between two line segments, or two lines
   * of infinite length.
   * 
   * @param  x0              X coordinate first end point first line segment.
   * @param  y0              Y coordinate first end point first line segment.
   * @param  x1              X coordinate second end point first line segment.
   * @param  y1              Y coordinate second end point first line segment.
   * @param  x2              X coordinate first end point second line segment.
   * @param  y2              Y coordinate first end point second line segment.
   * @param  x3              X coordinate second end point second line segment.
   * @param  y3              Y coordinate second end point second line segment.
   * @param  intersection[2] Preallocated by caller to double[2]
   * @return -1 if lines are parallel (x,y unset),
   *         -2 if lines are parallel and overlapping (x, y center)
   *          0 if intesrection outside segments (x,y set)
   *         +1 if segments intersect (x,y set)
   */
  public static int findLineSegmentIntersection (double x0, double y0,
                                                 double x1, double y1,
                                                 double x2, double y2,
                                                 double x3, double y3,
                                                 double[] intersection)
  {
    // TODO: Make limit depend on input domain
    final double LIMIT    = 1e-5;
    final double INFINITY = 1e10;
    
    double x, y;
    
    //
    // Convert the lines to the form y = ax + b
    //
    
    // Slope of the two lines
    double a0 = Geometry.equals (x0, x1, LIMIT) ?
                INFINITY : (y0 - y1) / (x0 - x1);
    double a1 = Geometry.equals (x2, x3, LIMIT) ?
                INFINITY : (y2 - y3) / (x2 - x3);
    
    double b0 = y0 - a0 * x0;
    double b1 = y2 - a1 * x2;
    
    // Check if lines are parallel
    if (Geometry.equals (a0, a1)) {
      if (!Geometry.equals (b0, b1))
        return -1; // Parallell non-overlapping
      
      else {
        if (Geometry.equals (x0, x1)) {
          if (Math.min (y0, y1) < Math.max (y2, y3) ||
              Math.max (y0, y1) > Math.min (y2, y3)) {
            double twoMiddle = y0 + y1 + y2 + y3 -
                               Geometry.min (y0, y1, y2, y3) -
                               Geometry.max (y0, y1, y2, y3);
            y = (twoMiddle) / 2.0;
            x = (y - b0) / a0;
          }
          else return -1;  // Parallell non-overlapping
        }
        else {
          if (Math.min (x0, x1) < Math.max (x2, x3) ||
              Math.max (x0, x1) > Math.min (x2, x3)) {
            double twoMiddle = x0 + x1 + x2 + x3 -
                               Geometry.min (x0, x1, x2, x3) -
                               Geometry.max (x0, x1, x2, x3);
            x = (twoMiddle) / 2.0;
            y = a0 * x + b0;
          }
          else return -1;
        }
        
        intersection[0] = x;
        intersection[1] = y;
        return -2;
      }
    }
    
    // Find correct intersection point
    if (Geometry.equals (a0, INFINITY)) {
      x = x0;
      y = a1 * x + b1;
    }
    else if (Geometry.equals (a1, INFINITY)) {
      x = x2;
      y = a0 * x + b0;
    }
    else {
      x = - (b0 - b1) / (a0 - a1);
      y = a0 * x + b0; 
    }
    
    intersection[0] = x;
    intersection[1] = y;
    
    // Then check if intersection is within line segments
    double distanceFrom1;
    if (Geometry.equals (x0, x1)) {
      if (y0 < y1)
        distanceFrom1 = y < y0 ? Geometry.length (x, y, x0, y0) :
                        y > y1 ? Geometry.length (x, y, x1, y1) : 0.0;
      else
        distanceFrom1 = y < y1 ? Geometry.length (x, y, x1, y1) :
                        y > y0 ? Geometry.length (x, y, x0, y0) : 0.0;
    }
    else {
      if (x0 < x1)
        distanceFrom1 = x < x0 ? Geometry.length (x, y, x0, y0) :
                        x > x1 ? Geometry.length (x, y, x1, y1) : 0.0;
      else
        distanceFrom1 = x < x1 ? Geometry.length (x, y, x1, y1) :
                        x > x0 ? Geometry.length (x, y, x0, y0) : 0.0;
    }
    
    double distanceFrom2;
    if (Geometry.equals (x2, x3)) {
      if (y2 < y3)
        distanceFrom2 = y < y2 ? Geometry.length (x, y, x2, y2) :
                        y > y3 ? Geometry.length (x, y, x3, y3) : 0.0;
      else
        distanceFrom2 = y < y3 ? Geometry.length (x, y, x3, y3) :
                        y > y2 ? Geometry.length (x, y, x2, y2) : 0.0;
    }
    else {
      if (x2 < x3)
        distanceFrom2 = x < x2 ? Geometry.length (x, y, x2, y2) :
                        x > x3 ? Geometry.length (x, y, x3, y3) : 0.0;
      else
        distanceFrom2 = x < x3 ? Geometry.length (x, y, x3, y3) :
                        x > x2 ? Geometry.length (x, y, x2, y2) : 0.0;
    }
    
    return Geometry.equals (distanceFrom1, 0.0) &&
      Geometry.equals (distanceFrom2, 0.0) ? 1 : 0;
  }
  
  
  
  /**
   * Find the intersections between a polygon and a straight line.
   * 
   * NOTE: This method is only guaranteed to work if the polygon
   * is first preprocessed so that "unneccesary" vertices are removed
   * (i.e vertices on the straight line between its neighbours).
   * 
   * @param  x   X coordinates of polygon.
   * @param  y   Y coordinates of polygon.   
   * @param  x0  X first end point of line.
   * @param  x0  Y first end point of line.
   * @param  x0  X second end point of line.
   * @param  x0  Y second end point of line.   
   * @return     Intersections [x,y,x,y...].
   */
  public static double[] findLinePolygonIntersections (double[] x, double[] y,
                                                       double x0, double y0,
                                                       double x1, double y1)
  {
    double          x2, y2, x3, y3;
    double          xi, yi;
    int nPoints   = x.length;
    int      nIntersections = 0;
    double[] intersections = new double[24];  // Result vector x,y,x,y,...
    double[] intersection  = new double[2];   // Any given intersection x,y
    
    for (int i = 0; i < nPoints; i++) {
      int next = i == nPoints - 1 ? 0 : i + 1;
      // The line segment of the polyline to check
      x2 = x[i];
      y2 = y[i];
      x3 = x[next];
      y3 = y[next];
      boolean isIntersecting = false;
      
      // Ignore segments of zero length
      if (Geometry.equals (x2, x3) && Geometry.equals (y2, y3))
        continue;
      int type = Geometry.findLineSegmentIntersection (x0, y0, x1, y1,
                                                       x2, y2, x3, y3,
                                                       intersection);
      
      if (type == -2) { // Overlapping
        int p1 = i    == 0           ? nPoints - 1 : i - 1;
        int p2 = next == nPoints - 1 ? 0           : next + 1;
        
        int side = Geometry.sameSide (x0, y0, x1, y1,
                                      x[p1], y[p1], x[p2], y[p2]);
        
        if (side < 0)
          isIntersecting = true;
      }
      else if (type == 1)
        isIntersecting = true;
      // Add the intersection point
      if (isIntersecting) {
        // Reallocate if necessary
        if (nIntersections << 1 == intersections.length) {
          double[] newArray = new double[nIntersections << 2];
          System.arraycopy (intersections, 0, newArray, 0,
                            intersections.length);
          intersections = newArray;
        }
        // Then add
        intersections[nIntersections << 1 + 0] = intersection[0];
        intersections[nIntersections << 1 + 1] = intersection[1];
        nIntersections++;
      }
    }
    if (nIntersections == 0) return null;
      
    // Reallocate result so array match number of intersections
    double[] finalArray = new double[nIntersections << 2];
    System.arraycopy (intersections, 0, finalArray, 0, finalArray.length);
    return finalArray;
  }

  
  /**
   * Return the geometry of an ellipse based on its four top points.
   * Integer domain. The method use the generic createEllipse()
   * method for the main task, and then transforms this according
   * to any rotation or skew defined by the given top points.
   * 
   * @param  x  X array of four top points of ellipse.
   * @param  y  Y array of four top points of ellipse.   
   * @return    Geometry of ellipse [x,y,x,y...].
   */
  public static int[] createEllipse (int[] x, int[] y)
  {
    // Center of ellipse
    int x0 = (x[0] + x[2]) / 2;
    int y0 = (y[0] + y[2]) / 2;
    // Angle between axis define skew
    double[] p0 = {(double) x0,   (double) y0,   0.0};
    double[] p1 = {(double) x[0], (double) y[0], 0.0};
    double[] p2 = {(double) x[1], (double) y[1], 0.0};
  
    double axisAngle = Geometry.ruputeAngle (p0, p1, p2);
  
    // dx / dy  
    double dx = Geometry.length (x0, y0, x[1], y[1]);
    double dy = Geometry.length (x0, y0, x[0], y[0]) * Math.sin (axisAngle);
    
    // Create geometry for unrotated / unsheared ellipse
    int[] ellipse = createEllipse (x0, y0, (int) Math.round (dx),
                                   (int) Math.round (dy));
    int nPoints = ellipse.length / 2;
    // Shear if neccessary. If angle is close to 90 there is no shear.
    // If angle is close to 0 or 180 shear is infinite, and we set
    // it to zero as well.
    if (!Geometry.equals (axisAngle, Math.PI/2.0, 0.1) && 
        !Geometry.equals (axisAngle, Math.PI,     0.1) &&
        !Geometry.equals (axisAngle, 0.0,         0.1)) {
      double xShear = 1.0 / Math.tan (axisAngle);
      for (int i = 0; i < nPoints; i++)
        ellipse[i*2 + 0] += Math.round ((ellipse[i*2 + 1] - y0) * xShear);
    }
    // Rotate
    int ddx = x[1] - x0;
    int ddy = y0   - y[1];
    
    double angle;
    if      (ddx == 0 && ddy == 0) angle = 0.0;
    else if (ddx == 0)             angle = Math.PI / 2.0;
    else                           angle = Math. atan ((double) ddy /
                                                       (double) ddx);
    
    double cosAngle = Math.cos (angle);
    double sinAngle = Math.sin (angle);
    
    for (int i = 0; i < nPoints; i++) {
      int xr = (int) Math.round (x0 +
                                 (ellipse[i*2+0] - x0) * cosAngle -
                                 (ellipse[i*2+1] - y0) * sinAngle);
      int yr = (int) Math.round (y0 -
                                 (ellipse[i*2+1] - y0) * cosAngle -
                                 (ellipse[i*2+0] - x0) * sinAngle);
                           
      ellipse[i*2+0] = xr;
      ellipse[i*2+1] = yr;
    }
    return ellipse;
  }

  /**
   * Create the geometry for an unrotated, unskewed ellipse.
   * Integer domain.
   * 
   * @param x0  X center of ellipse.
   * @param y0  Y center of ellipse.   
   * @param dx  X ellipse radius.
   * @param dy  Y ellipse radius.
   * @return    Ellipse geometry [x,y,x,y,...].
   */
  public static int[] createEllipse (int x0, int y0, int dx, int dy)
  {
    // Make sure deltas are positive
    dx = Math.abs (dx);
    dy = Math.abs (dy);
    // This is an approximate number of points we need to make a smooth
    // surface on a quater of the ellipse
    int nPoints = dx > dy ? dx : dy;
    nPoints /= 2;
    if (nPoints < 1) nPoints = 1;
    // Allocate arrays for holding the complete set of vertices around
    // the ellipse. Note that this is a complete ellipse: First and last
    // point coincide.
    int[] ellipse = new int[nPoints*8 + 2];
    // Compute some intermediate results to save time in the inner loop
    int  dxdy = dx * dy;
    int  dx2  = dx * dx;
    int  dy2  = dy * dy;
    // Handcode the entries in the four "corner" points of the ellipse,
    // i.e. at point 0, 90, 180, 270 and 360 degrees
    ellipse[nPoints*0 + 0] = x0 + dx;
    ellipse[nPoints*0 + 1] = y0;
    
    ellipse[nPoints*8 + 0] = x0 + dx;
    ellipse[nPoints*8 + 1] = y0;
    
    ellipse[nPoints*2 + 0] = x0;
    ellipse[nPoints*2 + 1] = y0 - dy;
    
    ellipse[nPoints*4 + 0] = x0 - dx;
    ellipse[nPoints*4 + 1] = y0;
    
    ellipse[nPoints*6 + 0] = x0;
    ellipse[nPoints*6 + 1] = y0 + dy;
    // Find the angle step
    double  angleStep = nPoints > 0 ? Math.PI / 2.0 / nPoints : 0.0;
    // Loop over angles from 0 to 90. The rest of the ellipse can be derrived
    // from this first quadrant. For each angle set the four corresponding
    // ellipse points.
    double a = 0.0;
    for (int i = 1; i < nPoints; i++) {
      a += angleStep;
      double t = Math.tan (a);
      double x = (double) dxdy / Math.sqrt (t * t * dx2 + dy2);
      double y = x * t;
    
      int xi = (int) (x + 0.5);
      int yi = (int) (y + 0.5);
      ellipse[(nPoints*0 + i) * 2 + 0] = x0 + xi;
      ellipse[(nPoints*2 - i) * 2 + 0] = x0 - xi;
      ellipse[(nPoints*2 + i) * 2 + 0] = x0 - xi;
      ellipse[(nPoints*4 - i) * 2 + 0] = x0 + xi;
      
      ellipse[(nPoints*0 + i) * 2 + 1] = y0 - yi;
      ellipse[(nPoints*2 - i) * 2 + 1] = y0 - yi;
      ellipse[(nPoints*2 + i) * 2 + 1] = y0 + yi;
      ellipse[(nPoints*4 - i) * 2 + 1] = y0 + yi;
    }
    return ellipse;
  }

  /**
   * Create the geometry for an unrotated, unskewed ellipse.
   * Floating point domain.
   * 
   * @param x0  X center of ellipse.
   * @param y0  Y center of ellipse.   
   * @param dx  X ellipse radius.
   * @param dy  Y ellipse radius.
   * @return    Ellipse geometry [x,y,x,y,...].
   */
  public static double[] createEllipse (double x0, double y0,
                                        double dx, double dy)
  {
    // Make sure deltas are positive
    dx = Math.abs (dx);
    dy = Math.abs (dy);
    // As we don"t know the resolution of the appliance of the ellipse
    // we create one vertex per 2nd degree. The nPoints variable holds
    // number of points in a quater of the ellipse.
    int nPoints = 45;
    // Allocate arrays for holding the complete set of vertices around
    // the ellipse. Note that this is a complete ellipse: First and last
    // point coincide.
    double[] ellipse = new double[nPoints*8 + 2];
    // Compute some intermediate results to save time in the inner loop
    double dxdy = dx * dy;
    double dx2  = dx * dx;
    double dy2  = dy * dy;
    // Handcode the entries in the four "corner" points of the ellipse,
    // i.e. at point 0, 90, 180, 270 and 360 degrees
    ellipse[nPoints*0 + 0] = x0 + dx;
    ellipse[nPoints*0 + 1] = y0;
    
    ellipse[nPoints*8 + 0] = x0 + dx;
    ellipse[nPoints*8 + 1] = y0;
    
    ellipse[nPoints*2 + 0] = x0;
    ellipse[nPoints*2 + 1] = y0 - dy;
    
    ellipse[nPoints*4 + 0] = x0 - dx;
    ellipse[nPoints*4 + 1] = y0;
    
    ellipse[nPoints*6 + 0] = x0;
    ellipse[nPoints*6 + 1] = y0 + dy;
    // Find the angle step
    double  angleStep = nPoints > 0 ? Math.PI / 2.0 / nPoints : 0.0;
    // Loop over angles from 0 to 90. The rest of the ellipse can be derrived
    // from this first quadrant. For each angle set the four corresponding
    // ellipse points.
    double a = 0.0;
    for (int i = 1; i < nPoints; i++) {
      a += angleStep;
      double t = Math.tan (a);
      double x = (double) dxdy / Math.sqrt (t * t * dx2 + dy2);
      double y = x * t + 0.5;   
    
      ellipse[(nPoints*0 + i) * 2 + 0] = x0 + x;
      ellipse[(nPoints*2 - i) * 2 + 0] = x0 - x;
      ellipse[(nPoints*2 + i) * 2 + 0] = x0 - x;
      ellipse[(nPoints*4 - i) * 2 + 0] = x0 + x;
      
      ellipse[(nPoints*0 + i) * 2 + 1] = y0 - y;
      ellipse[(nPoints*2 - i) * 2 + 1] = y0 - y;
      ellipse[(nPoints*2 + i) * 2 + 1] = y0 + y;
      ellipse[(nPoints*4 - i) * 2 + 1] = y0 + y;
    }
    return ellipse;
  }

  /**
   * Create geometry for a circle. Integer domain.
   * 
   * @param x0      X center of circle.
   * @param y0      Y center of circle.   
   * @param radius  Radius of circle.
   * @return        Geometry of circle [x,y,...]
   */
  public static int[] createCircle (int x0, int y0, int radius)
  {
    return createEllipse (x0, y0, radius, radius);
  }
  
  
  
  /**
   * Create geometry for a circle. Floating point domain.
   * 
   * @param x0      X center of circle.
   * @param y0      Y center of circle.   
   * @param radius  Radius of circle.
   * @return        Geometry of circle [x,y,...]
   */
  public static double[] createCircle (double x0, double y0, double radius)
  {
    return createEllipse (x0, y0, radius, radius);
  }

  
  /**
   * Create the geometry of a sector of an ellipse.
   * 
   * @param x0      X coordinate of center of ellipse.
   * @param y0      Y coordinate of center of ellipse.
   * @param dx      X radius of ellipse.
   * @param dy      Y radius of ellipse.
   * @param angle0  First angle of sector (in radians).
   * @param angle1  Second angle of sector (in radians).
   * @return        Geometry of secor [x,y,...]
   */
  public static int[] createSector (int x0, int y0, int dx, int dy,
                                    double angle0, double angle1)
  {
    // Determine a sensible number of points for arc
    double angleSpan   = Math.abs (angle1 - angle0);
    double arcDistance = Math.max (dx, dy) * angleSpan;
    int    nPoints     = (int) Math.round (arcDistance / 15);
    double angleStep   = angleSpan / (nPoints - 1);
    int[] xy = new int[nPoints*2 + 4];
    int index = 0;
    for (int i = 0; i < nPoints; i++) {
      double angle = angle0 + angleStep * i;
      double x = dx * Math.cos (angle);
      double y = dy * Math.sin (angle);
      xy[index+0] = x0 + (int) Math.round (x);
      xy[index+1] = y0 - (int) Math.round (y);
      index += 2;
    }
    // Start and end geometry at center of ellipse to make it a closed polygon
    xy[nPoints*2 + 0] = x0;
    xy[nPoints*2 + 1] = y0;
    xy[nPoints*2 + 2] = xy[0];
    xy[nPoints*2 + 3] = xy[1];    
    return xy;
  }

  
  /**
   * Create the geometry of a sector of a circle.
   * 
   * @param x0      X coordinate of center of ellipse.
   * @param y0      Y coordinate of center of ellipse.
   * @param dx      X radius of ellipse.
   * @param dy      Y radius of ellipse.
   * @param angle0  First angle of sector (in radians).
   * @param angle1  Second angle of sector (in radians).
   * @return        Geometry of secor [x,y,...]
   */
  public static int[] createSector (int x0, int y0, int radius,
                                    double angle0, double angle1)
  {
    return createSector (x0, y0, radius, radius, angle0, angle1);
  }
  
  
  
  /**
   * Create the geometry of an arrow. The arrow is positioned at the
   * end (last point) of the specified polyline, as follows:
   *
   *                      0,4--,              
   *                         \  --,           
   *                          \    --,        
   *                           \      --,     
   *                            \        --,  
   *    -------------------------3-----------1
   *                            /        --"  
   *                           /      --"     
   *                          /    --"        
   *                         /  --"           
   *                        2--"                
   * 
   * @param x       X coordinates of polyline of where arrow is positioned
   *                in the end. Must contain at least two points.
   * @param y       Y coordinates of polyline of where arrow is positioned
   *                in the end.
   * @param length  Length along the main axis from point 1 to the
   *                projection of point 0.
   * @param angle   Angle between the main axis and the line 1,0
   *                (and 1,2) in radians.
   * @param inset   Specification of point 3 [0.0-1.0], 1.0 will put
   *                point 3 at distance length from 1, 0.0 will put it
   *                at point 1.
   * @return        Array of the five coordinates [x,y,...]. 
   */
  public static int[] createArrow (int[] x, int[] y,
                                   double length, double angle, double inset)
  {
    int[] arrow = new int[10];
    
    int x0 = x[x.length - 1];
    int y0 = y[y.length - 1];
    arrow[2] = x0;
    arrow[3] = y0;    
    
    // Find position of interior of the arrow along the polyline
    int[] pos1 = new int[2];
    Geometry.findPolygonPosition (x, y, length, pos1);
    // Angles
    double dx = x0 - pos1[0];
    double dy = y0 - pos1[1];
    // Polyline angle
    double v = dx == 0.0 ? Math.PI / 2.0 : Math.atan (Math.abs (dy / dx));
    v = dx >  0.0 && dy <= 0.0 ? Math.PI + v :
        dx >  0.0 && dy >= 0.0 ? Math.PI - v :
        dx <= 0.0 && dy <  0.0 ? -v          :
        dx <= 0.0 && dy >  0.0 ? +v          : 0.0;
    double v0 = v + angle;
    double v1 = v - angle;
    double edgeLength = length / Math.cos (angle);
    
    arrow[0] = x0 + (int) Math.round (edgeLength * Math.cos (v0));
    arrow[1] = y0 - (int) Math.round (edgeLength * Math.sin (v0));    
    
    arrow[4] = x0 + (int) Math.round (edgeLength * Math.cos (v1));
    arrow[5] = y0 - (int) Math.round (edgeLength * Math.sin (v1));
    double c1 = inset * length;
    arrow[6] = x0 + (int) Math.round (c1 * Math.cos (v));
    arrow[7] = y0 - (int) Math.round (c1 * Math.sin (v));
    // Close polygon
    arrow[8] = arrow[0];
    arrow[9] = arrow[1];    
    
    return arrow;
  }
  
  
  /**
   * Create geometry for an arrow along the specified line and with
   * tip at x1,y1. See general method above.
   * 
   * @param x0      X first end point of line.
   * @param y0      Y first end point of line.
   * @param x1      X second end point of line.
   * @param y1      Y second end point of line.   
   * @param length  Length along the main axis from point 1 to the
   *                projection of point 0.
   * @param angle   Angle between the main axis and the line 1,0
   *                (and 1.2)
   * @param inset   Specification of point 3 [0.0-1.0], 1.0 will put
   *                point 3 at distance length from 1, 0.0 will put it
   *                at point 1.
   * @return        Array of the four coordinates [x,y,...]. 
   */
  public static int[] createArrow (int x0, int y0, int x1, int y1,
                                   double length, double angle, double inset)
  {
    int[] x = {x0, x1};
    int[] y = {y0, y1};    
    return createArrow (x, y, length, angle, inset);
  }

  
  /**
   * Create geometry for a rectangle. Returns a closed polygon; first
   * and last points matches. Integer domain.
   * 
   * @param x0      X corner of rectangle.
   * @param y0      Y corner of rectangle.   
   * @param width   Width (may be negative to indicate leftwards direction)
   * @param height  Height (may be negative to indicaten upwards direction)
   */
  public static int[] createRectangle (int x0, int y0, int width, int height)
  {
    return new int[] {x0,               y0,
                      x0 + (width - 1), y0,
                      x0 + (width - 1), y0 + (height - 1),
                      x0,               y0 + (height - 1),
                      x0,               y0};
  }

  /**
   * Create geometry for a rectangle. Returns a closed polygon; first
   * and last points matches. Floating point domain.
   * 
   * @param x0      X corner of rectangle.
   * @param y0      Y corner of rectangle.   
   * @param width   Width (may be negative to indicate leftwards direction)
   * @param height  Height (may be negative to indicaten upwards direction)
   */
  public static double[] createRectangle (double x0, double y0,
                                          double width, double height)
  {
    return new double[] {x0,         y0,
                         x0 + width, y0,
                         x0 + width, y0 + height,
                         x0,         y0 + height,
                         x0,         y0};
  }

  /**
   * Create geometry of a star. Integer domain.
   * 
   * @param x0           X center of star.
   * @param y0           Y center of star.
   * @param innerRadius  Inner radis of arms.
   * @param outerRadius  Outer radius of arms.
   * @param nArms        Number of arms.
   * @return             Geometry of star [x,y,x,y,...].
   */
  public static int[] createStar (int x0, int y0,
                                  int innerRadius, int outerRadius,
                                  int nArms)
  {
    int nPoints = nArms * 2 + 1;
    
    int[] xy = new int[nPoints * 2];
    
    double angleStep = 2.0 * Math.PI / nArms / 2.0;
    for (int i = 0; i < nArms * 2; i++) {
      double angle = i * angleStep;
      double radius = (i % 2) == 0 ? innerRadius : outerRadius;
      double x = x0 + radius * Math.cos (angle);
      double y = y0 + radius * Math.sin (angle);
      xy[i*2 + 0] = (int) Math.round (x);
      xy[i*2 + 1] = (int) Math.round (y);
    }
    // Close polygon
    xy[nPoints*2 - 2] = xy[0];
    xy[nPoints*2 - 1] = xy[1];
    return xy;
  }
  
  
  
  /**
   * Create geometry of a star. Floating point domain.
   * 
   * @param x0           X center of star.
   * @param y0           Y center of star.
   * @param innerRadius  Inner radis of arms.
   * @param outerRadius  Outer radius of arms.
   * @param nArms        Number of arms.
   * @return             Geometry of star [x,y,x,y,...].
   */
  public static double[] createStar (double x0, double y0,
                                     double innerRadius, double outerRadius,
                                     int nArms)
  {
    int nPoints = nArms * 2 + 1;
    
    double[] xy = new double[nPoints * 2];
    
    double angleStep = 2.0 * Math.PI / nArms / 2.0;
    for (int i = 0; i < nArms * 2; i++) {
      double angle = i * angleStep;
      double radius = (i % 2) == 0 ? innerRadius : outerRadius;
      xy[i*2 + 0] = x0 + radius * Math.cos (angle);
      xy[i*2 + 1] = y0 + radius * Math.sin (angle);
    }
    // Close polygon
    xy[nPoints*2 - 2] = xy[0];
    xy[nPoints*2 - 1] = xy[1];
    return xy;
  }

  /**
   * Return the x,y position at distance "length" into the given polyline.
   * 
   * @param x         X coordinates of polyline
   * @param y         Y coordinates of polyline   
   * @param length    Requested position
   * @param position  Preallocated to int[2]
   * @return          True if point is within polyline, false otherwise
   */
  public static boolean findPolygonPosition (int[] x, int[] y,
                                             double length,
                                             int[] position)
  {
    if (length < 0) return false;
    
    double accumulatedLength = 0.0;
    for (int i = 1; i < x.length; i++) {
      double legLength = Geometry.length (x[i-1], y[i-1], x[i], y[i]);
      if (legLength + accumulatedLength >= length) {
        double part = length - accumulatedLength;
        double fraction = part / legLength;
        position[0] = (int) Math.round (x[i-1] + fraction * (x[i] - x[i-1]));
        position[1] = (int) Math.round (y[i-1] + fraction * (y[i] - y[i-1]));
        return true;
      }
      accumulatedLength += legLength;
    }
    // Length is longer than polyline
    return false;
  }
}



Interpolates points given in the 2D plane

 
import java.awt.geom.Point2D;
import java.util.Arrays;
/* This code is PUBLIC DOMAIN */
/*
 * @(#)Spline2D.java
 * 
 * Copyright (c) 2003 Martin Krueger
 * Copyright (c) 2005 David Benson
 *  
 */
/**
 * Interpolates points given in the 2D plane. The resulting spline
 * is a function s: R -> R^2 with parameter t in [0,1].
 * 
 * @author krueger
 */
public class Spline2D {
  /** 
   *  Array representing the relative proportion of the total distance
   *  of each point in the line ( i.e. first point is 0.0, end point is
   *  1.0, a point halfway on line is 0.5 ).
   */
  private double[] t;
  private Spline splineX;
  private Spline splineY;
  /**
   * Total length tracing the points on the spline
   */
  private double length;
  
  /**
   * Creates a new Spline2D.
   * @param points
   */
  public Spline2D(Point2D[] points) {
    double[] x = new double[points.length];
    double[] y = new double[points.length];
    
    for(int i = 0; i< points.length; i++) {
      x[i] = points[i].getX();
      y[i] = points[i].getY(); 
    }
    
    init(x, y);
  }
  /**
   * Creates a new Spline2D.
   * @param x
   * @param y
   */
  public Spline2D(double[] x, double[] y) {
    init(x, y);
  }
  private void init(double[] x, double[] y) {
    if (x.length != y.length) {
      throw new IllegalArgumentException("Arrays must have the same length.");
    }
    
    if (x.length < 2) {
      throw new IllegalArgumentException("Spline edges must have at least two points.");
    }
    t = new double[x.length];
    t[0] = 0.0; // start point is always 0.0
    
    // Calculate the partial proportions of each section between each set
    // of points and the total length of sum of all sections
    for (int i = 1; i < t.length; i++) {
      double lx = x[i] - x[i-1];
      double ly = y[i] - y[i-1];
      // If either diff is zero there is no point performing the square root
      if ( 0.0 == lx ) {
        t[i] = Math.abs(ly);
      } else if ( 0.0 == ly ) {
        t[i] = Math.abs(lx);
      } else {
        t[i] = Math.sqrt(lx*lx+ly*ly);
      }
      
      length += t[i];
      t[i] += t[i-1];
    }
    
    for(int i = 1; i< (t.length)-1; i++) {
      t[i] = t[i] / length;
    }
    
    t[(t.length)-1] = 1.0; // end point is always 1.0
    
    splineX = new Spline(t, x);
    splineY = new Spline(t, y);
  }
  /**
   * @param t 0 <= t <= 1
   */
  public double[] getPoint(double t) {
    double[] result = new double[2];
    result[0] = splineX.getValue(t);
    result[1] = splineY.getValue(t);
    return result;
  }
  
  /**
   * Used to check the correctness of this spline
   */
  public boolean checkValues() {
    return (splineX.checkValues() && splineY.checkValues());
  }
  public double getDx(double t) {
    return splineX.getDx(t);
  }
  
  public double getDy(double t) {
    return splineY.getDx(t);
  }
  
  public Spline getSplineX() {
    return splineX;
  }
  
  public Spline getSplineY() {
    return splineY;
  }
  
  public double getLength() {
    return length;
  }
}

/**
 * Interpolates given values by B-Splines.
 * 
 * @author krueger
 */
class Spline {
  private double[] xx;
  private double[] yy;
  private double[] a;
  private double[] b;
  private double[] c;
  private double[] d;
  /** tracks the last index found since that is mostly commonly the next one used */
  private int storageIndex = 0;
  /**
   * Creates a new Spline.
   * @param xx
   * @param yy
   */
  public Spline(double[] xx, double[] yy) {
    setValues(xx, yy);
  }
  /**
   * Set values for this Spline.
   * @param xx
   * @param yy
   */
  public void setValues(double[] xx, double[] yy) {
    this.xx = xx;
    this.yy = yy;
    if (xx.length > 1) {
      calculateCoefficients();
    }
  }
  /**
   * Returns an interpolated value.
   * @param x
   * @return the interpolated value
   */
  public double getValue(double x) {
    if (xx.length == 0) {
      return Double.NaN;
    }
    if (xx.length == 1) {
      if (xx[0] == x) {
        return yy[0];
      } else {
        return Double.NaN;
      }
    }
    int index = Arrays.binarySearch(xx, x);
    if (index > 0) {
      return yy[index];
    }
    index = - (index + 1) - 1;
    //TODO linear interpolation or extrapolation
    if (index < 0) {
      return yy[0];
    }
    return a[index]
      + b[index] * (x - xx[index])
      + c[index] * Math.pow(x - xx[index], 2)
      + d[index] * Math.pow(x - xx[index], 3);
  }
  /**
   * Returns an interpolated value. To be used when a long sequence of values
   * are required in order, but ensure checkValues() is called beforehand to
   * ensure the boundary checks from getValue() are made
   * @param x
   * @return the interpolated value
   */
  public double getFastValue(double x) {
    // Fast check to see if previous index is still valid
    if (storageIndex > -1 && storageIndex < xx.length-1 && x > xx[storageIndex] && x < xx[storageIndex + 1]) {
    } else {
      int index = Arrays.binarySearch(xx, x);
      if (index > 0) {
        return yy[index];
      }
      index = - (index + 1) - 1;
      storageIndex = index;
    }
  
    //TODO linear interpolation or extrapolation
    if (storageIndex < 0) {
      return yy[0];
    }
    double value = x - xx[storageIndex];
    return a[storageIndex]
          + b[storageIndex] * value
          + c[storageIndex] * (value * value)
          + d[storageIndex] * (value * value * value);
  }
  /**
   * Used to check the correctness of this spline
   */
  public boolean checkValues() {
    if (xx.length < 2) {
      return false;
    } else {
      return true;
    }
  }
  /**
   * Returns the first derivation at x.
   * @param x
   * @return the first derivation at x
   */
  public double getDx(double x) {
    if (xx.length == 0 || xx.length == 1) {
      return 0;
    }
    int index = Arrays.binarySearch(xx, x);
    if (index < 0) {
      index = - (index + 1) - 1;
    }
    return b[index]
      + 2 * c[index] * (x - xx[index])
      + 3 * d[index] * Math.pow(x - xx[index], 2);
  }
  /**
   * Calculates the Spline coefficients.
   */
  private void calculateCoefficients() {
    int N = yy.length;
    a = new double[N];
    b = new double[N];
    c = new double[N];
    d = new double[N];
    if (N == 2) {
      a[0] = yy[0];
      b[0] = yy[1] - yy[0];
      return;
    }
    double[] h = new double[N - 1];
    for (int i = 0; i < N - 1; i++) {
      a[i] = yy[i];
      h[i] = xx[i + 1] - xx[i];
      // h[i] is used for division later, avoid a NaN
      if (h[i] == 0.0) {
        h[i] = 0.01;
      }
    }
    a[N - 1] = yy[N - 1];
    double[][] A = new double[N - 2][N - 2];
    double[] y = new double[N - 2];
    for (int i = 0; i < N - 2; i++) {
      y[i] =
        3
          * ((yy[i + 2] - yy[i + 1]) / h[i
            + 1]
            - (yy[i + 1] - yy[i]) / h[i]);
      A[i][i] = 2 * (h[i] + h[i + 1]);
      if (i > 0) {
        A[i][i - 1] = h[i];
      }
      if (i < N - 3) {
        A[i][i + 1] = h[i + 1];
      }
    }
    solve(A, y);
    for (int i = 0; i < N - 2; i++) {
      c[i + 1] = y[i];
      b[i] = (a[i + 1] - a[i]) / h[i] - (2 * c[i] + c[i + 1]) / 3 * h[i];
      d[i] = (c[i + 1] - c[i]) / (3 * h[i]);
    }
    b[N - 2] =
      (a[N - 1] - a[N - 2]) / h[N
        - 2]
        - (2 * c[N - 2] + c[N - 1]) / 3 * h[N
        - 2];
    d[N - 2] = (c[N - 1] - c[N - 2]) / (3 * h[N - 2]);
  }
  /**
   * Solves Ax=b and stores the solution in b.
   */
  public void solve(double[][] A, double[] b) {
    int n = b.length;
    for (int i = 1; i < n; i++) {
      A[i][i - 1] = A[i][i - 1] / A[i - 1][i - 1];
      A[i][i] = A[i][i] - A[i - 1][i] * A[i][i - 1];
      b[i] = b[i] - A[i][i - 1] * b[i - 1];
    }
    b[n - 1] = b[n - 1] / A[n - 1][n - 1];
    for (int i = b.length - 2; i >= 0; i--) {
      b[i] = (b[i] - A[i][i + 1] * b[i + 1]) / A[i][i];
    }
  }
}



Unions Rectangle2D

 
/*
 * $Id: RectUtils.java,v 1.2 2008/02/28 14:38:48 david Exp $
 *
 * Copyright (c) 2008 Gaudenz Alder
 *
 */

import java.awt.geom.Rectangle2D;
public class RectUtils {
  /**
   * Unions the pair of source <code>Rectangle2D</code> objects and puts the
   * result into the returned <code>Rectangle2D</code> object. This method
   * extends the Rectangle2D version by checking for null parameters, the
   * returned value will also be <code>null</code> if the two input
   * rectangles are <code>null</code>
   * 
   * @param src1
   *            the first of a pair of <code>Rectangle2D</code> objects to
   *            be combined with each other
   * @param src2
   *            the second of a pair of <code>Rectangle2D</code> objects to
   *            be combined with each other
   * 
   */
  public static Rectangle2D union(Rectangle2D src1, Rectangle2D src2) {
    Rectangle2D result = null;
    if (src1 == null && src2 == null) {
      result = null;
    } else if (src1 != null && src2 != null) {
      double x1 = Math.min(src1.getMinX(), src2.getMinX());
      double y1 = Math.min(src1.getMinY(), src2.getMinY());
      double x2 = Math.max(src1.getMaxX(), src2.getMaxX());
      double y2 = Math.max(src1.getMaxY(), src2.getMaxY());
      result = new Rectangle2D.Double();
      result.setFrameFromDiagonal(x1, y1, x2, y2);
    } else if (src1 != null) {
      double x1 = src1.getMinX();
      double y1 = src1.getMinY();
      double x2 = src1.getMaxX();
      double y2 = src1.getMaxY();
      result = new Rectangle2D.Double();
      result.setFrameFromDiagonal(x1, y1, x2, y2);
    } else {
      // only src2 is non-null
      double x1 = src2.getMinX();
      double y1 = src2.getMinY();
      double x2 = src2.getMaxX();
      double y2 = src2.getMaxY();
      result = new Rectangle2D.Double();
      result.setFrameFromDiagonal(x1, y1, x2, y2);
    }
    return result;
  }
}