fusionner des coques convexes en Java

Question

J'ai écrit un programme Java qui utilise l'algorithme de division et de conquête pour trouver la coque convexe d'un polygone dans une coordination cartésienne. J'ai une classe Coord qui a deux "double" champs X et Y et "this" sur lequel j'utilise la méthode, est une collection de coordonnées (set). ma méthode doit retourner la coque (Collection) du polygone

Mon code est comme ceci:

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

Je ne peux pas pourquoi quand je lance le programme, le message suivant apparaît:

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) 

Je serai si heureux si vous me dire où je l'ai fait une erreur

Answer 1

NOTE: Je suppose que votre code échoue à firstPart.add(sortedPointsByX.get(i)). Si vous postez un SSCCE, je pourrais fournir une meilleure assistance.

sortedPointsByX a une taille nulle.

Votre code:

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

évalue ainsi:

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

qui est:

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

qui est, à son tour, ce qui équivaut à:

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

Cependant, vous ne pouvez pas obtenir l'élément zeroeth de sortedPointsByX car il est vide.

---

Vous pouvez dire tout cela de votre erreur:

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

Un IndexOutOfBoundsException signifie que vous avez essayé d'accéder à un indice i tel que i < 0 ou i >= size(). L'erreur signale que la taille est zéro et que vous avez essayé d'accéder à l'index 0; Ainsi, 0 ≥ 0 et votre code échoue.