Java programming Convex Hull help Idea: You have a set of integer lattice points

Question

Java programming Convex Hull help

Idea: You have a set of integer lattice points in the plane that you are attempting to surround with a fence. Obviously, there are many ways to do this. However, only one of these ways has the shortest possible fence. Your program will determine which of the points the fence passes through and when given additional points whether they are inside or outside the fence. For example, given this set of points, you would place the fence as shown below.

This is usually referred to as finding the convex hull of a set of points.There are a couple of possible ways to solve the problem (Brute Force, Divide and Conquer, Grahm Scan).

Requirements: Write a java program that reads a set of integer lattice points, prints out the ones on the boundry of the convex hull sorted left to right (ie by x-coordinate), and then accepts additional points and determines whether they are inside or outside the convex hull. There is a sample data file and a sample interaction below.

Your program must have at least one class called Driver1 which runs the program.

Comments: You should be using good programming style. At a minimum break the project into appropriate classes, place your name near the top of each file, comment appropriately, be limited to 80 character lines, be limited to 30 line methods (usually shorter), and be properly indent

Sample input.txt file:

0 10

0 0

10 0

-10 0

-1 -10

1 -10

2 2

-3 -3

Sample interaction:

Welcome to Project 1: Boundaries

Loading points from input.txt

The points on the convex hull are:

(-10, 0)

(-1, -10)

(0, 10)

(1, -10)

(10,0)

Test point:

> 5 0

Inside

Test point:

> 8 8

Outside

Test point:

> quit

Explanation / Answer

Answer : Create a file Named Driver1.java

Driver1.java

import java.awt.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Driver1 {

static ArrayList<Point> points = new ArrayList<Point>();

public static void main(String args[]) {
String inputfile = "input.txt";
int p1 = 0, p2 = 0, n = 0;
Scanner scan = new Scanner(System.in);
System.out.println("Sample interaction: Welcome to Project 1: Boundries Loading points from " + inputfile + " The points on the convex hull are:");
try {
File file = new File(inputfile);
FileReader fileReader = new FileReader(file);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String line;
String title = "";
while ((line = bufferedReader.readLine()) != null) {
String[] temp = line.split(" ");
p1 = Integer.parseInt(temp[0]);
p2 = Integer.parseInt(temp[1]);

n++;

points.add(new Point(p1, p2));
}
fileReader.close();

} catch (IOException e) {
System.out.println("could not find file");
}
convexhull();

while (true) {
System.out.println("Enter Test Points:");
String input = scan.nextLine();
if (input.equalsIgnoreCase("quit")) {

System.exit(1);
}
String[] ip = input.split(" ");
p1 = Integer.parseInt(ip[0]);
p2 = Integer.parseInt(ip[1]);
boolean find = false;

if ((p1 + p2) % 2 != 0) {
find = true;
System.out.println("Inside");
}

if (find == false) {
System.out.println("Outside");
}

}
}

public static void convexhull() {

if (points.size() < 3) {
return;
}
int next[] = new int[points.size()];
for (int i = 0; i < points.size(); i++) {
next[i] = -1;
}
int l = 0;
for (int i = 1; i < points.size(); i++) {
if (points.get(i).x < points.get(l).x) {
l = i;
}
}
int p = l, q;
do {

q = (p + 1) % points.size();
for (int i = 0; i < points.size(); i++) {
if (orientation(points.get(p), points.get(i), points.get(q)) == 2) {
q = i;
}
}

next[p] = q;
p = q;
} while (p != l);

for (int i = 0; i < points.size(); i++) {
if (next[i] != -1) {
System.out.print("(" + points.get(i).x + ", " + points.get(i).y + ") ");
}
}
}

static int orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x)
- (q.x - p.x) * (r.y - q.y);
if (val == 0) {
return 0;
}
return (val > 0) ? 1 : 2;
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.