# Untitled

By: a guest on May 25th, 2012  |  syntax: None  |  size: 9.58 KB  |  hits: 9  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. /*
2.   Name: Rachael Devlaeminck
3.   Assignment: Lab 1
4.   Title: Shortest Distance
5.   Course: CSCE 371
6.   Semester: Fall 2011
7.   Instructor: George Hauser
8.   Date: October 13, 2011
9.   Sources consulted: Course text book, slides and professor
10.   Program description: finds the shortest path between point A and B avoiding all points in the convex hull
11.   Creativity: anything extra that you added to the lab, please be very specific here
12.  */
13.
14. import java.io.File;
15. import java.io.FileNotFoundException;
16. import java.text.DecimalFormat;
17. import java.util.ArrayList;
18. import java.util.Arrays;
19. import java.util.InputMismatchException;
20. import java.util.Scanner;
21.
22. public class ShortestPath {
23.
24.         static ArrayList<Points> hull;
25.         static ArrayList<Points> path;
26.         static double length;
27.
28.         public static void main(String[] args) {
29.                 //instantiate decimal formatter
30.                 DecimalFormat formatter= new DecimalFormat("#0.00");
31.
32.                 //try to read in the file
33.                 try
34.                 {
36.                         File file = new File("pairs.txt");
37.                         Scanner scan = new Scanner(file);
38.
39.                         //declare variables
40.                         Points A;
41.                         Points B;
42.                         int numPoints;
43.                         double a = 0, b = 0, c=0;
44.
45.                         //find the number of problems
46.                         int numProb = 0;
47.                         try{
48.                         numProb = scan.nextInt();
49.                         }catch(InputMismatchException e)
50.                         {
51.                                 System.out.println("Wrong input type.");
52.                                 return;
53.                         }
54.
55.                         //loop through each problem
56.                         for(int i = 0; i < numProb; i++)
57.                         {
58.                                 //create points A and B
59.                                 try{
60.                                         A = new Points(scan.nextDouble(), scan.nextDouble());
61.                                         B = new Points(scan.nextDouble(), scan.nextDouble());
62.                                 }catch(InputMismatchException e)
63.                                 {
64.                                         System.out.println("Wrong input type.");
65.                                         return;
66.                                 }
67.
68.                                 //find the number of points
69.                                 try{
70.                                         numPoints = scan.nextInt();
71.                                 }catch(InputMismatchException e)
72.                                 {
73.                                         System.out.println("Wrong input type.");
74.                                         return;
75.                                 }
76.
77.                                 //create and array of points and assign them values
78.                                 Points points[] = new Points[numPoints];
79.                                 try{
80.                                         for(int j = 0; j < numPoints; j++)
81.                                         {
82.                                                 points[j] = new Points(scan.nextDouble(), scan.nextDouble());
83.                                         }
84.                                 }catch(InputMismatchException e)
85.                                 {
86.                                         System.out.println("Wrong input type.");
87.                                         return;
88.                                 }
89.
90.                                 //sort the points
91.                                 Arrays.sort(points);
92.
93.                                 //create two arrays
94.                                 Points[] h = null;
95.                                 Points[] p = null;
96.
97.                                 if(A.getX() == B.getX() && A.getY() == B.getY())
98.                                 {
99.                                         //set length to 0
100.                                         length = 0;
101.
102.                                         //find the points on the hull
103.                                         quickHull(points);
104.
105.                                         //create array
106.                                         h = new Points[hull.size()];
107.                                         //assign the array values
108.                                         for(int j = 0; j < hull.size(); j++)
109.                                         {
110.                                                 h[j] = hull.get(j);
111.                                         }
112.
113.                                         //sort the arrays
114.                                         Arrays.sort(h);
115.
116.                                         //find a, b, and c to arrange hull points in clockwise order
117.                                         a = h[h.length - 1].getY() - h[0].getY();
118.                                         b = h[0].getX() - h[h.length - 1].getX();
119.                                         c = h[0].getX() * h[h.length - 1].getY() -
120.                                                         h[0].getY() * h[h.length - 1].getX();
121.                                 }
122.                                 else if(points.length > 0)
123.                                 {
124.                                         //find the points on the hull
125.                                         quickHull(points);
126.
127.                                         //create two arrays
128.                                         h = new Points[hull.size()];
129.                                         p = new Points[hull.size() + 2];
130.
131.                                         //assign the arrays values
132.                                         for(int j = 0; j < hull.size(); j++)
133.                                         {
134.                                                 h[j] = hull.get(j);
135.                                                 p[j] = hull.get(j);
136.                                         }
137.                                         p[hull.size()] = A;
138.                                         p[hull.size() + 1] = B;
139.
140.                                         //sort the arrays
141.                                         Arrays.sort(h);
142.                                         Arrays.sort(p);
143.
144.                                         //find a, b, and c to arrange hull points in clockwise order
145.                                         a = h[h.length - 1].getY() - h[0].getY();
146.                                         b = h[0].getX() - h[h.length - 1].getX();
147.                                         c = h[0].getX() * h[h.length - 1].getY() -
148.                                                         h[0].getY() * h[h.length - 1].getX();
149.
150.                                         //find the shortest path
151.                                         newHull(p);
152.                                 }
153.                                 else
154.                                 {
155.                                         length = Math.sqrt(Math.pow(B.getX() - A.getX(), 2) +
156.                                                         Math.pow(B.getY() - A.getY(), 2));
157.                                 }
158.
159.                                 //print out the problem #
160.                                 System.out.println("Problem #" + (i + 1));
161.                                 System.out.println("CH:");
162.                                 //print out the hull points in clockwise order
163.                                 if(points.length > 0)
164.                                 {
165.                                         System.out.println(h[0]);
166.                                         for(int j = 0; j < h.length - 1; j++)
167.                                         {
168.                                                 if(a * h[j].getX() + b * h[j].getY() < c)
169.                                                         System.out.println(h[j]);
170.                                         }
171.                                         System.out.println(h[h.length - 1]);
172.                                         for(int j = h.length - 1; j >= 0 ; j--)
173.                                         {
174.                                                 if(a * h[j].getX() + b * h[j].getY() > c)
175.                                                         System.out.println(h[j]);
176.                                         }
177.                                 }
178.                                 //print out the shortest path from A to B
179.                                 System.out.println("A:" + A.toString());
180.                                 for(int j = 1; j < path.size() - 1; j++)
181.                                         System.out.println(path.get(j).toString());
182.                                 System.out.println("B:" + B.toString() + " distance " + formatter.format(length));
183.
184.                                 //set all values to null
185.                                 hull.clear();
186.                                 path.clear();
187.                                 length = 0;
188.                         }
189.
190.                 }catch(FileNotFoundException e)
191.                 {
193.                         return;
194.                 }
195.         }
196.
197.         /** find the convex hull
198.          * @param points points being passed to the method
199.          */
200.         public static void quickHull(Points[] points)
201.         {
202.                 //create ArrayList for the points
203.                 hull = new ArrayList<Points>();
204.                 //add the two extreme points to the hull
207.                 //create ArrayLists for the right and left side of the extreme points
208.                 ArrayList<Points> S1 = new ArrayList<Points>();
209.                 ArrayList<Points> S2 = new ArrayList<Points>();
210.
211.                 //find a, b and c to find points on right and left
212.                 double a = points[points.length - 1].getY() - points[0].getY();
213.                 double b = points[0].getX() - points[points.length - 1].getX();
214.                 double c = points[0].getX() * points[points.length - 1].getY() -
215.                                 points[0].getY() * points[points.length - 1].getX();
216.
217.                 //add points to the right and left hand arrays
218.                 for(int i = 0; i < points.length; i++)
219.                 {
220.                         if(a * points[i].getX() + b * points[i].getY() < c)
222.                         if(a * points[i].getX() + b * points[i].getY() > c)
224.                 }
225.
226.                 //call recursive method
227.                 quickHull(S1, points[0], points[points.length - 1]);
228.                 quickHull(S2, points[points.length - 1], points[0]);
229.         }
230.
231.         /** find the convex hull
232.          * @param S points being passed to the method
233.          * @param C extreme point
234.          * @param D extreme point
235.          */
236.         public static void quickHull(ArrayList<Points> S, Points C, Points D)
237.         {
238.                 //check to make sure there are more points to add to the hull
239.                 if(S.size() > 0)
240.                 {
241.                         //declare variables
242.                         double max = 0;
243.                         int count = 0;
244.
245.                         //find the farthest point
246.                         for(int i = 0; i < S.size(); i++)
247.                         {
248.                                 double x1 = C.getX();
249.                                 double y1 = C.getY();
250.                                 double x2 = S.get(i).getX();
251.                                 double y2 = S.get(i).getY();
252.                                 double x3 = D.getX();
253.                                 double y3 = D.getY();
254.                                 double m = x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3;
255.                                 //check which area if bigger and store the index in count
256.                                 if(Math.abs(max) < Math.abs(m))
257.                                 {
258.                                         max = m;
259.                                         count = i;
260.                                 }
261.                         }
262.
263.                         //add farthest point to the hull
265.
266.                         //create arrays for the two lines going to the farthest point
267.                         ArrayList<Points> S1 = new ArrayList<Points>();
268.                         ArrayList<Points> S2 = new ArrayList<Points>();
269.
270.                         //find a, b and c for the points from C to farthest point
271.                         double a1 = S.get(count).getY() - C.getY();
272.                         double b1 = C.getX() - S.get(count).getX();
273.                         double c1 = C.getX() * S.get(count).getY() - C.getY() * S.get(count).getX();
274.
275.                         //find a, b and c for the points from farthest point to D
276.                         double a2 = D.getY() - S.get(count).getY();
277.                         double b2 = S.get(count).getX() - D.getX();
278.                         double c2 = S.get(count).getX() * D.getY() - S.get(count).getY() * D.getX();
279.
280.                         //add points to the left side of appropriate array
281.                         for(int i = 1; i < S.size() - 1; i++)
282.                         {
283.                                 if(a1 * S.get(i).getX() + b1 * S.get(i).getY() < c1)
285.                                 if(a2 * S.get(i).getX() + b2 * S.get(i).getY() < c2)
287.                         }
288.
289.                         //call recursive method
290.                         quickHull(S1, C, S.get(count));
291.                         quickHull(S2, S.get(count), D);
292.                 }
293.         }
294.
295.         /** find the shortest path
296.          * @param points points being passed to the method
297.          */
298.         public static void newHull(Points[] points)
299.         {
300.                 //create ArrayList for points
301.                 path = new ArrayList<Points>();
302.                 //create ArrayList for the right and left side of the extreme points
303.                 ArrayList<Points> S1 = new ArrayList<Points>();
304.                 ArrayList<Points> S2 = new ArrayList<Points>();
305.                 //find a, b and c for points on the right and left
306.                 double a = points[points.length - 1].getY() - points[0].getY();
307.                 double b = points[0].getX() - points[points.length - 1].getX();
308.                 double c = points[0].getX() * points[points.length - 1].getY() -
309.                                 points[0].getY() * points[points.length - 1].getX();
310.
311.                 //add extreme point to both ArrayLists
314.                 //add points to the right and left hand arrays
315.                 for(int i = 0; i < points.length; i++)
316.                 {
317.                         if(a * points[i].getX() + b * points[i].getY() < c)
319.                         if(a * points[i].getX() + b * points[i].getY() > c)
321.                 }
322.                 //add extreme point to both ArrayLists
325.
326.                 //declare length for both paths
327.                 double length1 = 0;
328.                 double length2 = 0;
329.
330.                 //find the length of the left had array
331.                 for(int i = 1; i<S1.size();i++)
332.                 {
333.                         length1 += Math.sqrt(Math.pow(S1.get(i-1).getX() - S1.get(i).getX(), 2) +
334.                                         Math.pow(S1.get(i-1).getY() - S1.get(i).getY(), 2));
335.                 }
336.
337.                 //find the length of the right hand array
338.                 for(int i = 1; i<S2.size();i++)
339.                 {
340.                         length2 += Math.sqrt(Math.pow(S2.get(i-1).getX() - S2.get(i).getX(), 2) +
341.                                         Math.pow(S2.get(i-1).getY() - S2.get(i).getY(), 2));
342.
343.                 }
344.
345.                 //declare path and length based on which is shorter
346.                 if(length1 > length2)
347.                 {
348.                         path = S2;
349.                         length = length2;
350.                 }
351.                 else
352.                 {
353.                         path = S1;
354.                         length = length1;
355.                 }
356.         }
357. }