erect the fence | convex hull problem

convexHull.cpp

//https://leetcode.com/problems/erect-the-fence/description/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * Created by ajaykumar.yadav on 11/09/18.
 **/


class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }
}

class Solution {

    public int orientation(Point p, Point q, Point r) {
        return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    }

    public boolean inBetween(Point p, Point i, Point q) {
        boolean a = i.x >= p.x && i.x <= q.x || i.x <= p.x && i.x >= q.x;
        boolean b = i.y >= p.y && i.y <= q.y || i.y <= p.y && i.y >= q.y;
        return a && b;
    }

    public List<Point> outerTrees(Point[] points) {

        HashSet<Point> hull = new HashSet<>();

        //first find leftmost point index
        int leftMostPoint = 0;
        int arrLength = points.length;
        for (int i = 0; i < arrLength; i++) {
            if (points[i].x < points[leftMostPoint].x) {
                leftMostPoint = i;
            }
        }
        //left most point is decided by this time


        int currentLeftMostPoint = leftMostPoint;
        do {
            //find next probablepoint
            int nextPoint = (currentLeftMostPoint + 1) % arrLength;

            //now check if there  is any point which is in left of line joining  leftMostPoint  and  nextPoint
            for (int i = 0; i < arrLength; i++) {
                if (orientation(points[currentLeftMostPoint], points[nextPoint], points[i]) < 0) {
                    nextPoint = i;
                }
            }

            //check for colinear points , if they
            for (int i = 0; i < arrLength; i++) {
                if (i != currentLeftMostPoint && i != nextPoint && (orientation(points[currentLeftMostPoint], points[nextPoint], points[i]) == 0) && inBetween(points[currentLeftMostPoint], points[i], points[nextPoint])) {
                    hull.add(points[i]);
                }
            }

            //add next pint to solution
            hull.add(points[nextPoint]);

            //move currnetLeftMostPoint
            currentLeftMostPoint = nextPoint;


        } while (currentLeftMostPoint != leftMostPoint);

        return new ArrayList<>(hull);
    }

    public static void main(String[] args) {
        List<Point> listPoint = new ArrayList<>();
        Point p1 = new Point(0, 0);
        Point p2 = new Point(0, 10);
        Point p3 = new Point(5, 0);
        Point p4 = new Point(6, 18);
        Point p5 = new Point(3, 3);

        listPoint.add(p1);
        listPoint.add(p2);
        listPoint.add(p3);
        listPoint.add(p4);
        listPoint.add(p5);

        Object[] pArray = listPoint.toArray();
        Point[] pointArray = new Point[5];
        for (int i = 0; i < pArray.length; i++) {
            pointArray[i] = (Point) pArray[i];
        }
        List<Point> lp = new Solution().outerTrees(pointArray);
        lp.stream().forEach(e -> {
            System.out.println(e.x + " "+e.y);
        });
    }
}