scribbledecobble: Shoestring Math

README

Code

/**
 * The <code>ShoestringMath</code> class demonstrates two methods that
 * can be used to compute the area of certain types of simple polygons:
 * <ul>
 * <li> Use a matrix to represent the polygon and cross multiply (the
 *      Shoelace Formula).
 * <li> Divide the polygon into triangles, compute the area of each
 *      triangle (using Heron's formula), and sum the areas.
 * </ul>
 */
public class ShoestringMath {

  /**
   * Converts command-line arguments to a matrix representing a polygon.
   * Cross multiplies, per the Shoelace Formula, to produce a value.
   * Converts the matrix into an array of coordinate triples, each
   * representing a triangle; computes and sums the areas of the
   * triagles. Outputs the matrix, the result of applying the Shoelace
   * Formula, and the sum of the areas of the triangles. For example,
   * if the value of <code>args</code> is:
   *
   * <blockquote>
   * <code>{"0", "0", "0", "1", "doh!", "1", "2.5", "0", "1"}</code>
   * </blockquote>
   *
   * then the output is:
   *
   * <blockquote>
   * <pre>
   * Shoelace Formula
   *
   * Matrix
   *
   * 0.0 0.0
   * 0.0 1.0
   * 1.0 2.5
   * 0.0 1.0
   * 0.0 0.0
   *
   * Magic: 1.0
   * Proof: 0.9999999999999991
   * </pre>
   * </blockquote>
   *
   * @author Spurgeon (John)
   *
   * @param args
   *
   *   An array of strings. Strings that can be converted to values
   *   of type <code>double</code> will be interpreted as coordinates;
   *   otherwise, they will be ignored.
   */
  public static void main(String[] args) {

    // Variable Declarations

    double[][] matrix;
    String matStr;
    double magicSum, checkSum;
    double[][][] triangles;

    // Variable Initialization

    matrix = ShoelaceMatrix.parseMatrix(args);
    matStr = ShoelaceMatrix.toString(matrix);
    magicSum = ShoelaceMatrix.crossMultiply(matrix);
    triangles = ShoelaceMatrix.toTriangles(matrix);
    checkSum = Adder.sumAreasOf(triangles);

    // Output

    System.out.println("Shoelace Formula\n");
    System.out.println("Matrix\n\n" + matStr);
    System.out.println("Magic: " + magicSum);
    System.out.println("Proof: " + checkSum);
  }
}

class ShoelaceMatrix {

  public static double[][] parseMatrix(String[] args) {

    // See: https://en.wikipedia.org/wiki/Shoelace_formula

    final int n = args.length;        // number of arguments
    int i, j, i2;                     // index/counter variables
    double[] tmp = new double[n];     // temporary array
    double[][] matrix;                // the shoelace matrix

    // Initialize an array with coordinate values.

    i = j = 0;
    while (i + 1 < n) {
      try {
        double x = Double.parseDouble(args[i]);
        i++;
        double y = Double.parseDouble(args[i]);
        i++;
        tmp[j] = x;
        j++;
        tmp[j] = y;
        j++;
      }
      catch (Exception e) {
        i++;
      }
    }

    // Create and return a two-dimensional matrix.

    final int m = (j / 2) + 1; // number of rows in matrix

    matrix = new double[m][2];
    for (i = 0; i + 1 < m; i++) {
      i2 = i * 2;
      matrix[i][0] = tmp[i2];     // abscissa (x)
      matrix[i][1] = tmp[i2 + 1]; // ordinate (y)
    }

    matrix[i] = matrix[0]; // Mathew 20:16

    return matrix;
  }

  public static double crossMultiply(double[][] matrix) {

    final int n = matrix.length; // number of rows
    double det;                  // a determinant
    double a, b, c, d;           // coordinate values
    double sum = 0;              // running total

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return sum / 2;
  }

  public static String toString(double[][] matrix) {

    final int n = matrix.length; // number of rows
    String s = "";               // string to return

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return s;
  }

  public static double[][][] toTriangles(double[][] matrix) {

    final int n = matrix.length;     // number of rows
    final int m = n > 2 ? n - 3 : 0; // number of triangles 
    double[] coord1, coord2, coord3; // coordinates
    double[][][] triangles;          // array of coordinates triplets

    triangles = new double[m][][];

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return triangles;
  }
}

class Path {

  public static double getLengthOf(double[][] path) {

    int n = path.length;     // number of points
    double dx, dy;           // delta (change in) value
    double[] coord1, coord2; // coordinate values
    double sum = 0;          // sum of lengths of segments

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return sum;
  }

}

class Polygon {

  public static double[] getLengthsOfSides(double[][] polygon) {

    final int n = polygon.length; // number of vertices
    double[] lengthsOfSides;      // array of lengths 

    lengthsOfSides = new double[n];

    /* MISSING CODE BEGINS HERE */
    // Hint: Use Path.getLengthOf
    /* MISSING CODE ENDS HERE */

    return lengthsOfSides;
  }

}

class Triangle {

  public static double getAreaGivenSides(double a, double b, double c) {

    // See: https://en.wikipedia.org/wiki/Heron%27s_formula

    double area = 0;
    double s; // semiperimeter (half of a + b + c)

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return area;
  }

  public static double getArea(double[][] triangle) {

    double area = 0;
    double[] sss = Polygon.getLengthsOfSides(triangle);
    double a = sss[0], b = sss[1], c = sss[2];

    /* MISSING CODE BEGINS HERE */
    // Hint use Triangle.getAreaGivenSides
    /* MISSING CODE ENDS HERE */

    return area;
  }

}

class Adder {

  public static double sumAreasOf(double[][][] triangles) {

    final int n = triangles.length; // number of triangles
    double sum = 0;                 // sum of areas of triangles
    double[][] triangle;            // an array of three coordinates
    double[] sss;                   // an array of three side lengths
    double a, b, c;                 // the length of a side

    /* MISSING CODE BEGINS HERE */
    // Hint: Use Triangle.getArea
    /* MISSING CODE ENDS HERE */

    return sum;
  }

}

