Quick Hull Algorithm in Java

This is a Java Program to implement Quick Hull Algorithm to find convex hull. Here we’ll talk about the Quick Hull algorithm, which is one of the easiest to implement and has a reasonable expected running time of O(n log n).

Here is the source code of the Java Program to Implement Quick Hull Algorithm to Find Convex Hull. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to find a points in convex hull using quick hull method

```
//source: Alexander Hrishov's website
```

//URL: http://www.ahristov.com/tutorial/geometry-games/convex-hull.html

```
 
```
```
import java.util.ArrayList;
```
```
import java.util.Scanner;
```
```
 
```
```
public class QuickHull
```
```
{
```

    public ArrayList<Point> quickHull(ArrayList<Point> points)

```
    {
```

        ArrayList<Point> convexHull = new ArrayList<Point>();

```
        if (points.size() < 3)
```

            return (ArrayList) points.clone();

```
 
```

        int minPoint = -1, maxPoint = -1;

```
        int minX = Integer.MAX_VALUE;
```
```
        int maxX = Integer.MIN_VALUE;
```

        for (int i = 0; i < points.size(); i++)

```
        {
```
```
            if (points.get(i).x < minX)
```
```
            {
```
```
                minX = points.get(i).x;
```
```
                minPoint = i;
```
```
            }
```
```
            if (points.get(i).x > maxX)
```
```
            {
```
```
                maxX = points.get(i).x;
```
```
                maxPoint = i;
```
```
            }
```
```
        }
```
```
        Point A = points.get(minPoint);
```
```
        Point B = points.get(maxPoint);
```
```
        convexHull.add(A);
```
```
        convexHull.add(B);
```
```
        points.remove(A);
```
```
        points.remove(B);
```
```
 
```

        ArrayList<Point> leftSet = new ArrayList<Point>();

        ArrayList<Point> rightSet = new ArrayList<Point>();

```
 
```

        for (int i = 0; i < points.size(); i++)

```
        {
```
```
            Point p = points.get(i);
```

            if (pointLocation(A, B, p) == -1)

```
                leftSet.add(p);
```

            else if (pointLocation(A, B, p) == 1)

```
                rightSet.add(p);
```
```
        }
```

        hullSet(A, B, rightSet, convexHull);

        hullSet(B, A, leftSet, convexHull);

```
 
```
```
        return convexHull;
```
```
    }
```
```
 
```

    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 hullSet(Point A, Point B, ArrayList<Point> set,

```
            ArrayList<Point> hull)
```
```
    {
```

        int insertPosition = hull.indexOf(B);

```
        if (set.size() == 0)
```
```
            return;
```
```
        if (set.size() == 1)
```
```
        {
```
```
            Point p = set.get(0);
```
```
            set.remove(p);
```

            hull.add(insertPosition, p);

```
            return;
```
```
        }
```
```
        int dist = Integer.MIN_VALUE;
```
```
        int furthestPoint = -1;
```

        for (int i = 0; i < set.size(); i++)

```
        {
```
```
            Point p = set.get(i);
```

            int distance = distance(A, B, p);

```
            if (distance > dist)
```
```
            {
```
```
                dist = distance;
```
```
                furthestPoint = i;
```
```
            }
```
```
        }
```

        Point P = set.get(furthestPoint);

```
        set.remove(furthestPoint);
```
```
        hull.add(insertPosition, P);
```
```
 
```

        // Determine who's to the left of AP

        ArrayList<Point> leftSetAP = new ArrayList<Point>();

        for (int i = 0; i < set.size(); i++)

```
        {
```
```
            Point M = set.get(i);
```

            if (pointLocation(A, P, M) == 1)

```
            {
```
```
                leftSetAP.add(M);
```
```
            }
```
```
        }
```
```
 
```

        // Determine who's to the left of PB

        ArrayList<Point> leftSetPB = new ArrayList<Point>();

        for (int i = 0; i < set.size(); i++)

```
        {
```
```
            Point M = set.get(i);
```

            if (pointLocation(P, B, M) == 1)

```
            {
```
```
                leftSetPB.add(M);
```
```
            }
```
```
        }
```
```
        hullSet(A, P, leftSetAP, hull);
```
```
        hullSet(P, B, leftSetPB, hull);
```
```
 
```
```
    }
```
```
 
```

    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 static void main(String args[])

```
    {
```

        System.out.println("Quick Hull Test");

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the number of points");

```
        int N = sc.nextInt();
```
```
 
```

        ArrayList<Point> points = new ArrayList<Point>();

        System.out.println("Enter the coordinates of each points: <x> <y>");

```
        for (int i = 0; i < N; i++)
```
```
        {
```
```
            int x = sc.nextInt();
```
```
            int y = sc.nextInt();
```
```
            Point e = new Point(x, y);
```
```
            points.add(i, e);
```
```
        }
```
```
 
```
```
        QuickHull qh = new QuickHull();
```

        ArrayList<Point> p = qh.quickHull(points);

```
        System.out
```

                .println("The points in the Convex hull using Quick Hull are: ");

        for (int i = 0; i < p.size(); i++)

            System.out.println("(" + p.get(i).x + ", " + p.get(i).y + ")");

```
        sc.close();
```
```
    }
```
```
}
```

Output:

$ javac QuickHull.java
$ java QuickHull
 
Quick Hull Test
Enter the number of points
4
Enter the coordinates of each points: <x> <y>
12 32
45 98
65 12
10 30
The points in the Convex hull using Quick Hull are: 
(10, 30)
(45, 98)
(65, 12)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Check if Point is Inside Polygon

» Next - Java Program to Find the Volume of a Tetrahedron using Determinants

Related Posts:

Recommended Articles: