CompGeom.java

import java.util.*;

public class CompGeom {
    public static void main(String[] args) {
        List<Point> points = new ArrayList<Point>();
//        points.add(new Point(5, 4));
//        points.add(new Point(4, 2));
//        points.add(new Point(3, 3));
//        points.add(new Point(6, 1));
//        points.add(new Point(7, 4));
//        points.add(new Point(2, 1));
//        points.add(new Point(1, 3));

        points.add(new Point(0, 0));
        points.add(new Point(0, 1));
        points.add(new Point(1, 0));
        points.add(new Point(1, 1));
        points.add(new Point(0.5, 0.5));

        Polygon poly = Polygon.convexHull(points);
        System.out.println(poly.area());
        System.out.println(poly.boundary);
        System.out.println(poly.containsPoint(new Point(0.3, 0.1)));
    }

    /**
     * Polygon class, holds an ordered list of points representing the boundary.
     */
    static class Polygon {
        List<Point> boundary;
        double minX, maxX, minY, maxY;

        public Polygon(List<Point> boundary) {
            this.boundary = boundary;

            List<Point> boundPoints = new ArrayList<>(boundary);
            Collections.sort(boundPoints, new Point.XYComparator());
            minX = boundPoints.get(0).x;
            maxX = boundPoints.get(boundPoints.size() - 1).x;

            Collections.sort(boundPoints, new Point.YXComparator());
            minY = boundPoints.get(0).y;
            maxY = boundPoints.get(boundPoints.size() - 1).y;
        }

        /**
         * Calculate and return the area of the Polygon.
         *
         * @return the area of the polygon
         */
        public double area() {
            double area = 0;
            Point p0 = boundary.get(0);
            for (int i = 1; i < boundary.size() - 1; i++) {
                area += Math.abs(new Vector(p0, boundary.get(i)).crossProductWith(new Vector(p0, boundary.get(i + 1)))) / 2.0;
            }
            return area;
        }

        /**
         * Determine if a Point is in the polygon's bounding box.
         *
         * @param p the Point to test
         * @return true, if the point is in the polygon's bounding box, false otherwise
         */
        public boolean inBoundingBox(Point p) {
            return minX <= p.x && p.x <= maxX
                    && minY <= p.y && p.y <= maxY;
        }

        /**
         * Determine if a Point is in a polygon using inBoundingBox(Point) then ray casting. On the boundary is
         * considered inside.
         *
         * @param p the Point to test
         * @return true, if the point is in the polygon, false otherwise
         */
        public boolean containsPoint(Point p) {
            if (inBoundingBox(p)) {
                LineSegment ray = new LineSegment(p, new Point(minX - 1, p.y));

                int intersection = 0;

                for (int i = 0; i < boundary.size(); i++) {
                    if (Point.intersectionOf(new LineSegment(boundary.get(i), boundary.get((i + 1) % boundary.size())), ray) != null) {
                        intersection++;
                    }
                }

                // If the number of intersections is odd, then the point is inside the polygon
                return intersection % 2 == 1;
            }
            return false;
        }

        /**
         * Cut a Polygon into two or more parts if the line intersects the polygon or just return the polygon otherwise.
         *
         * @param l the LineType used to cut the polygon
         * @param <LineType> anything that extends Line (i.e. Line or LineSegment)
         * @return either two polygons if the line intersected the polygon or the original polygon back
         */
        public <LineType extends Line> List<Polygon> cut(LineType l) {
            // TODO: Implement
            return null;
        }

