src/main/java/de/javagl/geom/ConvexHull.java
/**
     * Perform the actual Graham Scan on the given points
     * 
     * @param points The input points
     * @return The points of the convex hull
     */
Perform the actual Graham Scan on the given points

@param points The input points
@return The points of the convex hull
Perform the actual Graham Scan on the given points @param points The input points @return The points of the convex hull
private static List<Point2D> scan(List<Point2D> points)
    {
        List<Point2D> result = new ArrayList<Point2D>();
        result.add(points.get(0));
        result.add(points.get(1));
        for (int i=2; i<points.size(); i++)
        {
            Point2D p0 = result.get(result.size()-1);
            Point2D p1 = result.get(result.size()-2);
            Point2D p = points.get(i);
            double x0 = p0.getX();
            double y0 = p0.getY();
            double x1 = p1.getX();
            double y1 = p1.getY();
            double x = p.getX();
            double y = p.getY();
            int r = Line2D.relativeCCW(x0, y0, x1, y1, x, y);
            if (r >= 0)
            {
                result.add(p);
            }
            else
            {
                result.remove(result.size()-1);
                i--;
            }
        }
        return result;
    }
private static List < Point2D > scan ( List < Point2D > points ) { List < Point2D > result = new ArrayList < Point2D > ( ) ; result . add ( points . get ( 0 ) ) ; result . add ( points . get ( 1 ) ) ; for ( int i = 2 ; i < points . size ( ) ; i ++ ) { Point2D p0 = result . get ( result . size ( ) - 1 ) ; Point2D p1 = result . get ( result . size ( ) - 2 ) ; Point2D p = points . get ( i ) ; double x0 = p0 . getX ( ) ; double y0 = p0 . getY ( ) ; double x1 = p1 . getX ( ) ; double y1 = p1 . getY ( ) ; double x = p . getX ( ) ; double y = p . getY ( ) ; int r = Line2D . relativeCCW ( x0 , y0 , x1 , y1 , x , y ) ; if ( r >= 0 ) { result . add ( p ) ; } else { result . remove ( result . size ( ) - 1 ) ; i -- ; } } return result ; }
Perform the actual Graham Scan on the given points
Perform the actual Graham Scan on the given points
//System.out.println("relative "+r+" for "+p0+" "+p1+" "+p);
 // A check for r>0 should be sufficient, but
 // may cause problems for equal points. So
 // doing the conservative r>=0 check here.
