quickHull

package penguhull;

import java.util.Arrays;

public class PenguHull {

    /**
     *  Main algorithm
     * @param points
     * @return convexHull
     */
    public static int[][] quickHull(int[][] points) {
        
        // main Convex Hull Set
        int[][] convexHull;
        
        // finding the leftmost and rightmost point in the set
        final int[] leftMostPoint = findLeftmostPoint(points);
        final int[] rightMostPoint = findRightmostPoint(points);
        
        /**
         * divides points based on their position,
         * from the line segment between leftMostPoint and rightMostPoint,
         * also removes points which are on the line segment
         */
        int[][] pointsAboveSeg = createSegment(points, leftMostPoint, rightMostPoint, true);
        int[][] pointsBelowSeg = createSegment(points, leftMostPoint, rightMostPoint, false);
       
        // find the hull above the line segment of leftMost and rightMost Point
        int[][] firstHull = quickHullLeftOf(pointsAboveSeg, leftMostPoint, rightMostPoint);
        
        // find the hull below the line segment of leftMost and rightMost Point
        int[][] secondHull = quickHullLeftOf(pointsBelowSeg, rightMostPoint, leftMostPoint);
        
        // if no points exists above or below the line segment
        if (firstHull == null && secondHull == null)
            return new int[][]{leftMostPoint, rightMostPoint, leftMostPoint};
        
        // combine first and second hull
        convexHull = combineHulls(secondHull, firstHull);
        
        /**
         * returns the convex hull, in the form of
         * {p, r1, r2, r3..., p} in a closed loop
         */
        return combineHulls(new int[][]{leftMostPoint}, convexHull);
    }
    
    // finds the convex hull which covers all the points above/below the line segment
    public static int[][] quickHullLeftOf(int[][] points, int[] p, int[] q) {
        
        if (points.length < 1)
            return null;
        
        int[][] segA;
        int[][] segB = null;
        int[][] segC = null;
        
        // finds the farthest point from the line segment
        int[] farthestPoint = findPointFarthestLeftFrom(points, p, q);
        
        /**
         * checking points on the right side of the line segment,
         * joining farthestPoint and q
         */
        if (existsPointLeftOf(points, farthestPoint, q))
            segB = quickHullLeftOf(points, farthestPoint, q);
        
        /**
         * checking points on the left side of the line segment,
         * joining farthestPoint and p
         */
        if (existsPointLeftOf(points, p, farthestPoint))
            segC = quickHullLeftOf(points, p, farthestPoint);
        
        // self explanatory
        if (segB != null && segC != null) {
            segA = combineHulls(segB, segC);
        } else if (segB == null && segC != null) {
            segA = combineHulls(new int[][]{q}, segC);
        } else if (segB != null && segC == null) {
            segA = combineHulls(segB, new int[][]{p});
        } else {
            segA = new int[][]{q, farthestPoint, p};
        }
        
        return segA;
    }

    /**
     * combines two Hulls
     */
    public static int[][] combineHulls(int[][] firstHull, int[][] secondHull) {
        
        if (firstHull != null && secondHull == null)
            return firstHull;
        else if (firstHull == null && secondHull != null)
            return secondHull;
        
        if (firstHull != null && secondHull != null) {
            int[][] convexHull;
            int pointer = 0;
            if (firstHull[firstHull.length-1][0] == secondHull[0][0] && firstHull[firstHull.length-1][1] == secondHull[0][1]) {
                // closed Hull
                convexHull = new int[firstHull.length + secondHull.length - 1][];

                for (int i = 0; i < (firstHull.length - 1); i++) {
                    convexHull[pointer] = firstHull[i];
                    pointer++;
                }
            } else {
                // open Hull
                convexHull = new int[firstHull.length + secondHull.length][];

                for (int[] i : firstHull) {
                    convexHull[pointer] = i;
                    pointer++;
                }
            }

            for (int[] i : secondHull) {
                convexHull[pointer] = i;
                pointer++;
            }
            
            return convexHull;
        }
        
        return null;
    }
    
