There is an area in the two-dimensional Euclidean plane defined by a set of points P1(x1, y1), ... Pn(xn, yn). This set of points defines a convex region that must not be entered. I am also given a pair of points A(xa, ya) and B(xb, yb) with xa < min{ x1,

Points.java

/*
  Name: Rachael Devlaeminck
  Assignment: Lab 1
  Title: Shortest Distance
  Course: CSCE 371
  Semester: Fall 2011
  Instructor: George Hauser
  Date: October 13, 2011
  Sources consulted: Course text book, slides and professor
  Program description: finds the shortest path between point A and B avoiding all points in the convex hull
  Creativity: anything extra that you added to the lab, please be very specific here
 */

import java.text.DecimalFormat;


public class Points implements Comparable{
	
	private double x;
	private double y;
	DecimalFormat formatter= new DecimalFormat("#0.00");
	
	/**
	 * @param x1 x-value of the point
	 * @param y1 y-value of the point
	 */
	public Points(double x1, double y1)
	{
		x = x1;
		y = y1;
	}
	
	/**
	 * @return x-value of the point
	 */
	public double getX()
	{
		return x;
	}
	
	/**
	 * @return y-value of the point
	 */
	public double getY()
	{
		return y;
	}
	
	/**
	 * @param x1 x-value to set point to
	 */
	public void setX(double x1)
	{
		x = x1;
	}
	
	/**
	 * @param y1 y-value to set point to
	 */
	public void setY(double y1)
	{
		y = y1;
	}
	
	/** 
	 * @return the x and y-values formatted
	 */
	public String toString()
	{
		return "(" + formatter.format(x) + ", " + formatter.format(y) + ")";
	}
	
	/** 
	 * @return which point comes first
	 */
	public int compareTo(Object o)
	{
			if (o instanceof Points)
			{
				Points other = (Points)o;
				if(getX() > other.getX())
					return 1;
				else if(getX() < other.getX())
					return -1;
				if(getY() > other.getY())
					return 1;
				else if(getY() < other.getY())
					return -1;
				else
					return 0;
			}
			else throw new RuntimeException("Error. Invalid Object Type");
	}
}

ShortestPath.java

/*
  Name: Rachael Devlaeminck
  Assignment: Lab 1
  Title: Shortest Distance
  Course: CSCE 371
  Semester: Fall 2011
  Instructor: George Hauser
  Date: October 13, 2011
  Sources consulted: Course text book, slides and professor
  Program description: finds the shortest path between point A and B avoiding all points in the convex hull
  Creativity: anything extra that you added to the lab, please be very specific here
 */

import java.io.File;
import java.io.FileNotFoundException;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Scanner;

public class ShortestPath {
	
	static ArrayList<Points> hull;
	static ArrayList<Points> path;
	static double length;

	public static void main(String[] args) {
		//instantiate decimal formatter
		DecimalFormat formatter= new DecimalFormat("#0.00");
		
		//try to read in the file
		try
		{
			//read in the file
			File file = new File("pairs.txt");
			Scanner scan = new Scanner(file);
			
			//declare variables
			Points A;
			Points B;
			int numPoints;
			double a = 0, b = 0, c=0;
			
			//find the number of problems
			int numProb = 0;
			try{
			numProb = scan.nextInt();
			}catch(InputMismatchException e)
			{
				System.out.println("Wrong input type.");
				return;
			}
			
			//loop through each problem
			for(int i = 0; i < numProb; i++)
			{
				//create points A and B
				try{
					A = new Points(scan.nextDouble(), scan.nextDouble());
					B = new Points(scan.nextDouble(), scan.nextDouble());
				}catch(InputMismatchException e)
				{
					System.out.println("Wrong input type.");
					return;
				}
				
				//find the number of points
				try{
					numPoints = scan.nextInt();
				}catch(InputMismatchException e)
				{
					System.out.println("Wrong input type.");
					return;
				}
				
				//create and array of points and assign them values
				Points points[] = new Points[numPoints];
				try{
					for(int j = 0; j < numPoints; j++)
					{
						points[j] = new Points(scan.nextDouble(), scan.nextDouble());
					}
				}catch(InputMismatchException e)
				{
					System.out.println("Wrong input type.");
					return;
				}
				
				//sort the points
				Arrays.sort(points);
				
				//create two arrays
				Points[] h = null;
				Points[] p = null;

				if(A.getX() == B.getX() && A.getY() == B.getY())
				{
					//set length to 0
					length = 0;
					
					//find the points on the hull
					quickHull(points);
					
					//create array
					h = new Points[hull.size()];
					//assign the array values
					for(int j = 0; j < hull.size(); j++)
					{
						h[j] = hull.get(j);
					}
					
					//sort the arrays
					Arrays.sort(h);
					
					//find a, b, and c to arrange hull points in clockwise order
					a = h[h.length - 1].getY() - h[0].getY();
					b = h[0].getX() - h[h.length - 1].getX();
					c = h[0].getX() * h[h.length - 1].getY() - 
							h[0].getY() * h[h.length - 1].getX();
				}
				else if(points.length > 0)
				{
					//find the points on the hull
					quickHull(points);
					
					//create two arrays
					h = new Points[hull.size()];
					p = new Points[hull.size() + 2];

					//assign the arrays values
					for(int j = 0; j < hull.size(); j++)
					{
						h[j] = hull.get(j);
						p[j] = hull.get(j);
					}
					p[hull.size()] = A;
					p[hull.size() + 1] = B;

					//sort the arrays
					Arrays.sort(h);
					Arrays.sort(p);

					//find a, b, and c to arrange hull points in clockwise order
					a = h[h.length - 1].getY() - h[0].getY();
					b = h[0].getX() - h[h.length - 1].getX();
					c = h[0].getX() * h[h.length - 1].getY() - 
							h[0].getY() * h[h.length - 1].getX();

					//find the shortest path
					newHull(p);
				}
				else
				{
					length = Math.sqrt(Math.pow(B.getX() - A.getX(), 2) + 
							Math.pow(B.getY() - A.getY(), 2));
				}
				
				//print out the problem #
				System.out.println("Problem #" + (i + 1));
				System.out.println("CH:");
				//print out the hull points in clockwise order
				if(points.length > 0)
				{
					System.out.println(h[0]);
					for(int j = 0; j < h.length - 1; j++)
					{
						if(a * h[j].getX() + b * h[j].getY() < c)
							System.out.println(h[j]);
					}
					System.out.println(h[h.length - 1]);
					for(int j = h.length - 1; j >= 0 ; j--)
					{
						if(a * h[j].getX() + b * h[j].getY() > c)
							System.out.println(h[j]);
					}
				}
				//print out the shortest path from A to B
				System.out.println("A:" + A.toString());
				for(int j = 1; j < path.size() - 1; j++)
					System.out.println(path.get(j).toString());
				System.out.println("B:" + B.toString() + " distance " + formatter.format(length));
				
				//set all values to null
				hull.clear();
				path.clear();
				length = 0;
			}
			
		}catch(FileNotFoundException e)
		{
			System.out.println("File not found.");
			return;
		}
	}
	
	/** find the convex hull
	 * @param points points being passed to the method
	 */
	public static void quickHull(Points[] points)
	{
		//create ArrayList for the points
		hull = new ArrayList<Points>();
		//add the two extreme points to the hull
		hull.add(points[0]);
		hull.add(points[points.length - 1]);
		//create ArrayLists for the right and left side of the extreme points
		ArrayList<Points> S1 = new ArrayList<Points>();
		ArrayList<Points> S2 = new ArrayList<Points>();

		//find a, b and c to find points on right and left
		double a = points[points.length - 1].getY() - points[0].getY();
		double b = points[0].getX() - points[points.length - 1].getX();
		double c = points[0].getX() * points[points.length - 1].getY() - 
				points[0].getY() * points[points.length - 1].getX();

		//add points to the right and left hand arrays
		for(int i = 0; i < points.length; i++)
		{
			if(a * points[i].getX() + b * points[i].getY() < c)
				S1.add(points[i]);
			if(a * points[i].getX() + b * points[i].getY() > c)
				S2.add(points[i]);
		}

		//call recursive method
		quickHull(S1, points[0], points[points.length - 1]);
		quickHull(S2, points[points.length - 1], points[0]);
	}
	
	/** find the convex hull
	 * @param S points being passed to the method
	 * @param C extreme point
	 * @param D extreme point
	 */
	public static void quickHull(ArrayList<Points> S, Points C, Points D)
	{
		//check to make sure there are more points to add to the hull
		if(S.size() > 0)
		{
			//declare variables
			double max = 0;
			int count = 0;
		
			//find the farthest point
			for(int i = 0; i < S.size(); i++)
			{
				double x1 = C.getX();
				double y1 = C.getY();
				double x2 = S.get(i).getX();
				double y2 = S.get(i).getY();
				double x3 = D.getX();
				double y3 = D.getY();
				double m = x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3;
				//check which area if bigger and store the index in count
				if(Math.abs(max) < Math.abs(m))
				{
					max = m;
					count = i;
				}
			}

			//add farthest point to the hull
			hull.add(S.get(count));

			//create arrays for the two lines going to the farthest point
			ArrayList<Points> S1 = new ArrayList<Points>();
			ArrayList<Points> S2 = new ArrayList<Points>();
			
			//find a, b and c for the points from C to farthest point
			double a1 = S.get(count).getY() - C.getY();
			double b1 = C.getX() - S.get(count).getX();
			double c1 = C.getX() * S.get(count).getY() - C.getY() * S.get(count).getX();

			//find a, b and c for the points from farthest point to D
			double a2 = D.getY() - S.get(count).getY();
			double b2 = S.get(count).getX() - D.getX();
			double c2 = S.get(count).getX() * D.getY() - S.get(count).getY() * D.getX();

			//add points to the left side of appropriate array
			for(int i = 1; i < S.size() - 1; i++)
			{
				if(a1 * S.get(i).getX() + b1 * S.get(i).getY() < c1)
					S1.add(S.get(i));
				if(a2 * S.get(i).getX() + b2 * S.get(i).getY() < c2)
					S2.add(S.get(i));
			}

			//call recursive method
			quickHull(S1, C, S.get(count));
			quickHull(S2, S.get(count), D);
		}
	}
	
	/** find the shortest path
	 * @param points points being passed to the method
	 */
	public static void newHull(Points[] points)
	{
		//create ArrayList for points
		path = new ArrayList<Points>();
		//create ArrayList for the right and left side of the extreme points
		ArrayList<Points> S1 = new ArrayList<Points>();
		ArrayList<Points> S2 = new ArrayList<Points>();
		//find a, b and c for points on the right and left
		double a = points[points.length - 1].getY() - points[0].getY();
		double b = points[0].getX() - points[points.length - 1].getX();
		double c = points[0].getX() * points[points.length - 1].getY() - 
				points[0].getY() * points[points.length - 1].getX();

		//add extreme point to both ArrayLists
		S1.add(points[0]);
		S2.add(points[0]);
		//add points to the right and left hand arrays
		for(int i = 0; i < points.length; i++)
		{
			if(a * points[i].getX() + b * points[i].getY() < c)
				S1.add(points[i]);
			if(a * points[i].getX() + b * points[i].getY() > c)
				S2.add(points[i]);
		}
		//add extreme point to both ArrayLists
		S1.add(points[points.length - 1]);
		S2.add(points[points.length - 1]);

		//declare length for both paths
		double length1 = 0;
		double length2 = 0;

		//find the length of the left had array
		for(int i = 1; i<S1.size();i++)
		{
			length1 += Math.sqrt(Math.pow(S1.get(i-1).getX() - S1.get(i).getX(), 2) +
					Math.pow(S1.get(i-1).getY() - S1.get(i).getY(), 2));
		}

		//find the length of the right hand array
		for(int i = 1; i<S2.size();i++)
		{
			length2 += Math.sqrt(Math.pow(S2.get(i-1).getX() - S2.get(i).getX(), 2) + 
					Math.pow(S2.get(i-1).getY() - S2.get(i).getY(), 2));
			
		}

		//declare path and length based on which is shorter
		if(length1 > length2)
		{
			path = S2;
			length = length2;
		}
		else
		{
			path = S1;
			length = length1;
		}
	}
}