Spring 2017, Siena College

BruteForceConvexHull BlueJ Project

BruteForceConvexHull Source Code

The Java source code for BruteForceConvexHull is below. Click on a file name to download it.

### BruteForceConvexHull.java

```/*
Brute force convex hull implementation

Jim Teresco
Spring 2011, CSIS 385, Siena College
Updated for Spring 2017

Updated to output a CHM project .gra file for plotting

\$Id: BruteForceConvexHull.java 2062 2013-02-14 02:19:07Z terescoj \$

*/

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

class Point {

// instance variables for label and coordinates
private String label;
private double x;
private double y;

public Point(String label, double x, double y) {
this.label = label;
this.x = x;
this.y = y;
}

public double getX() {
return x;
}

public double getY() {
return y;
}

public String getLabel() {
return label;
}

public String toString() {
return label + " (" + x + "," + y + ")";
}

public String toStringTMG() {
return label + " " + x + " " + y;
}

public boolean equals(Object o) {
Point other = (Point)o;
return (x == other.x) &&
(y == other.y) &&
label.equals(other.label);
}

public double squaredDistance(Point other) {

double dx, dy;
dx = x-other.x;
dy = y-other.y;
return dx*dx + dy*dy;
}

/**
Check if this point is directly in between the two given
points.  Note: the assumption is that they are colinear.

@param o1 one of the points
@param o2 the other point
@return whether this point is between the two given points
*/
public boolean isBetween(Point o1, Point o2) {

double sqDisto1o2 = o1.squaredDistance(o2);
return (squaredDistance(o1) < sqDisto1o2) &&
(squaredDistance(o2) < sqDisto1o2);
}
}

class LineSegment {

// store the endpoints
private Point start;
private Point end;

public LineSegment(Point a, Point b) {

start = a;
end = b;
}

public Point getStart() {

return start;
}

public Point getEnd() {

return end;
}

public String toString() {
return "Segment from " + start + " to " + end;
}
}

public class BruteForceConvexHull {

/**
Read in a list of points:
label x y
from the file in args (first line contains number of points)

The compute convex hull using brute force, print out in
readable text (argv.equals("text") or nothing) or as data
plottable in the TMG data Google Maps viewer (argv.equals("tmg").
*/

public static void main(String args[]) {

int numPoints = 0;
boolean debug = false;

if (args.length == 0) {
System.err.println("Usage: java BruteForceConvexHull filename [type]");
System.exit(1);
}

// create a list of points
ArrayList<Point> points = new ArrayList<Point>();

try {
Scanner s = new Scanner(new File(args));
// skip header line (would be good to do error checking)
s.nextLine();
// second line is number of waypoints and connections
numPoints = s.nextInt();
// skip the rest of the line
s.nextLine();
for (int i = 0; i<numPoints; i++) {
}

}
catch (FileNotFoundException e) {
System.err.println(e);
System.exit(1);
}

// we will build the line segments that form the hull in this list
ArrayList<LineSegment> hull = new ArrayList<LineSegment>();

// consider each pair of points
for (int i = 0; i<numPoints-1; i++) {

Point point1 = points.get(i);
for (int j = i+1; j<numPoints; j++) {

Point point2 = points.get(j);
// from here, we need to see if all other points are
// on the same side of the line connecting point1 and point2
double a = point2.getY() - point1.getY();
double b = point1.getX() - point2.getX();
double c = point1.getX() * point2.getY() - point1.getY() * point2.getX();
// now check all other points to see if they're on the
// same side -- stop as soon as we find they're not
boolean lookingForPositive = false;
boolean foundProblem = false;
boolean firstTestPoint = true;

for (int k = 0; k<numPoints; k++) {

Point point3 = points.get(k);

if (point1.equals(point3) || point2.equals(point3))
continue;
double checkVal = a * point3.getX() + b * point3.getY() - c;
if (debug)
System.out.println("Checking " + point3 +
" for segment from " + point1 +
" to " + point2);
if (checkVal == 0) {
// if in between, continue, otherwise skip this pair
// since we'll catch it elsewhere
if (point3.isBetween(point1, point2)) {
continue;
}
else {
if (debug)
System.out.println("Found colinear point " +
point3 + " directly between " +
point1 + " and " + point2);
foundProblem = true;
break;
}
}
if (firstTestPoint) {
lookingForPositive = (checkVal > 0);
firstTestPoint = false;
}
else {
if ((lookingForPositive && (checkVal < 0) ||
(!lookingForPositive && (checkVal > 0)))) {
// segment not on hull, jump out of innermost loop
if (debug)
System.out.println("Found points on opposite sides of line between " +
point1 + " and " + point2);
foundProblem = true;
break;
}
}
}
// we didn't find a reason that this segment was not on the
// hull, so we add it
}
}

// we now have a list of line segments that form the hull
if (debug) {
System.out.println("Convex hull is formed from line segments:");
for (LineSegment l : hull)
System.out.println(l);
}

// we pull out the points and list them in order, repeating the last
// so we can easily draw the hull
ArrayList<Point> hullPoints = new ArrayList<Point>();
LineSegment firstSegment = hull.get(0);
Point firstHullPoint = firstSegment.getStart();
Point nextSegmentPoint = firstSegment.getEnd();
hull.remove(firstSegment);
while (!hull.isEmpty()) {
for (LineSegment l : hull) {
if (l.getStart().equals(nextSegmentPoint)) {
nextSegmentPoint = l.getEnd();
hull.remove(l);
break;
}
if (l.getEnd().equals(nextSegmentPoint)) {
nextSegmentPoint = l.getStart();
hull.remove(l);
break;
}
}
}

// print the results
if ((args.length == 1) || !args.equals("tmg")) {
System.out.println("Convex hull polygon:");
// all points along the way
for (Point p : hullPoints) {
System.out.println(p);
}
}
else {
System.out.println("TMG 1.0 simple");
System.out.println(hullPoints.size() + " " + hullPoints.size());
// all points along the way
for (Point p : hullPoints) {
System.out.println(p.toStringTMG());
}
if ((args.length > 1) && args.equals("tmg")) {
// add in "graph edges", really just connections between
for (int i = 0; i < hullPoints.size(); i++) {
System.out.print(i + " ");
if (i < hullPoints.size()-1) {
System.out.print(i+1);
}
else {
System.out.print(0);
}
System.out.println(" HullSeg" + i);
}
}
}
}
}
```