        /**
         * Find the convex hull from a list of Points and return the Polygon represented by it.
         *
         * @param points the list of points to calculate the convex hull from
         * @return a new convex hull polygon from a list of points
         */
        public static Polygon convexHull(List<Point> points) {
            Collections.sort(points, new Point.YXComparator());

            Collections.sort(points, new Point.PolarComparator(points.get(0)));
            Iterator<Point> it = points.iterator();
            List<Point> boundary = new ArrayList<Point>();
            boundary.add(0, it.next());
            boundary.add(0, it.next());
            boundary.add(0, it.next());

            while (it.hasNext()) {
                Point nextToTop = boundary.get(1);
                Point top = boundary.get(0);
                Point p = it.next();
                Vector v1 = new Vector(nextToTop, top);
                Vector v2 = new Vector(top, p);

                Vector.TurningDirection td = v1.turningDirectionOnto(v2);

                while (td != Vector.TurningDirection.LEFT) {
                    boundary.remove(0);
                    top = nextToTop;
                    nextToTop = boundary.get(1);

                    v1 = new Vector(nextToTop, top);
                    v2 = new Vector(top, p);

                    td = v1.turningDirectionOnto(v2);
                }
                boundary.add(0, p);
            }

            return new Polygon(boundary);
        }
    }

    /**
     * Point class that holds an x and y co-ordinate.
     */
    static class Point {
        double x, y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }

