Java Modified QuickHull


  • 0

    I was intrigued that the QuickHull Algorithm wasn't listed amongst the solutions so I wanted to give it a try to see if I could make it work. I found a decent Java QuickHull implementation here and then set about modifying it to work in colinear cases.

    • Use a set instead of a list to store the hull to prevent duplicates (e.g. points in the middle of a straight line)
    • When initially partitioning the set, add colinear points to both sets
    • When finding the farthest point in FindHull, if it's colinear (i.e. distance 0) then add all such points to hull and skip partitioning
    • When re-partitioning the set in FindHull, add colinear points to the subset

    Just like the quicksort algorithm, it has the expected time complexity of O(n log n), but may degenerate to Θ(nh) = O(n2) in the worst case.

    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
           
        public List<Point> outerTrees(Point[] points) {
            Set<Point> convexHull = new HashSet<Point>();
            List<Point> pointsList = new ArrayList<Point>(Arrays.asList(points));
            if (pointsList.size() < 3)
                return pointsList;
     
            // Find left and right most points, say A & B, and add A & B to convex hull
            Point minPoint = null;
            Point maxPoint = null;
            int minX = Integer.MAX_VALUE;
            int maxX = Integer.MIN_VALUE;
            for (Point p : pointsList)
            {
                if (p.x < minX) {
                    minX = p.x;
                    minPoint = p;
                }
                if (p.x > maxX) {
                    maxX = p.x;
                    maxPoint = p;
                }
            }
            convexHull.add(minPoint);
            convexHull.add(maxPoint);
            pointsList.remove(minPoint);
            pointsList.remove(maxPoint);
     
            // Segment AB divides the remaining (n-2) points into 2 groups S1 and S2 
            //   where S1 are points in S that are on the right side of the oriented line from A to B, 
            //   and S2 are points in S that are on the right side of the oriented line from B to A 
            List<Point> leftSet = new ArrayList<Point>();
            List<Point> rightSet = new ArrayList<Point>();
     
            for (Point p : pointsList)
            {
                if (pointLocation(minPoint, maxPoint, p) == -1) {
                    leftSet.add(p);
                } else if (pointLocation(minPoint, maxPoint, p) == 1) {
                    rightSet.add(p);
                } else {
                    // Normally we'd ignore co-linear points but in this case we're adding them to the both sets
                    leftSet.add(p);
                    rightSet.add(p);
                }
            }
            findHull(minPoint, maxPoint, rightSet, convexHull);
            findHull(maxPoint, minPoint, leftSet, convexHull);
     
            return new ArrayList(convexHull);
        }
        
        public int pointLocation(Point A, Point B, Point P)
        {
            int cp1 = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);
            if (cp1 > 0) {
                return 1;
            } else if (cp1 == 0) {
                return 0;
            } else {
                return -1;
            }
        }
        
        public int distance(Point A, Point B, Point C)
        {
            int ABx = B.x - A.x;
            int ABy = B.y - A.y;
            int num = ABx * (A.y - C.y) - ABy * (A.x - C.x);
            if (num < 0)
                num = -num;
            return num;
        }
     
        public void findHull(Point A, Point B, List<Point> set,
                Set<Point> hull)
        {
            // Find points on convex hull from the set Sk of points 
            // that are on the right side of the oriented line from P to Q
            
            // If Sk has no point, then return. 
            if (set.size() == 0) {
                return;
            } else if (set.size() == 1) {
                Point p = set.get(0);
                set.remove(p);
                hull.add(p);
                return;
            }
            
            // From the given set of points in Sk, find farthest point, say C, from segment PQ 
            int dist = Integer.MIN_VALUE;
            List<Point> furthestPoints = new ArrayList<Point>();
            for (Point p : set)
            {
                int distance = distance(A, B, p);
                if (distance >= dist)
                {
                    dist = distance;
                    if (dist > 0) {
                        furthestPoints.clear();
                    }
                    furthestPoints.add(p);
                }
            }
            // Normally we'd ignore co-linear points but in this case we're adding them to the hull
            if (dist == 0) {
                hull.addAll(furthestPoints);
                return;
            }
            
            // Add point C to convex hull at the location between P and Q
            Point P = furthestPoints.get(0);
            set.remove(P);
            hull.add(P);
     
            // Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2 
            //   where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented 
            //   line from  P to C, and S2 are points on the right side of the oriented line from C to Q.
            List<Point> leftSetAP = new ArrayList<Point>();
            List<Point> leftSetPB = new ArrayList<Point>();
            for (Point M : set)
            {
                // Determine who's to the left of AP
                if (pointLocation(A, P, M) >= 0)
                {
                    leftSetAP.add(M);
                }
                // Determine who's to the left of PB
                if (pointLocation(P, B, M) >= 0)
                {
                    leftSetPB.add(M);
                }
            }
            
            findHull(A, P, leftSetAP, hull);
            findHull(P, B, leftSetPB, hull);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.