Дополнительная точка в выпуклой оболочке (с использованием сканирования graham) error + java

Question

Мой код, который использует алгоритм Graham, чтобы найти выпуклый корпус, работает очень хорошо (он показывает мне многоугольник, который он предположил для показа), но я вижу, что он отправляет мне одна дополнительная точка коллинеарны (хотя я обработка точки коллинеарных в моем коде) вот мой код:

public Collection<Coord> territoire() 
    { 
     double checkPoints; 
     Collection<Coord> sommets = new ArrayList<Coord>(this); 
     Stack<Coord> stackOfConvexHull = new Stack<Coord>(); 
     ArrayList<Coord> thisToArrList = new ArrayList<Coord>(); 
     for(Coord c : this) 
      thisToArrList.add(c); 


     //sorting the array by Y 
     ArrayList<Coord> sortedPointsByY = sortedArrayByY(thisToArrList); 

     //sorting the set of points with increasing order of angle 
     // they and the base point (basePoint) make with X axis 
     List<Coord> sortedPointsByAngle = new ArrayList<Coord>(sortPointsByAngle(sortedPointsByY)); 

     if(sortedPointsByAngle.size() < 3) 
      System.out.println("the convex hull of less than 3 points is not possible"); 
     if(collinear(sortedPointsByAngle)) 
      System.out.println("can't make a convex hull of collinear points"); 


     stackOfConvexHull.push(sortedPointsByAngle.get(0)); 
     stackOfConvexHull.push(sortedPointsByAngle.get(1)); 

      for (int i = 2; i < sortedPointsByAngle.size(); i++) 
      { 

       Coord p1 = sortedPointsByAngle.get(i); 
       Coord p2 = stackOfConvexHull.pop(); 
       Coord p3 = stackOfConvexHull.peek(); 

       checkPoints = ccw(p3, p2, p1); 

       // counter-clockwise 
       if(checkPoints > 0) 
       { 
        stackOfConvexHull.push(p2); 
        stackOfConvexHull.push(p1); 
       } 

       // collinear 
       if(checkPoints == 0) 
        stackOfConvexHull.push(p1); 

       // clockwise 
       else 
        i--; 
      } 

      // end of the hull 
      stackOfConvexHull.push(sortedPointsByAngle.get(0)); 
      sommets = new ArrayList<Coord>(stackOfConvexHull); 

     return sommets; 

    } 

//**********************************Auxiliary méthods**************************************************** 

          //***** sorting points by Y and angles ***** 

    //sorting the points by their y in ascending order 
    public ArrayList<Coord> sortedArrayByY(ArrayList<Coord> arrayOfPoints) 
    { 
     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).y < arrayOfPoints.get(j).y) 
       { 
        temp = arrayOfPoints.get(j+1); 
        arrayOfPoints.set(j+1, arrayOfPoints.get(j)); 
        arrayOfPoints.set(j, temp); 
       } 
      } 
     } 
     return arrayOfPoints; 
    } 


    public Set<Coord> sortPointsByAngle(ArrayList<Coord> points) 
    { 
     int min = minYIndex(points); 
     final Coord basePoint = points.get(min); 

     TreeSet<Coord> set = new TreeSet<Coord>(new Comparator<Coord>() 
     { 
      public int compare(Coord a, Coord b) { 

       if(a == b || a.equals(b)) 
        return 0; 

       double firstAngle = angle(basePoint, a); 
       double secondAngle = angle(basePoint, b); 

       if(firstAngle < secondAngle) 
        return -1; 

       else if(firstAngle > secondAngle) 
        return 1; 

       else 
       { 
        // collinear with the 'basePoint' point, let the point closest to it come first 
        double firstDistance = findDistance(basePoint, a); 
        double secondDistance = findDistance(basePoint, b); 

        if(firstDistance < secondDistance) 
         return -1;  

        else 
         return 1; 
       } 
      } 
     }); 

     set.addAll(points); 
     return set; 
    } 


    // find the buttom most point (minimum Y) 
    // if If the lowest y-coordinate exists in 
    // more than one point in the set, the point with the one with the lowest x-coordinate 
    // will be chosen 

    public int minYIndex(ArrayList<Coord> sortedPointsByY) 
    { 
     int min = 0; 
     for (int i = 1; i < sortedPointsByY.size(); i++) // O(n) => n number of points 
     { 
      if (sortedPointsByY.get(i).y == sortedPointsByY.get(min).y) 
      { 
       if (sortedPointsByY.get(i).x < sortedPointsByY.get(min).x) 
        min = i; 
      } 
      else if (sortedPointsByY.get(i).y < sortedPointsByY.get(min).y) 
       min = i; 
     } 
     return min; 
    } 

    public double angle(Coord basePoint, Coord a) 
    { 
     return Math.atan2(a.y - basePoint.y, a.x - basePoint.x); 
    } 


    public double findDistance(Coord basePoint, Coord a) 
    { 
     return Math.sqrt(((basePoint.x - a.x) * (basePoint.x - a.x)) + 
       ((basePoint.y - a.y) * (basePoint.y - a.y))); 
    } 


    //if the result is zero, the point is collinear 
    //if it is positive, the three points constitute left turn (counter clockwise) 
    //else the three points constitute right turn (clockwise)  
    public double ccw(Coord p1, Coord p2, Coord p3) 
    { 
     return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x); 
    } 

// check if the points are collinear 
    public boolean collinear(List<Coord> sortedPointsByAngle) 
    { 

     Coord a, b, c; 
     if(sortedPointsByAngle.size() < 2) 
      return true; 

     a = sortedPointsByAngle.get(0); 
     b = sortedPointsByAngle.get(1); 

     for(int i = 2; i < sortedPointsByAngle.size(); i++) 
     { 

      c = sortedPointsByAngle.get(i); 

      if(ccw(a, b, c) != 0) 
       return false; 
     } 

     return true; 
    } 

Я так ждал, чтобы иметь какие-то намеки, чтобы помочь мне найти мою проблему

Answer 1

это вероятно, проблема округления. Вы вычислить это выражение (функция ccw)

(p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) 

с двойной точностью. Шансы, что это будет точно0 небольшие.

Что я обычно делаю, чтобы решить эту проблему (хотя это не очень чистая практика), чтобы просто проверить «почти 0»:

if (Math.abs(checkPoints) < 0.0000001) // colinear