        /**
         * Compare points, ordered by lowest x first, then lowest y.
         */
        static class XYComparator implements Comparator<Point> {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.x == p2.x)
                    return Double.compare(p1.y, p2.y);
                return Double.compare(p1.x, p2.x);
            }
        }

        /**
         * Compare points, ordered by lowest y first, then lowest x.
         */
        static class YXComparator implements Comparator<Point> {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.y == p2.y)
                    return Double.compare(p1.x, p2.x);
                return Double.compare(p1.y, p2.y);
            }
        }

        /**
         * Compare points, ordered anti-clockwise rotationally from a single points.
         */
        static class PolarComparator implements Comparator<Point> {
            Point p;
            public PolarComparator(Point p) {
                this.p = p;
            }

            @Override
            public int compare(Point p1, Point p2) {
                Vector v1 = new Vector(p, p1);
                Vector v2 = new Vector(p, p2);
                Vector.TurningDirection td = v1.turningDirectionOnto(v2);
                if (td == Vector.TurningDirection.STRAIGHT)
                    return Double.compare(v1.length(), v2.length());
                else
                    return td.val;
            }
        }

        /**
         * Find the intersection of two LineTypes by determining if their bounding boxes intersect then comparing the
         * signs of the cross products from one end of each line to the ends of the other line.
         *
         * @param l1 the first LineType
         * @param l2 the second LineType
         * @param <LineType> anything that extends Line (i.e. Line or LineSegment)
         * @return the Point of intersection or null if the lines don't intersect or are parallel
         */
        static <LineType extends Line> Point intersectionOf(LineType l1, LineType l2) {
            if (l1.boundingBoxIntersects(l2)) {
                Vector v0, v1, v2;
                Vector.TurningDirection v0ToV1, v0ToV2;

                // Only check from l1 to the ends of l2 if l2 is a line segment
                if (l2 instanceof LineSegment) {
                    v0 = new Vector(l1.p1, l1.p2);
                    v1 = new Vector(l1.p1, l2.p1);
                    v2 = new Vector(l1.p1, l2.p2);
                    v0ToV1 = v0.turningDirectionOnto(v1);
                    v0ToV2 = v0.turningDirectionOnto(v2);

                    if (v0ToV1 == v0ToV2 && v0ToV1 != Vector.TurningDirection.STRAIGHT)
                        return null;
                }

                // Only check from l2 to the ends of l1 if l1 is a line segment
                if (l1 instanceof LineSegment) {
                    v0 = new Vector(l2.p1, l2.p2);
                    v1 = new Vector(l2.p1, l1.p1);
                    v2 = new Vector(l2.p1, l1.p2);
                    v0ToV1 = v0.turningDirectionOnto(v1);
                    v0ToV2 = v0.turningDirectionOnto(v2);

                    if (v0ToV1 == v0ToV2 && v0ToV1 != Vector.TurningDirection.STRAIGHT)
                        return null;
                }

                if ((l1.p1.y - l1.p2.y) / (l1.p1.x - l1.p2.x) == (l2.p1.y - l2.p2.y) / (l2.p1.x - l2.p2.x))
                    return null; // co-linear lines

                // https://en.wikipedia.org/wiki/Line–line_intersection#Given_two_points_on_each_line
                // x = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)
                //     -----------------------------------------------------------------
                //     (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

                // y = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)
                //     -----------------------------------------------------------------
                //     (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

                double x = ((l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x) * (l2.p1.x - l2.p2.x) - (l1.p1.x - l1.p2.x) * (l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x))
                        / ((l1.p1.x - l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x - l2.p2.x));
                double y = ((l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x))
                        / ((l1.p1.x - l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x - l2.p2.x));

                return new Point(x, y);
            }

            // Bounding boxes don't intersect
            return null;
        }
    }

    /**
     * A vector from the origin to a Point.
     */
    static class Vector extends Point {
        public Vector(double x, double y) {
            super(x, y);
        }

        public Vector(Point p1, Point p2) {
            super(p2.x - p1.x, p2.y - p1.y);
        }

        /**
         * Calculate the cross product of this vector and a given vector
         *
         * @param v the second vector to calculate the cross product with
         * @return the result of the this vector crossed with v
         */
        public double crossProductWith(Vector v) {
            return x * v.y - v.x * y;
        }

        /**
         * Calculate the length of this vector.
         *
         * @return the length of this vector
         */
        public double length() {
            return Math.sqrt(x * x + y * y);
        }

        /**
         * Determine the turning direction from this vector to another vector.
         *
         * @param v the vector we're turning onto
         * @return the TurningDirection taken
         */
        public TurningDirection turningDirectionOnto(Vector v) {
            return TurningDirection.turningDirectionFromCrossProduct(this.crossProductWith(v));
        }

        /**
         * TurningDirection enumerator, used to represent the turning direction from one Vector to the next.
         */
        enum TurningDirection {
            LEFT(-1),
            STRAIGHT(0),
            RIGHT(1);

            int val;
            TurningDirection(int val) {
                this.val = val;
            }

            /**
             * Get the TurningDirection from the result of the cross product, RIGHT if negative, LEFT if positive,
             * STRAIGHT if 0.
             *
             * @param crossProductResult result of the cross product
             * @return the resultant TurningDirection
             */
            static TurningDirection turningDirectionFromCrossProduct(double crossProductResult) {
                if (crossProductResult < 0) return RIGHT;
                else if (crossProductResult == 0) return STRAIGHT;
                else return LEFT;
            }
        }
    }

    /**
     * Infinitely long line defined by two Points.
     */
    static class Line {
        public Point p1, p2;

        public Line(Point p1, Point p2) {
            if (p2.y < p1.y || (p1.y == p2.y && p2.x < p1.x)) {
                this.p1 = p2;
                this.p2 = p1;
            } else {
                this.p1 = p1;
                this.p2 = p2;
            }
        }

        /**
         * Determine if a LineType's bounding box intersect this' bounding box, always true if either this or l is a
         * Line.
         *
         * @param l the LineType to test bounding boxes against
         * @param <LineType> anything that extends Line (i.e. Line or LineSegment)
         * @return true, if the bounding boxes intersect, false otherwise
         */
        public <LineType extends Line> boolean boundingBoxIntersects(LineType l) {
            // Lines are infinite and therefore always have intersecting bounding boxes
            return true;
        }
    }

    /**
     * Line that is contained between two points.
     */
    static class LineSegment extends Line {
        public LineSegment(Point p1, Point p2) {
            super(p1, p2);
        }

        @Override
        public <LineType extends Line> boolean boundingBoxIntersects(LineType l) {
            return !(l instanceof LineSegment) || // then l is a line
                    p2.x >= l.p1.x
                            && l.p2.x >= p1.x
                            && p2.y >= l.p1.y
                            && l.p2.y >= p1.y;
        }

        /**
         * Calculate and return the line segment's length.
         *
         * @return the line segment's length
         */
        public double length() {
            return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
        }
    }
}