/**
 * The <code>Path</code> class defines operations that may be
 * performed on path values defined by sequences of cartesian
 * coordinates.
 */
class Path {
  
  /**
   * Computes and returns the length of a path by summing the
   * distances between consecutive points in the path.
   *
   * @author Spurgeon (John)
   *
   * @param path
   *
   *   An array of points where each point is represented by an
   *   array of ordered pairs of real numbers, i.e. coordinates.
   */
  public static double getLengthOf(double[][] path) {
    
    int n = path.length;     // number of points
    double dx, dy;           // delta (change in) value
    double[] coord1, coord2; // coordinate values
    double sum = 0;          // sum of lengths of segments
    
    /* MISSING CODE BEGINS HERE */
    for (int i = 0; i + 1 < n; i++) {
      coord1 = path[i];
      coord2 = path[i + 1];
      double x1 = coord1[0], y1 = coord1[1];
      double x2 = coord2[0], y2 = coord2[1];
      dx = x2 - x1;
      dy = y2 - y1;
      double dist = Math.sqrt(dx * dx + dy * dy);
      sum += dist;
    }
    /* MISSING CODE ENDS HERE */
    
    return sum;
  }
  
  /**
   * Tests the methods of the <code>Path</code> class.
   *
   * @author Spurgeon (John)
   *
   * @param args
   *
   *   The command line arguments passed to the program
   *   when the program is executed, which are ignored.
   */
  public static void main(String[] args) {
    
    // Test Data
    
    final double EPSILON = 1E-12;
    final double[][] points = {
      {0, 0},
      {0, 1},
      {2, 1}
    };
    final double[][][] paths = {
      {points[0]},
      {points[0], points[1]},
      {points[0], points[1], points[2]}
    };
    final double[] actual = {
      getLengthOf(paths[0]),
      getLengthOf(paths[1]),
      getLengthOf(paths[2])
    };
    final double[] expect = {0, 1, 3};
    final int n = paths.length;
    
    // Test Execution and Output
    
    System.out.println("Testing Path.getLengthOf");
    System.out.println("Tolerance: " + EPSILON);
    for (int i = 0; i < n; i++) {
      double a = actual[i], e = expect[i];
      boolean closeEnough = Math.abs(a - e) <= EPSILON;
      System.out.print(closeEnough ? "Pass" : "Fail");
      System.out.println(": expect " + e + ", actual " + a);
    }
  }
  
}

/**
 * The <code>ShoelaceMatrix</code> class contains methods for working
 * with a two-dimensional matrix of values arranged specifically for
 * use with the famous Shoelace Formula, which can be used to compute
 * the area of a simple polygon. Each row in such a matrix is a single
 * dimensional array containing two values (coordinates) representing
 * a point in two-dimensional space. The first and last rows refer to
 * the same point.
 */
class ShoelaceMatrix {

  /******************/
  /* Public Methods */
  /******************/

  /**
   * Reads a sequence of strings and returns a corresponding matrix.
   * Strings that can't be converted to floating-point numbers of type
   * <code>double</code> are ignored. The first two converted values
   * are treated as (x, y) coordinates defining a point and make up
   * the first row of the matrix. The next two converted values
   * represent the second point, becoming the second row, and so on.
   * If the number of converted values is odd, then the last value is
   * ignored. The last row in the matrix is a repetition of the first;
   * Hence, if the input array contains n strings that can be converted
   * to floating-point numbers and n is even and not zero, then the
   * matrix returned will contain (n / 2) + 1 rows.
   * 
   * <p>Example:</p>
   *
   * If the value of the parameter <code>args</code> is the sequence
   * of strings:
   *
   * <blockquote>
   * <code>{"0", "0", "oops", "0", "1", "1.5", "1", "1.5", "0"}</code>
   * </blockquote>
   *
   * then the two-dimensional matrix returned will be:
   *
   * <blockquote>
   * <code>{ {0, 0}, {0, 1}, {1.5, 1}, {1.5, 0}, {0, 0} }</code>
   * </blockquote>
   *
   * @author Spurgeon (John)
   *
   * @param args
   *
   *   An array of strings. Values that cannot be converted to
   *   floating point numbers will be ignored.
   *
   * @return
   *
   *   A two-dimensional matrix representing a list of points,
   *   with the first and last rows of the matrix representing
   *   the same point.
   */
  public static double[][] parseMatrix(String[] args) {

    // See: https://en.wikipedia.org/wiki/Shoelace_formula

    final int n = args.length;        // number of arguments
    int i, j, i2;                     // index/counter variables
    double[] tmp = new double[n + 2]; // temporary array
    double[][] matrix;                // the shoelace matrix

    // Initialize an array with coordinate values.

    i = j = 0;
    while (i + 1 < n) {
      try {
        double x = Double.parseDouble(args[i]);
        i++;
        double y = Double.parseDouble(args[i]);
        i++;
        tmp[j] = x;
        j++;
        tmp[j] = y;
        j++;
      }
      catch (Exception e) {
        i++;
      }
    }

    // Create and return a two-dimensional matrix.

    final int m = (j / 2) + 1; // number of rows in matrix

    matrix = new double[m][2];
    for (i = 0; i + 1 < m; i++) {
      i2 = i * 2;
      matrix[i][0] = tmp[i2];     // abscissa (x)
      matrix[i][1] = tmp[i2 + 1]; // ordinate (y)
    }

    matrix[i] = matrix[0]; // Mathew 20:16

    return matrix;
  }

