Untitled

/*
  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;
                }
        }
}