在java中合併凸包

Question

我寫了一個java程序，它使用分治算法在笛卡爾座標系中查找多邊形的凸包。 我有一個類Coord，它有兩個「雙」字段X和Y，我使用該方法的「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; 
    } 

我不知道爲什麼，當我運行該程序，下面的消息顯示出來：

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) 

我會，如果你告訴我，我犯了一個錯誤

Answer 1

注意很高興：我假設你的代碼在firstPart.add(sortedPointsByX.get(i))失敗。如果您發佈SSCCE，我可以提供更好的幫助。

sortedPointsByX具有零大小。

您的代碼：

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

從而計算爲：

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

它是：

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

這，反過來，等同於：

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

但是，您無法獲得sortedPointsByX的zeroeth元素，因爲它是空的。

---

你可以從你的錯誤告訴這一切：

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

的IndexOutOfBoundsException意味着你試圖訪問某個索引i這樣i < 0或i >= size()。該錯誤報告大小爲零，並且您嘗試訪問索引0;因此，0 ≥ 0和您的代碼失敗。