geometry.java

use Java code to draw on pad canvas

  /**
   * 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.computeAngle (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 + 0.5;   
    
      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];