  /**
   * Per the shoelace formula, performs cross multiplication
   * on a two-dimensional matrix.
   *
   * <p>Example:</p>
   *
   * If the value of the parameter <code>matrix</code> is:
   *
   * <blockquote>
   * <code>{ {0, 0}, {0, 1}, {1.5, 1}, {1.5, 0}, {0, 0} }</code>
   * </blockquote>
   *
   * then the value returned is:
   *
   * <blockquote>
   * <pre>
   * 0.5 * (
   * | det {{0, 0}, {0, 1}} | +
   * | det {{0, 1}, {1.5, 1}} | +
   * | det {{1.5, 1}, {1.5, 0}} | +
   * | det {{1.5, 0}, {0, 0}} |
   * )
   * = 0.5 * (
   * |0 * 1 - 0 * 0| +
   * |0 * 1 - 1 * 1.5| +
   * |1.5 * 0 - 1.5 * 1| +
   * |1.5 * 0 - 0 * 0|
   * )
   * = 0.5 * (0 + 1.5 * 1.5 * 0)
   * = 1.5
   * </pre>
   * </blockquote>
   *
   * <p>In the example above, <code>det</code> refers to the
   * determinant of a matrix; for example, the determinant
   * of the 2 x 2 matrix <code>{{a, b}, {c, d}}</code> is the
   * value <code>a * d - b * c</code>. The notation
   * <code>| x |</code> means the absolute value of x.</p>
   *
   * @author Spurgeon (John)
   *
   * @param matrix
   *
   *   A two-dimensional matrix representing a list of points,
   *   with the first and last rows of the matrix representing
   *   the same point.
   *
   * @return
   *
   *   A floating-point number determined by summing the
   *   absolute values of determinants of 2x2 matrices and
   *   dividing the sum in half.
   */
  public static double crossMultiply(double[][] matrix) {

    final int n = matrix.length; // number of rows
    double det;                  // a determinant
    double a, b, c, d;           // coordinate values
    double sum = 0;              // running total

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return sum / 2;
  }

  /**
   * Converts a two-dimensional array of values into a
   * string of characters representing the same matrix.
   *
   * @author Spurgeon (John)
   *
   * @param matrix
   *
   *   A two-dimensional array to be converted to a string.
   *
   * @return
   *
   *   A string representation of the value of the parameter
   *   <code>matrix</code>.
   */
  public static String toString(double[][] matrix) {

    final int n = matrix.length; // number of rows
    String s = "";               // string to return

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return s;
  }

  /**
   * Converts a "shoelace matrix" into an array of values
   * representing a set of triangles defined by 3-tuples or
   * triplets of vertices of the polygon represented by the
   * matrix. Each triangle in the set of triangles represented
   * by the three-dimensional array the method returns has one
   * vertex in common; the other two vertices are unique
   * adjacent pairs of verticies from the set of vertices
   * that define the polygon represented by the matrix.
   *
   * <p>A matrix with n rows (where each row represents a
   * point or vertex) represents n - 1 distinct, successive
   * points with the first and last row referencing the same
   * point. If such a matrix represents a convext polygon
   * (with n - 1 vertices) then the polygon can be partitioned
   * into m triangles where the value of m is the number of
   * vertices minus two (n - 1 - 2 = n - 3).</p>
   *
   * <p>Example:</p>
   *
   * If the value of the parameter <code>matrix</code> is:
   *
   * <blockquote>
   * <code>{ {0, 0}, {0, 1}, {1.5, 1}, {1.5, 0}, {0, 0} }</code>
   * </blockquote>
   *
   * then the three-dimensional array returned would be:
   *
   * <blockquote>
   * <pre>
   * {
   *   { {0, 0}, {0, 1}, {1.5, 1} },
   *   { {0, 0}, {1.5, 1}, {1.5, 0} }
   * }
   * </pre>
   * </blockquote>
   *
   * @author Spurgeon (John)
   *
   * @param matrix
   *
   *   A two-dimensional array to be converted to a list of
   *   values representing a set of triangles.
   *
   * @return
   *
   *   A list of values representing a set of triangles.
   */
  public static double[][][] toTriangles(double[][] matrix) {

    final int n = matrix.length;     // number of rows
    final int m = n > 2 ? n - 3 : 0; // number of triangles 
    double[] coord1, coord2, coord3; // coordinates
    double[][][] triangles;          // array of coordinates triplets

    triangles = new double[m][][];

    /* MISSING CODE BEGINS HERE */
    /* MISSING CODE ENDS HERE */

    return triangles;
  }

  /**
   * Tests public methods of the <code>ShoelaceMatrix</code> class.
   *
   * @author Spurgeon (John)
   * @param args Command-line arguments. (Ignored.)
   */
  public static void main(String[] args) {
    testParseMatrix();
    testCrossMultiply();
    testToString();
    testToTriangles();
  }

  /************************/
  /* Private Test Methods */
  /************************/

  private static void testParseMatrix() {
    String result = "Testing ShoelaceMatrix.parseMatrix: ";
    String[] args = {"0", "0", "oops", "0", "1", "1.5", "1", "1.5", "0"};
    double[][]
      actual = ShoelaceMatrix.parseMatrix(args),
      expect = { {0, 0}, {0, 1}, {1.5, 1}, {1.5, 0}, {0, 0} };
    result += Tester.are2DArraysEqual(actual, expect) ? "Pass" : "Fail";
    System.out.println(result);
  }

  private static void testCrossMultiply() {
    String result = "Testing ShoelaceMatrix.crossMultiply: ";
    /* TO DO */
    System.out.println(result);
  }

  private static void testToString() {
    String result = "Testing ShoelaceMatrix.toString: ";
    double[][] matrix = { {0, 0}, {0, 1}, {1.5, 1}, {1.5, 0}, {0, 0} };
    String
      actual = ShoelaceMatrix.toString(matrix),
      expect = "0.0 0.0\n0.0 1.0\n1.5 1.0\n1.5 0.0\n0.0 0.0\n";
    result += actual.equals(expect) ? "Pass" : "Fail";
    System.out.println(result);
  }

  private static void testToTriangles() {
    String result = "Testing ShoelaceMatrix.toTriangles: ";
    /* TO DO */
    System.out.println(result);
  }

}

/**
 * The <code>Tester</code> class provides methods that can be used
 * to test values of various data structures.
 */
class Tester {

