The requirement for this task is to verify the area of polygons. The motivation could be controlling the amount of material used to cut shapes on some type of material. Some time ago led a project that developed a system to print images on film. The software used two hardware devices to keep track of the number of feet used per roll and the total area of all images (polygons) used to generate images by the software.
In this case the description of the polygons (made up of consecutive lines), lines (made of start and end point) and points (3D coordinates) are provided via an XML file. For simplicity and brevity I will skip the code I wrote to load and parse the XML file. The polygons are defined in a 3D space.
Following is the output for the test program from the console of the Eclipse IDE:
main <<< xml file: main <<< fileName ==>c:\temp\surfaces.xml<== main <<< Point [id=C5, x=148.849118968, y=-35.280894216, z=0.0] main <<< Point [id=C6, x=167.386651237, y=-35.280894216, z=6.179177423] main <<< Point [id=C7, x=167.386651237, y=-62.598506625, z=6.179177423] main <<< Point [id=C8, x=148.849118968, y=-62.598506625, z=0.0] main <<< Point [id=C9, x=178.875083323, y=-35.280894216, z=2.349700061] main <<< Point [id=C10, x=178.875083323, y=-31.323411856, z=2.349700061] main <<< Point [id=C11, x=201.711593098, y=-31.323411856, z=-5.262469864] main <<< Point [id=C12, x=201.711593098, y=-42.61799658, z=-5.262469864] main <<< Point [id=C13, x=214.965105828, y=-42.61799658, z=-9.680307441] main <<< Point [id=C14, x=214.965105828, y=-66.872649874, z=-9.680307441] main <<< Point [id=C15, x=188.533782115, y=-66.872649874, z=-0.869866203] main <<< Point [id=C16, x=188.533782115, y=-62.598506625, z=-0.869866203] main <<< Point [id=C17, x=162.910389045, y=-66.872649874, z=-9.410997227] main <<< Point [id=C18, x=162.910389045, y=-60.31390767, z=-9.410997227] main <<< Point [id=C19, x=185.276865726, y=-60.31390767, z=-1.955505] main <<< Line [id=L1, points=[C5, C6], type=RAKE] main <<< Line [id=L2, points=[C8, C5], type=EAVE] main <<< Line [id=L3, points=[C6, C7], type=RIDGE] main <<< Line [id=L4, points=[C7, C8], type=RAKE] main <<< Line [id=L5, points=[C6, C9], type=RAKE] main <<< Line [id=L6, points=[C16, C7], type=RAKE] main <<< Line [id=L7, points=[C9, C10], type=EAVE] main <<< Line [id=L8, points=[C10, C11], type=RAKE] main <<< Line [id=L9, points=[C11, C12], type=EAVE] main <<< Line [id=L10, points=[C12, C13], type=RAKE] main <<< Line [id=L11, points=[C13, C14], type=EAVE] main <<< Line [id=L12, points=[C14, C15], type=RAKE] main <<< Line [id=L13, points=[C15, C16], type=RIDGE] main <<< Line [id=L14, points=[C15, C17], type=RAKE] main <<< Line [id=L15, points=[C19, C16], type=STEPFLASH] main <<< Line [id=L16, points=[C17, C18], type=EAVE] main <<< Line [id=L17, points=[C18, C19], type=STEPFLASH] main <<< Polygon [id=P1, orientation=203.7, lines=[L1, L3, L4, L2], pitch=4.0, area=533.793651249] main <<< Polygon [id=P2, orientation=23.7, lines=[L5, L7, L8, L9, L10, L11, L12, L13, L6, L3], pitch=4.0, area=1481.878887582] main <<< Polygon [id=P3, orientation=203.7, lines=[L14, L16, L17, L15, L13], pitch=4.0, area=173.226255806] main <<< pt: Point [id=C5, x=148.849118968, y=-35.280894216, z=0.0] main <<< pt: Point [id=C6, x=167.386651237, y=-35.280894216, z=6.179177423] main <<< pt: Point [id=C7, x=167.386651237, y=-62.598506625, z=6.179177423] main <<< pt: Point [id=C8, x=148.849118968, y=-62.598506625, z=0.0] main <<< pitch: 4.0 main <<< area: 533.794 == computedArea: 533.794 main <<< pt: Point [id=C6, x=167.386651237, y=-35.280894216, z=6.179177423] main <<< pt: Point [id=C9, x=178.875083323, y=-35.280894216, z=2.349700061] main <<< pt: Point [id=C10, x=178.875083323, y=-31.323411856, z=2.349700061] main <<< pt: Point [id=C11, x=201.711593098, y=-31.323411856, z=-5.262469864] main <<< pt: Point [id=C12, x=201.711593098, y=-42.61799658, z=-5.262469864] main <<< pt: Point [id=C13, x=214.965105828, y=-42.61799658, z=-9.680307441] main <<< pt: Point [id=C14, x=214.965105828, y=-66.872649874, z=-9.680307441] main <<< pt: Point [id=C15, x=188.533782115, y=-66.872649874, z=-0.869866203] main <<< pt: Point [id=C16, x=188.533782115, y=-62.598506625, z=-0.869866203] main <<< pt: Point [id=C7, x=167.386651237, y=-62.598506625, z=6.179177423] main <<< pitch: 4.0 main <<< area: 1481.879 == computedArea: 1481.879 main <<< pt: Point [id=C15, x=188.533782115, y=-66.872649874, z=-0.869866203] main <<< pt: Point [id=C17, x=162.910389045, y=-66.872649874, z=-9.410997227] main <<< pt: Point [id=C18, x=162.910389045, y=-60.31390767, z=-9.410997227] main <<< pt: Point [id=C19, x=185.276865726, y=-60.31390767, z=-1.955505] main <<< pt: Point [id=C16, x=188.533782115, y=-62.598506625, z=-0.869866203] main <<< pitch: 4.0 main <<< area: 173.226 == computedArea: 173.226
The program tests for the file entered by the user. At some point I 
commented out the line that prompts the user and hardcoded the path to one of the sample XML file.
The points are read and displayed. The lines are then read and displayed. Notice that the lines have a starting and an ending point (more on this later). Finally the polygons are displayed.
A loop follows. In it each polygon is selected and the area is computed and verified (to 3 decimal points) that they match.
The Java code for the Point class follows:
package john.polygon.area;
public class Point {
// **** members ****
private String id;
private double x;
private double y;
private double z;
/**
* Constructor.
*/
public Point() {
this.id = "";
this.x = 0.0;
this.y = 0.0;
this.z = 0.0;
}
/**
* Constructor.
*/
public Point(String id, double x, double y, double z) {
this.id = id;
this.x = x;
this.y = y;
this.z = z;
}
/**
* @return the id
*/
public String getId() {
return id;
}
/**
* @param id the id to set
*/
public void setId(String id) {
this.id = id;
}
/**
* @return the x
*/
public double getX() {
return x;
}
/**
* @param x the x to set
*/
public void setX(double x) {
this.x = x;
}
/**
* @return the y
*/
public double getY() {
return y;
}
/**
* @param y the y to set
*/
public void setY(double y) {
this.y = y;
}
/**
* @return the z
*/
public double getZ() {
return z;
}
/**
* @param z the z to set
*/
public void setZ(double z) {
this.z = z;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Point [id=" + id + ", x=" + x + ", y=" + y + ", z=" + z + "]";
}
}
The Java code for the Line class follows:
package john.polygon.area;
import java.util.LinkedList;
public class Line {
// **** members ****
private String id;
private LinkedList<String> points;
private String type;
/**
* Constructor.
*/
public Line() {
this.id = "";
this.points = null;
this.type = "";
}
/**
* Constructor.
*/
public Line(String id, LinkedList<String> points, String type) {
this.id = id;
this.points = points;
this.type = type;
}
/**
* @return the id
*/
public String getId() {
return id;
}
/**
* @param id the id to set
*/
public void setId(String id) {
this.id = id;
}
/**
* @return the points
*/
public LinkedList<String> getPoints() {
return points;
}
/**
* @param points the points to set
*/
public void setPoints(LinkedList<String> points) {
this.points = points;
}
/**
* @return the type
*/
public String getType() {
return type;
}
/**
* @param type the type to set
*/
public void setType(String type) {
this.type = type;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Line [id=" + id + ", points=" + points + ", type=" + type + "]";
}
}
The Java code for the Polygon class follows:
package john.polygon.area;
import java.util.LinkedList;
public class Polygon {
// **** members ****
private String id;
private double orientation;
private LinkedList<String> lines;
private double pitch;
private double area;
/**
* constructor
*/
public Polygon(String id, double orientation, LinkedList<String> lines, double pitch, double area) {
this.id = id;
this.orientation = orientation;
this.lines = lines;
this.pitch = pitch;
this.area = area;
}
/**
* constructor
*/
public Polygon() {
this.id = "";
this.orientation = 0.0;
this.lines = null;
this.pitch = 0.0;
this.area = 0.0;
}
/**
* @return the id
*/
public String getId() {
return id;
}
/**
* @param id the id to set
*/
public void setId(String id) {
this.id = id;
}
/**
* @return the orientation
*/
public double getOrientation() {
return orientation;
}
/**
* @param orientation the orientation to set
*/
public void setOrientation(double orientation) {
this.orientation = orientation;
}
/**
* @return the lines
*/
public LinkedList<String> getLines() {
return lines;
}
/**
* @param path the path to set
*/
public void setLines(LinkedList<String> lines) {
this.lines = lines;
}
/**
* @return the pitch
*/
public double getPitch() {
return pitch;
}
/**
* @param pitch the pitch to set
*/
public void setPitch(double pitch) {
this.pitch = pitch;
}
/**
* @return the area
*/
public double getArea() {
return area;
}
/**
* @param area the area to set
*/
public void setArea(double area) {
this.area = area;
}
/**
*
*/
@Override
public String toString() {
return "Polygon [id=" + id + ", orientation=" + orientation + ", lines=" + lines + ", pitch=" + pitch
+ ", area=" + area + "]";
}
}
Once the classes were implemented I started drawing a UML diagram with the intent to abstract classes and use a Factory class. I decided that it was not worthwhile my time.
The Java code for the Area class that computes the area of polygons follows:
package john.polygon.area;
import java.util.LinkedList;
public class Area {
/**
* Constructor.
*/
public Area() {}
/**
* Generate a list of points associated with the specified polygon
*/
public LinkedList<Point> linesToPoints(Polygon polygon, LinkedList<Line> lines, LinkedList<Point> points) {
LinkedList<Point> polyPoints = new LinkedList<Point>();
String endPointId = "";
// **** get the list of polygon lines ****
LinkedList<String> pLines = polygon.getLines();
// **** traverse the list of polygon lines ****
for (String pLine : pLines) {
// ***** get the name for the points for the line ****
LinkedList<String> lPoints = lineToPoints(pLine, lines);
// **** get the end points for the line ****
LinkedList<Point> endPoints = lineEndPoints(lPoints, points);
// **** add the proper start point to the list ****
if (endPointId.equals("")) {
polyPoints.add(endPoints.get(0));
endPointId = endPoints.get(1).getId();
} else {
// **** use line start point ****
if (endPoints.get(0).getId().equals(endPointId)) {
polyPoints.add(endPoints.get(0));
endPointId = endPoints.get(1).getId();
}
// **** use line end point ****
else {
polyPoints.add(endPoints.get(1));
endPointId = endPoints.get(0).getId();
}
}
}
// **** ****
return polyPoints;
}
/**
* Compute the area for the specified list of points.
* The points must be an ordered list of points for a single polygon.
*/
public double computeArea(LinkedList<Point> polyPoints, double pitch) {
double area = 0.0;
double firstProducts = 0.0;
double secondProducts = 0.0;
double tmp = 0.0;
// **** select points to operate on ****
for (int i = 0; i < polyPoints.size(); i++) {
// **** get the points to be processed ****
Point curPt = polyPoints.get(i);
Point nextPt = null;
if (i == polyPoints.size() - 1) {
nextPt = polyPoints.get(0);
} else {
nextPt = polyPoints.get(i + 1);
}
// **** multiply X coordinate by Y coordinate and add to current total ****
tmp = curPt.getX() * nextPt.getY();
firstProducts += tmp;
// **** multiply Y coordinate by X coordinate and add to current total ****
tmp = curPt.getY() * nextPt.getX();
secondProducts += tmp;
}
// **** subtract totals and divide by 2.0 ****
area = secondProducts - firstProducts;
area /= 2.0;
// **** compensate for pitch (rounded to 3 decimal places) ****
area = adjustForPitch(area, pitch);
// **** rounded to 3 decimal places ****
return area;
}
/**
* Adjust area taking into account the pitch.
*/
private double adjustForPitch(double area, double pitch) {
double cosOfTheta = 12.0 / Math.sqrt(144.0 + (pitch * pitch));
area /= cosOfTheta;
area = Math.round(area * 1000.0);
return area / 1000.0;
}
/**
* Return the end points for the specified point ids.
*/
private LinkedList<Point> lineEndPoints(LinkedList<String> lPoints, LinkedList<Point> points) {
LinkedList<Point> endPoints = new LinkedList<Point>();
// **** traverse the list of points in the line (MUST be 2) ****
for (String lPoint : lPoints) {
// **** look up the point in the list ****
for (Point pt : points) {
if (pt.getId().equals(lPoint)) {
endPoints.add(pt);
break;
}
}
}
// **** ****
return endPoints;
}
/**
* Return the ids of the points at the ends of the specified line.
*/
private LinkedList<String> lineToPoints(String lineId, LinkedList<Line> lines) {
// **** look up the line ****
for (Line line : lines) {
if (line.getId().equals(lineId)) {
return line.getPoints();
}
}
// **** line not found ****
return null;
}
}
The test code follows:
package john.polygon.area;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;
import org.apache.commons.io.FilenameUtils;
public class Solution {
public static void main(String[] args) throws Exception {
String fileName = "";
Scanner sc = new Scanner(System.in);
// **** prompt for name of XML file ****
System.out.print("main <<< xml file: ");
// fileName = sc.next();
fileName = "c:\\temp\\surfaces.xml";
sc.close();
System.out.println("main <<< fileName ==>" + fileName + "<=="); // **** validate the specified file **** File file = new File(fileName); boolean exists = file.exists(); if (!exists) { throw new FileNotFoundException("EXCEPTION - fileName ==>" + fileName + "<== NOT found"); } boolean isDirectory = file.isDirectory(); if (isDirectory) { throw new Exception("EXCEPTION - fileName ==>" + fileName + "<== is a DIRECTORY"); } boolean isFile = file.isFile(); if (!isFile) { throw new Exception("EXCEPTION - fileName ==>" + fileName + "<== is NOT a file"); } String ext = FilenameUtils.getExtension(fileName); if (!ext.toLowerCase().equals("xml")) { throw new Exception("EXCEPTION - fileName ==>" + fileName + "<== does not have an XML extension");
}
// **** ****
ReadXMLFile xmlFile = new ReadXMLFile();
// **** read points from the specified XML file ****
LinkedList<Point> points = xmlFile.readXMLPoints(fileName);
// **** display list of points ****
for (Point point : points) {
System.out.println("main <<< " + point.toString());
}
System.out.println();
// **** read lines from the specified XML file ****
LinkedList<Line> lines = xmlFile.readXMLLines(fileName);
// **** display list of lines ****
for (Line line : lines) {
System.out.println("main <<< " + line.toString());
}
System.out.println();
// **** read polygons from the specified XML file ****
LinkedList<Polygon> polygons = xmlFile.readXMLPolygons(fileName);
// **** display list of polygons ****
for (Polygon polygon : polygons) {
System.out.println("main <<< " + polygon.toString());
}
System.out.println();
// **** ****
Area areaGen = new Area();
// **** compute and verify the area of each polygon ****
for (Polygon p : polygons) {
// **** generate point representation of polygon ****
LinkedList<Point> polyPoints = areaGen.linesToPoints(p, lines, points);
// **** display list of points ****
for (Point pt : polyPoints) {
System.out.println("main <<< pt: " + pt.toString());
}
// **** get the pitch of the polygon ****
System.out.println("main <<< pitch: " + p.getPitch());
// **** compute polygon area using point representation****
double computedArea = areaGen.computeArea(polyPoints, p.getPitch());
// **** compare areas (rounded to 3 decimals) ****
double area = Math.round(p.getArea() * 1000.0);
area /= 1000.0;
if (area == computedArea) {
System.out.printf("main <<< area: %8.3f == computedArea: %8.3f\n", area, computedArea);
} else {
System.out.printf("main <<< area: %8.3f != computedArea: %8.3f\n", area, computedArea);
}
System.out.println();
}
}
}
In the first polygon all is well. The areas match. When I was working on the second polygon, I noticed that some of the lines are shared by polygons and the implementation needs to use a directed line. The reason is to make sure that the points are in consecutive order. For example, if line L5 is drawn from P8 to P9 in one polygon, on an adjacent one L5 could be drawn from P9 to P8. Take a look at the last line in the second polygon. The lineToPoints() method takes care of the order of the points for the lines that make up each polygon.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. I will reply as soon as possible and will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa