geometry.java

use Java code to draw on pad canvas

  /**
   * 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.computePolygonArea (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;
  }