  /**
   * Determines whether the elemental values of two 1D arrays are equal.
   *
   * @author Spurgeon (John)
   * @param a1 A one-dimensional array.
   * @param a2 Another one-dimensional array.
   * @return True if the elemental values are the same; false otherwise.
   */
  public static boolean are1DArraysEqual(double[] a1, double[] a2) {
    if ((a1 == null || a2 == null) && a1 != a2) {
      return false;
    }
    int n = a1.length;
    if (n != a2.length) {
      return false;
    }
    for (int i = 0; i < n; i++) {
      if (a1[i] != a2[i]) {
        return false;
      }
    }
    return true;
  }

  /**
   * Determines whether the elemental values of two 2D arrays are equal.
   *
   * @author Spurgeon (John)
   * @param a1 A two-dimensional array.
   * @param a2 Another two-dimensional array.
   * @return True if the elemental values are the same; false otherwise.
   */
  public static boolean are2DArraysEqual(double[][] a1, double[][] a2) {
    if ((a1 == null || a2 == null) && a1 != a2) {
      return false;
    }
    int n = a1.length;
    if (n != a2.length) {
      return false;
    }
    for (int i = 0; i < n; i++) {
      if (!Tester.are1DArraysEqual(a1[i], a2[i])) {
        return false;
      }
    }
    return true;
  }

  /**
   * Determines whether the elemental values of two 3D arrays are equal.
   *
   * @author Spurgeon (John)
   * @param a1 A three-dimensional array.
   * @param a2 Another three-dimensional array.
   * @return True if the elemental values are the same; false otherwise.
   */
  public static boolean are3DArraysEqual(double[][][] a1, double[][][] a2) {
    if ((a1 == null || a2 == null) && a1 != a2) {
      return false;
    }
    int n = a1.length;
    if (n != a2.length) {
      return false;
    }
    for (int i = 0; i < n; i++) {
      if (!Tester.are2DArraysEqual(a1[i], a2[i])) {
        return false;
      }
    }
    return true;
  }

}

public class Grader {

  public static void main(String[] args) {

    String[] // simulated command-line arguments
      argsTriN   = {"3", "0", "0", "4", "-3", "0"},
      argsTriW   = {"-3", "0", "-7", "-3", "-3", "-6"},
      argsTriS   = {"-3", "-6", "0", "-10", "3", "-6"},
      argsTriE   = {"3", "-6", "7", "-3", "3", "0"},
      argsTriNE  = {"-3", "0", "3", "0", "-3", "-6"},
      argsTriSW  = {"-3", "0", "-3", "-6", "3", "-6"}, 
      argsStar   = {
        "3", "0",
        "0", "4",
        "-3", "0",
        "-7", "-3",
        "-3", "-6",
        "0", "-10",
        "3", "-6",
        "7", "-3"
      },
      argsSquare = {
        "3", "0",
        "-3", "0",
        "-3", "-6",
        "3", "-6"
      };

    double[] // points
      pNE = {3, 0},
      pN  = {0, 4},
      pNW = {-3, 0},
      pW  = {-7, -3},
      pSW = {-3, -6},
      pS  = {0, -10},
      pSE = {3, -6},
      pE  = {7, -3};

    double[][] // matrices
      matTriN   = ShoelaceMatrix.parseMatrix(argsTriN),
      matTriW   = ShoelaceMatrix.parseMatrix(argsTriW),
      matTriS   = ShoelaceMatrix.parseMatrix(argsTriS),
      matTriE   = ShoelaceMatrix.parseMatrix(argsTriE),
      matTriNE  = ShoelaceMatrix.parseMatrix(argsTriNE),
      matTriSW  = ShoelaceMatrix.parseMatrix(argsTriSW), 
      matStar   = ShoelaceMatrix.parseMatrix(argsStar),
      matSquare = ShoelaceMatrix.parseMatrix(argsSquare);

    double[][] // polygons and paths
      triN   = {pNE, pN, pNW},
      triW   = {pNW, pW, pSW},
      triS   = {pSW, pS, pSE},
      triE   = {pSE, pE, pNE},
      triNE  = {pNW, pNE, pSE},
      triSW  = {pNW, pSW, pSE}, 
      star   = {pNE, pN, pNW, pW, pSW, pS, pSE, pE},
      square = {pNE, pNW, pSW, pSE};

    double[][][] // arrays of triangles
      singleTriN  = {triN},
      singleTriW  = {triW},
      singleTriS  = {triS},
      singleTriE  = {triE},
      singleTriNE = {triNE},
      singleTriSW = {triSW},
      triangles   = {triN, triW, triS, triE, triNE, triSW},
      squarePair  = {triNE, triSW};

    double // path lengths (not circumferences)
      lenTriN   = Path.getLengthOf(triN),
      lenTriW   = Path.getLengthOf(triW),
      lenTriS   = Path.getLengthOf(triS),
      lenTriE   = Path.getLengthOf(triE),
      lenTriNE  = Path.getLengthOf(triNE),
      lenTriSW  = Path.getLengthOf(triSW),
      lenStar   = Path.getLengthOf(star),
      lenSquare = Path.getLengthOf(square);

    double // areas computed by summing areas of triangles
      aSumTriN   = Adder.sumAreasOf(singleTriN),
      aSumTriW   = Adder.sumAreasOf(singleTriW),
      aSumTriS   = Adder.sumAreasOf(singleTriS),
      aSumTriE   = Adder.sumAreasOf(singleTriE),
      aSumTriNE  = Adder.sumAreasOf(singleTriNE),
      aSumTriSW  = Adder.sumAreasOf(singleTriSW),
      aSumStar   = Adder.sumAreasOf(triangles),
      aSumSquare = Adder.sumAreasOf(squarePair);

    double // areas computed using the shoelace formula
      aShoeTriN   = ShoelaceMatrix.crossMultiply(matTriN),
      aShoeTriW   = ShoelaceMatrix.crossMultiply(matTriW),
      aShoeTriS   = ShoelaceMatrix.crossMultiply(matTriS),
      aShoeTriE   = ShoelaceMatrix.crossMultiply(matTriE),
      aShoeTriNE  = ShoelaceMatrix.crossMultiply(matTriNE),
      aShoeTriSW  = ShoelaceMatrix.crossMultiply(matTriSW),
      aShoeStar   = ShoelaceMatrix.crossMultiply(matStar),
      aShoeSquare = ShoelaceMatrix.crossMultiply(matSquare);

    final double EPSILON = 1E-12;

    // Evaluate Results

    boolean[] tests = {
      (lenTriN == 5.0 * 2),                          // 0
      (lenTriW == 5.0 * 2),                          // 1
      (lenTriS == 5.0 * 2),                          // 2
      (lenTriE == 5.0 * 2),                          // 3
      (lenTriNE == 6.0 * 2),                         // 4
      (lenTriSW == 6.0 * 2),                         // 5
      (lenStar == 5.0 * 7),                          // 6
      (lenSquare == 6.0 * 3),                        // 7
      (aShoeTriN == 12.0),                           // 8
      (aShoeTriW == 12.0),                           // 9
      (aShoeTriS == 12.0),                           // 10
      (aShoeTriE == 12.0),                           // 11
      (aShoeTriNE == 18.0),                          // 12
      (aShoeTriSW == 18.0),                          // 13
      (aShoeStar == (12.0 * 4) + 36.0),              // 14
      (aShoeSquare == 36.0),                         // 15
      (Math.abs(aShoeTriN - aSumTriN) < EPSILON),    // 16
      (Math.abs(aShoeTriW - aSumTriW) < EPSILON),    // 17
      (Math.abs(aShoeTriS - aSumTriS) < EPSILON),    // 18
      (Math.abs(aShoeTriE - aSumTriE) < EPSILON),    // 19
      (Math.abs(aShoeTriNE - aSumTriNE) < EPSILON),  // 20
      (Math.abs(aShoeTriSW - aSumTriSW) < EPSILON),  // 21
      (Math.abs(aShoeStar - aSumStar) < EPSILON),    // 22
      (Math.abs(aShoeSquare - aSumSquare) < EPSILON) // 23
    };

    // Output Evaluation

    boolean passed = true;
    int numTests = tests.length;
    for (int i = 0; i < numTests; i++) {
      if (!tests[i]) {
        System.out.println("Failed test " + i);
        passed = false;
      }
    }
    if (passed) {
      System.out.println("Passed!");
    }

    // Execute the main method of the ShoestringMath class.

    ShoestringMath.main(argsTriN);
    ShoestringMath.main(argsTriW);
    ShoestringMath.main(argsTriS);
    ShoestringMath.main(argsTriE);
    ShoestringMath.main(argsTriNE);
    ShoestringMath.main(argsTriSW);
    ShoestringMath.main(argsStar);
    ShoestringMath.main(argsSquare);
    ShoestringMath.main(args);
  }

}

