merging convex hulls in java

Question

I've written a java program which which uses the divide and conquer algorithm to find the convex hull of a polygon in a cartesian coordination. I have a class Coord which has two "double" fields X and y and "this" which I'm using the method on, is a collection of coordinates (set). my method should return the hull (Collection) of the polygon

My code is 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 ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));
    }



//************************************** 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 can't get why when I run the program, the following message shows up:

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'll be so glad if you tell me where I've made a mistake

yes, you are right. my bad :) but I don't even know why I got this error — Navid Koochooloo

wchargin wchargin · Accepted Answer · 2013-05-11T18:31:53

NOTE: I'm assuming your code fails at firstPart.add(sortedPointsByX.get(i)). If you post an SSCCE, I could provide better assistance.

sortedPointsByX has zero size.

Your code:

for(int i = 0; i < sortedPointsByX.size()/2+1; i++) {
    firstPart.add(sortedPointsByX.get(i));
}

thus evaluates to:

for (int i=0; i<(0 / 2) + 1; i++) {
    firstPart.add(sortedPointsByX.get(i));
}

which is:

for (int i=0; i<1; i++) {
    firstPart.add(sortedPointsByX.get(i));
}

which is, in turn, equivalent to:

firstPart.add(sortedPointsByX.get(0));

However, you can't get the zeroeth element of sortedPointsByX because it is empty.

You can tell all this from your error:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
    at java.util.ArrayList.rangeCheck(ArrayList.java:604)

An IndexOutOfBoundsException means you tried to access some index i such that i < 0 or i >= size(). The error reports that the size is zero and that you tried to access index 0; thus, 0 &geq; 0 and your code fails.

merging convex hulls in java

1 Answers