I wrote a java program that uses the division and conquest algorithm to find the convex hull of a polygon in Cartesian coordination. I have a Coord class, which has two "double" fields X and y and "this", which I use with the on method, is a set of coordinates (set). my method should return the polygon body
My code looks like this:
public Collection<Coord> territoire() { Collection<Coord> sommets = new ArrayList<Coord>(); ArrayList<Coord> thisToArrList = new ArrayList<Coord>(); for(Coord c : this) thisToArrList.add(c); ArrayList<Coord> sortedPointsByX = new ArrayList<Coord>(); int n = this.size(); if (n <= 2) return this; //sorting the points by their X coordinates sortedPointsByX = sortedArrayByX(thisToArrList); //>>>>>>>>>>>>>>>>>> works good till here <<<<<<<<<<<<<<<<<<<<<<<< // now sortedPointsByX array contains the points with increasing X // splitting the sortedPointsByX into two arrays ArrayList<Coord> firstPart = new ArrayList<Coord>(); ArrayList<Coord> secondPart = new ArrayList<Coord>(); // if the number of the points is prime, the leftmost and the rightmost half // both have same number of points if(sortedPointsByX.size() % 2 == 0) { for(int i = 0; i < sortedPointsByX.size()/2; i++) { firstPart.add(sortedPointsByX.get(i)); } for(int i = sortedPointsByX.size()/2; i < sortedPointsByX.size(); i++) { secondPart.add(sortedPointsByX.get(i)); } } //>>>>>>>>>>>>>>>>>>>>>works good till here<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< // if the number of points is odd, the leftmost half have the extra points else { for(int i = 0; i < sortedPointsByX.size()/2+1; i++) { firstPart.add(sortedPointsByX.get(i)); } for(int i = sortedPointsByX.size()/2+1; i < sortedPointsByX.size(); i++) { secondPart.add(sortedPointsByX.get(i)); } } //>>>>>>>>>>>>>>>>>>>>>>>works good till here<<<<<<<<<<<<<<<<<<<<<<<<< CoordSet firstSet = new CoordSet(firstPart); CoordSet secondSet = new CoordSet(secondPart); // converting the arrays to list of coordinates in order to use recursion over them //recursion for sub coordsets Collection<Coord> firstSetSommet = firstSet.territoire(); Collection<Coord> secondSetSommet = secondSet.territoire(); ArrayList<Coord> firstHull = new ArrayList<Coord>(firstSetSommet); ArrayList<Coord> secondHull = new ArrayList<Coord>(secondSetSommet); sommets = mergeHulls(firstHull, secondHull); return sommets; } public Collection<Coord> mergeHulls(ArrayList<Coord> firstHull, ArrayList<Coord> secondHull) { Collection<Coord> pointsInside = new ArrayList<Coord>(); Collection<Coord> sommets = new ArrayList<Coord>(); //********************upper tangent*************** //find the highest point of the leftmost part Coord firstPartHighestPoint = getMaxY(firstHull); //find the highest point of the rightmost part Coord secondPartHighestPoint = getMaxY(secondHull); for(int i = 0; i< firstHull.size(); i++) { // check if the points lie on the line between highest point in leftmost and in rightmost // if true, the current point is above the line if(isCollinear(firstPartHighestPoint, secondPartHighestPoint, firstHull.get(i))>0) { // the current point is above the line firstPartHighestPoint = firstHull.get(i); } pointsInside.add(firstPartHighestPoint); } for(int i = 0; i < secondHull.size(); i++) { if(isCollinear(firstPartHighestPoint, secondPartHighestPoint, secondHull.get(i))>0) { // the current point is above the line secondPartHighestPoint = secondHull.get(i); } pointsInside.add(secondPartHighestPoint); } //******************lower tangent*************** //find the lowest point of the leftmost part Coord firstPartLowestPoint = getMinY(firstHull); // find the lowest point of the rightmost part Coord secondPartLowestPoint = getMinY(secondHull); for(int i = 0; i< firstHull.size(); i++) { // check if the points lie on the line between highest point in leftmost and in rightmost // if true, the current point is above the line if(isCollinear(firstPartLowestPoint, secondPartLowestPoint, firstHull.get(i)) < 0) { // the current point is above the line firstPartLowestPoint = firstHull.get(i); } pointsInside.add(firstPartLowestPoint); } for(int i = 0; i < secondHull.size(); i++) { if(isCollinear(firstPartLowestPoint, secondPartLowestPoint, secondHull.get(i)) < 0) { // the current point is above the line secondPartLowestPoint = secondHull.get(i); } pointsInside.add(firstPartLowestPoint); } sommets.addAll(firstHull); sommets.addAll(secondHull); sommets.removeAll(pointsInside); return sommets; } //**********************************Auxiliary méthods**************************************************** // if the equation is equal to 0, the points are collinear // the method returns the determinant of the point matrix // This determinant tells how far point 'c' is from vector ab and on which side // it is // < 0 if the point 'c' is below the line (assumption : horizontal line) // > 0 if the point 'c' is above the line public double isCollinear(Coord a, Coord b, Coord c) { return ((bx - ax)*(cy - ay) - (by - ay)*(cx - ax)); } //************************************** line equation ************************************************ // find the slope of the line between two points public static double findSlope(Coord point1, Coord point2) { return (point2.y - point1.y)/(point2.x-point1.x); } // finding the constant 'b' of the line equation y = xm + b public static double constantB(Double slope, Coord point) { return point.y - slope* point.x; } //*************************************** Minimum and Maximum "Y" ***************************************** // the point with maximum Y public static Coord getMaxY(ArrayList<Coord> points) { double maxY = points.get(0).y; // start with the first value Coord maxPoint = points.get(0); for (int i=1; i<points.size(); i++) { if (points.get(i).y > maxY) { maxY = points.get(i).y; // new maximum maxPoint = points.get(i); } } return maxPoint; } // a method to find the Point with the minimum y public static Coord getMinY(ArrayList<Coord> points) { double minValue = points.get(0).y; Coord minPoint = points.get(0); for(int i=1;i<points.size();i++){ if(points.get(i).y < minValue) { minPoint = points.get(i); minValue = points.get(i).y; } } return minPoint; } //************************************** sorting the points ******************************************** //sorting the points by their x in ascending order public static ArrayList<Coord> sortedArrayByX(ArrayList<Coord> arrayOfPoints) { //double minval = arrayOfPoints[0].x; Coord temp = null; for(int i = 0; i< arrayOfPoints.size(); i++) { for(int j = 0; j< arrayOfPoints.size()-1; j++) { if(arrayOfPoints.get(j+1).x < arrayOfPoints.get(j).x) { temp = arrayOfPoints.get(j+1); arrayOfPoints.set(j+1, arrayOfPoints.get(j)); arrayOfPoints.set(j, temp); } } } return arrayOfPoints; }
I cannot understand why, when I run the program, the following message appears:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0 at java.util.ArrayList.rangeCheck(ArrayList.java:604) at java.util.ArrayList.get(ArrayList.java:382) at miniprojet2.CoordSet.getMaxY(CoordSet.java:270) at miniprojet2.CoordSet.mergeHulls(CoordSet.java:154) at miniprojet2.CoordSet.territoire(CoordSet.java:139) at miniprojet2.CalculeTerritoire.main(CalculeTerritoire.java:36)
I will be glad if you tell me where I was wrong.
source share