class ShoestringMath {

  public static void main(String[] args) {

    // Variable Declarations

    double[][] matrix;
    String matStr;
    double magicSum, checkSum;
    double[][][] triangles;

    // Variable Initialization

    matrix = ShoelaceMatrix.parseMatrix(args);
    matStr = ShoelaceMatrix.toString(matrix);
    magicSum = ShoelaceMatrix.crossMultiply(matrix);
    triangles = ShoelaceMatrix.toTriangles(matrix);
    checkSum = Adder.sumAreasOf(triangles);

    // Output

    System.out.print("Arguments:");
    for (String s : args) {
      System.out.print(" " + s);
    }
    System.out.println("\n\nShoelace Matrix:\n\n" + matStr);
    System.out.println("Cross: " + magicSum);
    System.out.println("Check: " + checkSum);
    System.out.println("Delta: " + Math.abs(checkSum - magicSum));
    System.out.println();
  }

}

class ShoelaceMatrix {

  public static double[][] parseMatrix(String[] args) {

    // See: https://en.wikipedia.org/wiki/Shoelace_formula

    final int n = args.length;        // number of arguments
    int i, j, i2;                     // index/counter variables
    double[] tmp = new double[n];     // temporary array
    double[][] matrix;                // the shoelace matrix

    // Initialize an array with coordinate values.

    i = j = 0;
    while (i + 1 < n) {
      try {
        double x = Double.parseDouble(args[i]);
        i++;
        double y = Double.parseDouble(args[i]);
        i++;
        tmp[j] = x;
        j++;
        tmp[j] = y;
        j++;
      }
      catch (Exception e) {
        i++;
      }
    }

    // Create and return a two-dimensional matrix.

    final int m = (j / 2) + 1; // number of rows in matrix

    matrix = new double[m][2];
    for (i = 0; i + 1 < m; i++) {
      i2 = i * 2;
      matrix[i][0] = tmp[i2];     // abscissa (x)
      matrix[i][1] = tmp[i2 + 1]; // ordinate (y)
    }

    matrix[i] = matrix[0]; // Mathew 20:16

    return matrix;
  }

  public static double crossMultiply(double[][] matrix) {

    final int n = matrix.length; // number of rows
    double det;                  // a determinant
    double a, b, c, d;           // coordinate values
    double sum = 0;              // running total

    for (int i = 0; i + 1 < n; i++) {
      a = matrix[i][0];
      b = matrix[i][1];
      c = matrix[i + 1][0];
      d = matrix[i + 1][1];

      /* BUG BEGINS HERE */
      det = 0; // Hint: Carefully multiply and subtract.
      /* BUG ENDS HERE */

      sum += det;
    }

    return Math.abs(sum / 2);
  }

  public static String toString(double[][] matrix) {

    final int n = matrix.length; // number of rows
    String s = "";               // string to return

    /* BUG BEGINS HERE // HINT: It's me not you. (The bug is on this line.)
    for (int i = 0; i < n; i++) {
      s += matrix[i][0];
      s += " ";
      s += matrix[i][1];
      s += "\n";
    }
    /* BUG ENDS HERE */

    return s;
  }

  public static double[][][] toTriangles(double[][] matrix) {

    final int n = matrix.length;     // number of rows
    final int m = n > 2 ? n - 3 : 0; // number of triangles 
    double[] coord1, coord2, coord3; // coordinates
    double[][][] triangles;          // array of coordinates triplets

    triangles = new double[m][][];

    /* BUG BEGINS HERE */
    for (int i = 0; false; i++) { // Hint: Not false. (Tricky!)
    /* BUG ENDS HERE */

      coord1 = matrix[0];
      coord2 = matrix[i + 1];
      coord3 = matrix[i + 2];
      double[][] triangle = {coord1, coord2, coord3};
      triangles[i] = triangle;
    }

    return triangles;
  }
}

class Path {

  public static double getLengthOf(double[][] path) {

    int n = path.length;     // number of points
    double dx, dy;           // delta (change in) value
    double[] coord1, coord2; // coordinate values
    double sum = 0;          // sum of lengths of segments

    for (int i = 0; i + 1 < n; i++) {
      coord1 = path[i];
      coord2 = path[i + 1];
      double x1 = coord1[0], y1 = coord1[1];
      double x2 = coord2[0], y2 = coord2[1];
      dx = x2 - x1;
      dy = y2 - y1;

      /* BUG BEGINS HERE */
      double dist = 0; // Hint: Use Math.sqrt().
      /* BUG ENDS HERE */

      sum += dist;
    }

    return sum;
  }

}

class Polygon {

  public static double[] getLengthsOfSides(double[][] polygon) {

    final int n = polygon.length; // number of vertices
    double[] lengthsOfSides;      // array of lengths 

    lengthsOfSides = new double[n];

    for (int i = 0; i < n; i++) {

      /* BUG BEGINS HERE */
      int j = 0; // Hint: Use the % operator.
      /* BUG ENDS HERE */

      double[][] segment = {polygon[i], polygon[j]};
      lengthsOfSides[i] = Path.getLengthOf(segment);
    }

    return lengthsOfSides;
  }

}

class Triangle {

  public static double getAreaGivenSides(double a, double b, double c) {

    // See: https://en.wikipedia.org/wiki/Heron%27s_formula

    double area = 0;
    double s; // semiperimeter (half of a + b + c)

    s = (a + b + c) / 2.0;

    /* BUG BEGINS HERE */
    area = 0; // Hint: Use Math.sqrt().
    /* BUG ENDS HERE */

    return area;
  }

  public static double getArea(double[][] triangle) {

    double area = 0;
    double[] sss = Polygon.getLengthsOfSides(triangle);
    double a = sss[0], b = sss[1], c = sss[2];

    /* BUG BEGINS HERE */
      area = 0; // Hint: Use another method from this class.
    /* BUG ENDS HERE */

    return area;
  }

}

class Adder {

  public static double sumAreasOf(double[][][] triangles) {

    final int n = triangles.length; // number of triangles
    double sum = 0;                 // sum of areas of triangles
    double[][] triangle;            // an array of three coordinates

    for (int i = 0; i < n; i++) {
      triangle = triangles[i];

    /* BUG BEGINS HERE */
      sum += 0; // Hint: Use a method from the Triangle class.
    /* BUG ENDS HERE */

    }

    return sum;
  }

}

public class Grader {