    /**
     * functions
     */
    public static int[] findPointFarthestLeftFrom(int[][] points, int[] firstLinePoint, int[] secondLinePoint) {
        double maxDistance = 0.0;
        int[] leftmostPoint = null;
        for (int[] point : points) {
            double distance = Math.abs(signedDistance(point, firstLinePoint, secondLinePoint));
            if (isPointLeftOf(point, firstLinePoint, secondLinePoint) && distance > maxDistance) {
                maxDistance = distance;
                leftmostPoint = point;
            }
        }
        return leftmostPoint;
    }
    
    // finds the leftmost point in the plane from the given set
    public static int[] findLeftmostPoint(int[][] points) {
        int[] currLeftmost = points[0];
        for (int i=1; i < points.length; i++) {
            if (points[i][0] < currLeftmost[0])
                currLeftmost = points[i];
        }
        return currLeftmost;
    }
    
    // finds the rightmost point in the plane from the given set
    public static int[] findRightmostPoint(int[][] points) {
        int[] currRightmost = points[0];
        for (int i=1; i < points.length; i++) {
            if (points[i][0] > currRightmost[0])
                currRightmost = points[i];
        }
        return currRightmost;
    }

    // checks if the point is in the left of the line segment
    public static boolean isPointLeftOf(int[] point, int[] firstLinePoint, int[] secondLinePoint) {
        double n = signedDistance(point, firstLinePoint, secondLinePoint);
        return n < 0;
    }

    // checks if their exists any points on the left of the line segment
    public static boolean existsPointLeftOf(int[][] points, int[] firstLinePoint, int[] secondLinePoint) {
        for (int[] point : points) {
            if (isPointLeftOf(point, firstLinePoint, secondLinePoint)) {
                return true;
            }
        }
        return false;
    }

    public static double signedDistance(int[] point, int[] firstLinePoint, int[] secondLinePoint) {
        int det = (secondLinePoint[0] - firstLinePoint[0]) * (firstLinePoint[1] - point[1])
            - (firstLinePoint[0] - point[0]) * (secondLinePoint[1] - firstLinePoint[1]);
        double len = Math.sqrt(
            Math.pow(secondLinePoint[0] - firstLinePoint[0], 2) + Math.pow(secondLinePoint[1] - firstLinePoint[1], 2)
        );

        return det / len;
    }

    public static String pointsToPlotString(int[][] points) {
        
        String pointPlotX = "";
        String pointPlotY = "";
        
        for (int[] i : points) {
            pointPlotX += i[0] + ",";
            pointPlotY += i[1] + ",";
        }
        
        String result = "\"x\":[" + pointPlotX.substring(0, pointPlotX.length()-1) + "],\n" + "\"y\":[" + pointPlotY.substring(0, pointPlotY.length()-1) + "]";
        
        return result;
    }
    
    // divides points based upon their position(left/right) from the line segment
    public static int[][] createSegment(int[][] points, int[] x, int[] y, boolean up) {
        
        int[][] newPoints = new int[points.length][];
        int pointerA = 0;
        
        for (int[] i : points) {
            if (up) {
                if (isPointLeftOf(i, x, y)) {
                    newPoints[pointerA] = i;
                    pointerA++;
                }
            } else {
                if (isPointLeftOf(i, y, x)) {
                    newPoints[pointerA] = i;
                    pointerA++;
                }
            }
        }
        
        int[][] returnPoints = new int[pointerA][];
        
        System.arraycopy(newPoints, 0, returnPoints, 0, pointerA);
        
        return returnPoints;
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // main set containing all points
        int[][] input = {
                {0,0}, {10,10},
                {1,5}, {3,7},
                {7,3}, {9,5},
                {1,1}, {5,5}, {0,0}, {2,4}, {7,8}, {9,9}, {2,5}
        };
        int[][] expectedOutput = {
                {0,0},
                {7,3}, {9,5},
                {10,10},
                {3,7}, {1,5},
                {0,0}
        };
        
        int[][] output = quickHull(input);
        
        System.out.println("Original input: ");
        System.out.println(pointsToPlotString(input));
        System.out.println("\nConvex Hull: ");
        System.out.println(pointsToPlotString(output));
        System.out.println("\nTest Passed: " + checkIfEqual(output));
    }
    
    public static boolean checkIfEqual(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[0][0] != b[0][0] || a[1][1] != b[1][1]) {
                System.out.println("False");
                return false;
            }    
        }
        System.out.println("True");
        return true;
    }
    
}