## Friday, 20 January 2017

### Chapter 22 Exercise 9, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

22.9 (Geometry: gift-wrapping algorithm for finding a convex hull) Section 22.10.1 introduced the gift-wrapping algorithm for finding a convex hull for a set of points. Assume that the Java’s coordinate system is used for the points. Imple-
ment the algorithm using the following method:

/** Return the points that form a convex hull */
public static ArrayList<Point2D> getConvexHull(double[][] s)

Point2D is defined in Section 9.6.
Write a test program that prompts the user to enter the set size and the points
and displays the points that form a convex hull.

import java.util.ArrayList;

public class Exercise09 {

public static void main(String[] args) {
double[][] points = new double[6][2];
for (int i = 0; i < points.length; i++) {
points[i][0] = (int)(Math.random() * 100);
points[i][1] = (int)(Math.random() * 100);
}
/*
points[0][0] = 1;
points[0][1] = 2.4;
points[1][0] = 2.5;
points[1][1] = 2;
points[2][0] = 1.5;
points[2][1] = 34.5;
points[3][0] = 5.5;
points[3][1] = 6;
points[4][0] = 6;
points[4][1] = 2.4;
points[5][0] = 5.5;
points[5][1] = 9;
*/
ArrayList<MyPoint> hull = getConvexHull(points);
System.out.println("There are " + points.length + " points:");
for (int i = 0; i < points.length; i++) {
System.out.print("(" + points[i][0] + ", " + points[i][1] + ")  ");
}
System.out.println("\nThe convex hull is:");
for (MyPoint myPoint : hull) {
System.out.print("(" + myPoint.x + ", " + myPoint.y + ")  ");
}
}

public static ArrayList<MyPoint> getConvexHull(double[][] s) {
ArrayList<MyPoint> oldPoints = new ArrayList<>();
for (int i = 0; i < s.length; i++) {
}

ArrayList<MyPoint> points = new ArrayList<>();

//first point
MyPoint h0 = oldPoints.get(0);
for (int i = 1; i < oldPoints.size(); i++) {
if(oldPoints.get(i).y > h0.y) {
h0 = oldPoints.get(i);
} else if(oldPoints.get(i).y == h0.y) {
if(oldPoints.get(i).x > h0.x) {
h0 = oldPoints.get(i);
}
}
}

//second point
MyPoint virtualPoint = new MyPoint(h0.x + 1, h0.y);
MyPoint h1 = oldPoints.get(0);
double tmpAngle = getAngle(h0, virtualPoint, h1);
if(Double.isNaN(tmpAngle)) {
tmpAngle = Double.MAX_VALUE;
}
for (int j = 1; j < oldPoints.size(); j++) {
double newAngle = getAngle(h0, virtualPoint, oldPoints.get(j));
if(Double.isNaN(newAngle)) {
newAngle = Double.MAX_VALUE;
}
if(newAngle < tmpAngle) {
tmpAngle = newAngle;
h1 = oldPoints.get(j);
}
}

//other points
while(h1 != points.get(0)) {
MyPoint tmpPoint = oldPoints.get(0);
double tmpAngle2 = getAngle(h1, tmpPoint, h0);
if(Double.isNaN(tmpAngle2)) {
tmpAngle2 = 0;
}
for (int j = 1; j < oldPoints.size(); j++) {
double newAngle = getAngle(h1, oldPoints.get(j), h0);
if(Double.isNaN(newAngle)) {
continue;
}
if(newAngle > tmpAngle2) {
tmpAngle2 = newAngle;
tmpPoint = oldPoints.get(j);
} else if(newAngle == tmpAngle2) {
if(getSide(h1, oldPoints.get(j)) > getSide(h1, tmpPoint)) {
tmpAngle2 = newAngle;
tmpPoint = oldPoints.get(j);
}
}
}
if(tmpPoint != points.get(0)) {
}
h0 = h1;
h1 = tmpPoint;
}
return points;
}

public static double getAngle(MyPoint p1, MyPoint p2, MyPoint p3) {
double a = getSide(p2, p3);
double b = getSide(p1, p3);
double c = getSide(p1, p2);
return Math.toDegrees(Math.acos((a * a - b * b - c * c) / (-2 * b * c)));
}

public static double getSide(MyPoint p1, MyPoint p2) {
return Math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
}

static class MyPoint {
double x, y;
MyPoint(double x, double y) {
this.x = x; this.y = y;
}
}
}