  public static void main(String[] args) {

    String[] // simulated command-line arguments
      argsTriN   = {"3", "0", "0", "4", "-3", "0"},
      argsTriW   = {"-3", "0", "-7", "-3", "-3", "-6"},
      argsTriS   = {"-3", "-6", "0", "-10", "3", "-6"},
      argsTriE   = {"3", "-6", "7", "-3", "3", "0"},
      argsTriNE  = {"-3", "0", "3", "0", "-3", "-6"},
      argsTriSW  = {"-3", "0", "-3", "-6", "3", "-6"}, 
      argsStar   = {
        "3", "0",
        "0", "4",
        "-3", "0",
        "-7", "-3",
        "-3", "-6",
        "0", "-10",
        "3", "-6",
        "7", "-3"
      },
      argsSquare = {
        "3", "0",
        "-3", "0",
        "-3", "-6",
        "3", "-6"
      };

    double[] // points
      pNE = {3, 0},
      pN  = {0, 4},
      pNW = {-3, 0},
      pW  = {-7, -3},
      pSW = {-3, -6},
      pS  = {0, -10},
      pSE = {3, -6},
      pE  = {7, -3};

    double[][] // matrices
      matTriN   = ShoelaceMatrix.parseMatrix(argsTriN),
      matTriW   = ShoelaceMatrix.parseMatrix(argsTriW),
      matTriS   = ShoelaceMatrix.parseMatrix(argsTriS),
      matTriE   = ShoelaceMatrix.parseMatrix(argsTriE),
      matTriNE  = ShoelaceMatrix.parseMatrix(argsTriNE),
      matTriSW  = ShoelaceMatrix.parseMatrix(argsTriSW), 
      matStar   = ShoelaceMatrix.parseMatrix(argsStar),
      matSquare = ShoelaceMatrix.parseMatrix(argsSquare);

    double[][] // polygons and paths
      triN   = {pNE, pN, pNW},
      triW   = {pNW, pW, pSW},
      triS   = {pSW, pS, pSE},
      triE   = {pSE, pE, pNE},
      triNE  = {pNW, pNE, pSE},
      triSW  = {pNW, pSW, pSE}, 
      star   = {pNE, pN, pNW, pW, pSW, pS, pSE, pE},
      square = {pNE, pNW, pSW, pSE};

    double[][][] // arrays of triangles
      singleTriN  = {triN},
      singleTriW  = {triW},
      singleTriS  = {triS},
      singleTriE  = {triE},
      singleTriNE = {triNE},
      singleTriSW = {triSW},
      triangles   = {triN, triW, triS, triE, triNE, triSW},
      squarePair  = {triNE, triSW};

    double // path lengths (not circumferences)
      lenTriN   = Path.getLengthOf(triN),
      lenTriW   = Path.getLengthOf(triW),
      lenTriS   = Path.getLengthOf(triS),
      lenTriE   = Path.getLengthOf(triE),
      lenTriNE  = Path.getLengthOf(triNE),
      lenTriSW  = Path.getLengthOf(triSW),
      lenStar   = Path.getLengthOf(star),
      lenSquare = Path.getLengthOf(square);

    double // areas computed by summing areas of triangles
      aSumTriN   = Adder.sumAreasOf(singleTriN),
      aSumTriW   = Adder.sumAreasOf(singleTriW),
      aSumTriS   = Adder.sumAreasOf(singleTriS),
      aSumTriE   = Adder.sumAreasOf(singleTriE),
      aSumTriNE  = Adder.sumAreasOf(singleTriNE),
      aSumTriSW  = Adder.sumAreasOf(singleTriSW),
      aSumStar   = Adder.sumAreasOf(triangles),
      aSumSquare = Adder.sumAreasOf(squarePair);

    double // areas computed using the shoelace formula
      aShoeTriN   = ShoelaceMatrix.crossMultiply(matTriN),
      aShoeTriW   = ShoelaceMatrix.crossMultiply(matTriW),
      aShoeTriS   = ShoelaceMatrix.crossMultiply(matTriS),
      aShoeTriE   = ShoelaceMatrix.crossMultiply(matTriE),
      aShoeTriNE  = ShoelaceMatrix.crossMultiply(matTriNE),
      aShoeTriSW  = ShoelaceMatrix.crossMultiply(matTriSW),
      aShoeStar   = ShoelaceMatrix.crossMultiply(matStar),
      aShoeSquare = ShoelaceMatrix.crossMultiply(matSquare);

    final double EPSILON = 1E-12;

    // Execute tests.

    boolean[] tests = {
      (lenTriN == 5.0 * 2),                          // 0
      (lenTriW == 5.0 * 2),                          // 1
      (lenTriS == 5.0 * 2),                          // 2
      (lenTriE == 5.0 * 2),                          // 3
      (lenTriNE == 6.0 * 2),                         // 4
      (lenTriSW == 6.0 * 2),                         // 5
      (lenStar == 5.0 * 7),                          // 6
      (lenSquare == 6.0 * 3),                        // 7
      (aShoeTriN == 12.0),                           // 8
      (aShoeTriW == 12.0),                           // 9
      (aShoeTriS == 12.0),                           // 10
      (aShoeTriE == 12.0),                           // 11
      (aShoeTriNE == 18.0),                          // 12
      (aShoeTriSW == 18.0),                          // 13
      (aShoeStar == (12.0 * 4) + 36.0),              // 14
      (aShoeSquare == 36.0),                         // 15
      (Math.abs(aShoeTriN - aSumTriN) < EPSILON),    // 16
      (Math.abs(aShoeTriW - aSumTriW) < EPSILON),    // 17
      (Math.abs(aShoeTriS - aSumTriS) < EPSILON),    // 18
      (Math.abs(aShoeTriE - aSumTriE) < EPSILON),    // 19
      (Math.abs(aShoeTriNE - aSumTriNE) < EPSILON),  // 20
      (Math.abs(aShoeTriSW - aSumTriSW) < EPSILON),  // 21
      (Math.abs(aShoeStar - aSumStar) < EPSILON),    // 22
      (Math.abs(aShoeSquare - aSumSquare) < EPSILON) // 23
    };

    // Output test results.

    int numTests = tests.length;
    for (int i = 0; i < numTests; i++) {
      if (!tests[i]) {
        System.out.println("Failed test " + i);
      }
    }

    // Execute the main method of the ShoestringMath class.

    ShoestringMath.main(argsTriN);
    ShoestringMath.main(argsTriW);
    ShoestringMath.main(argsTriS);
    ShoestringMath.main(argsTriE);
    ShoestringMath.main(argsTriNE);
    ShoestringMath.main(argsTriSW);
    ShoestringMath.main(argsStar);
    ShoestringMath.main(argsSquare);
    ShoestringMath.main(args);
  }

}

Q&A

Notes

Exercises

Study the source code for the ShoestringMath class, including the associated Javadoc comments. Then study the source code for each of the following classes.
Study the sample solution for the Path class, then create documentation and automated tests for the other classes listed above as follows.
1. Create Javadoc comments for each of the classes and for all of the public methods of the classes that do not already have Javadoc comments.
2. For each of the classes that do not already have a main method, add a main method to the class.
3. Implement each main method so that it tests whether the other public methods of the class function as intended. (Make sure you understand how the methods are supposed to work!)
4. Create Javadoc comments for each of the main methods that you create.
5. Try to improve the sample solution for the Path class.
6. Try organizing your code for the classes listed above in a single file and in multiple files.
  1. Compile your code by placing the code for all classes in a file named ShoestringMath.java. Execute each of your main methods.
  2. Make each of the classes public and put the code for each class in its own file. Save the files in a common directory. Compile the code and execute each of your main methods.
Finish implementing the methods that are missing code.
1. Use the main methods you implemented in the previous exercise to test your implementations, and/or...
2. Start with the Bugger (a gradable buggy program) code listing, fix the bugs int that code, and verify that all the tests defined in the Grader class pass.
3. Test your code using other sets of inputs (command-line arguments). What problems, if any, did you discover?

Solution

/**
 * The <code>ShoestringMath</code> class demonstrates two methods that
 * can be used to compute the area of certain types of simple polygons:
 * <ul>
 * <li> Use a matrix to represent the polygon and cross multiply (the
 *      Shoelace Formula).
 * <li> Divide the polygon into triangles, compute the area of each
        triangle (using Heron's Formula), and sum the areas.
 * </ul>
 */
public class ShoestringMath {

/**
   * Converts command-line arguments to a matrix representing a polygon.
   * Cross multiplies, per the Shoelace Formula, to produce a value.
   * Converts the matrix into an array of coordinate triples, each
   * representing a triangle; computes and sums the areas of the
   * triagles. Outputs the matrix, the result of applying the Shoelace
   * Formula, and the sum of the areas of the triangles. For example,
   * if the command-line arguements are:
   * <blockquote>
   *   <code>0 0 0 1 ignore me 1 2.5 0 1</code>
   * </blockquote>
   * then the output is:
   * <blockquote>
   *   <pre>
   *   Shoelace Formula
   *
   *   Matrix
   *
   *   0.0 0.0
   *   0.0 1.0
   *   1.0 2.5
   *   0.0 1.0
   *   0.0 0.0
   *
   *   Magic: 1.0
   *   Proof: 0.9999999999999991
   *   </pre>
   * </blockquote>
   *
   * @author Spurgeon (John)
   *
   * @param args
   *
   *   An array of strings. Strings that can be converted to values
   *   of type <code>double</code> will be interpreted as coordinates;
   *   otherwise, they will be ignored.
   */
  public static void main(String[] args) {

// Variable Declarations

double[][] matrix;
    String matStr;
    double result, checkSum;
    double[][][] triangles;

// Variable Initialization

matrix = ShoelaceMatrix.parseMatrix(args);
    matStr = ShoelaceMatrix.toString(matrix);
    result = ShoelaceMatrix.crossMultiply(matrix);
    triangles = ShoelaceMatrix.toTriangles(matrix);
    checkSum = Adder.sumAreasOf(triangles);

// Output

System.out.println("Shoelace Formula\n");
    System.out.println("Matrix\n\n" + matStr);
    System.out.println("Magic: " + result);
    System.out.println("Proof: " + checkSum);
  }
}

class ShoelaceMatrix {

public static double[][] parseMatrix(String[] args) {

// See: https://en.wikipedia.org/wiki/Shoelace_formula

final int n = args.length;        // number of arguments
    int i, j, i2;                     // index/counter variables
    double[] tmp = new double[n];     // temporary array
    double[][] matrix;                // the shoelace matrix

// Initialize an array with coordinate values.

i = j = 0;
    while (i + 1 < n) {
      try {
        double x = Double.parseDouble(args[i]);
        i++;
        double y = Double.parseDouble(args[i]);
        i++;
        tmp[j] = x;
        j++;
        tmp[j] = y;
        j++;
      }
      catch (Exception e) {
        i++;
      }
    }

// Create and return a two-dimensional matrix.

final int m = (j / 2) + 1; // number of rows in matrix

matrix = new double[m][2];
    for (i = 0; i + 1 < m; i++) {
      i2 = i * 2;
      matrix[i][0] = tmp[i2];     // abscissa (x)
      matrix[i][1] = tmp[i2 + 1]; // ordinate (y)
    }

matrix[i] = matrix[0]; // Mathew 20:16

return matrix;
  }

public static double crossMultiply(double[][] matrix) {

final int n = matrix.length; // number of rows
    double det;                  // a determinant
    double a, b, c, d;           // coordinate values
    double sum = 0;              // running total

for (int i = 0; i + 1 < n; i++) {
      a = matrix[i][0];
      b = matrix[i][1];
      c = matrix[i + 1][0];
      d = matrix[i + 1][1];
      det = a * d - b * c;
      sum += det;
    }

return Math.abs(sum / 2);
  }

public static String toString(double[][] matrix) {

final int n = matrix.length; // number of rows
    String s = "";               // string to return

for (int i = 0; i < n; i++) {
      s += matrix[i][0];
      s += " ";
      s += matrix[i][1];
      s += "\n";
    }

return s;
  }

public static double[][][] toTriangles(double[][] matrix) {

final int n = matrix.length;     // number of rows
    final int m = n > 2 ? n - 3 : 0; // number of triangles 
    double[] coord1, coord2, coord3; // coordinates
    double[][][] triangles;          // array of coordinates triplets

triangles = new double[m][][];

for (int i = 0; i + 3 < n; i++) {
      coord1 = matrix[0];
      coord2 = matrix[i + 1];
      coord3 = matrix[i + 2];
      double[][] triangle = {coord1, coord2, coord3};
      triangles[i] = triangle;
    }

return triangles;
  }
}

class Path {

public static double getLengthOf(double[][] path) {

int n = path.length;     // number of points
    double dx, dy;           // delta (change in) value
    double[] coord1, coord2; // coordinate values
    double sum = 0;          // sum of lengths of segments

for (int i = 0; i + 1 < n; i++) {
      coord1 = path[i];
      coord2 = path[i + 1];
      double x1 = coord1[0], y1 = coord1[1];
      double x2 = coord2[0], y2 = coord2[1];
      dx = x2 - x1;
      dy = y2 - y1;
      double dist = Math.sqrt(dx * dx + dy * dy);
      sum += dist;
    }

return sum;
  }

}

class Polygon {

public static double[] getLengthsOfSides(double[][] polygon) {

final int n = polygon.length; // number of vertices
    double[] lengthsOfSides;      // array of lengths

lengthsOfSides = new double[n];

for (int i = 0; i < n; i++) {
      int j = (i + 1) % n;
      double[][] segment = {polygon[i], polygon[j]};
      lengthsOfSides[i] = Path.getLengthOf(segment);
    }

return lengthsOfSides;
  }

}

class Triangle {

public static double getAreaGivenSides(double a, double b, double c) {

// See: https://en.wikipedia.org/wiki/Heron%27s_formula

double area = 0;
    double s; // semiperimeter (half of a + b + c)

s = (a + b + c) / 2.0;
    area = Math.sqrt(s * (s - a) * (s - b) * (s - c));

return area;
  }

}

class Adder {

public static double sumAreasOf(double[][][] triangles) {

final int n = triangles.length; // number of triangles
    double sum = 0;                 // sum of areas of triangles
    double[][] triangle;            // an array of three coordinates
    double[] sss;                   // an array of three side lengths
    double a, b, c;                 // the length of a side

for (int i = 0; i < n; i++) {
      triangle = triangles[i];
      sss = Polygon.getLengthsOfSides(triangle);
      a = sss[0];
      b = sss[1];
      c = sss[2];
      sum += Triangle.getAreaGivenSides(a, b, c);
    }

return sum;
  }

}

scribbledecobble

Pages

Shoestring Math

README

See Also

Code

Q&A

Notes

Exercises

Solution