source: trunk/src/org/expeditee/core/bounds/PolygonBounds.java@ 1415

package org.expeditee.core.bounds;

import java.util.LinkedList;
import java.util.List;

import org.expeditee.core.Line;
import org.expeditee.core.Point;

/**
 * A bounds that is defined as the area enclosed by a polygon formed
 * from a set of points. When considering if something is enclosed by
 * a polygon, the set of points is always considered closed (even if
 * the first and last points arenn't equal).
 * 
 * @author cts16
 */
public class PolygonBounds extends Bounds {

        /** The points that form this polygon. */
        private List<Point> _points;
        
        /** The right-most extent of this bounds. */
        Integer _maxX;
        /** The left-most extent of this bounds. */
        Integer _minX;
        /** The down-most extent of this bounds. */
        Integer _maxY;
        /** The up-most extent of this bounds. */
        Integer _minY;
        
        /** Standard constructor (creates a degenerate polygon with no points). */
        public PolygonBounds()
        {
                _points = new LinkedList<Point>();
                _maxX = _minX = _maxY = _minY = null;
        }
        
        /** Copy constructor. */
        public PolygonBounds(PolygonBounds other)
        {
                this();
                for (Point p : other._points) {
                        addPoint(p);
                }
        }
        
        /**
         * Constructs a polygon from a set of lines. Lines should be connected
         * end to end, otherwise the resulting polygon may not match the given input.
         */
        public PolygonBounds(Line[] lines)
        {
                this();
                for (Line line : lines) {
                        addPoint(line.getFirstEnd());
                }
                addPoint(lines[lines.length - 1].getSecondEnd());
        }
        
        /** Adds a new point to the polygon. */
        public void addPoint(Point p)
        {
                addPoint(p.getX(), p.getY());
        }
        
        /** Adds a new point to the polygon. */
        public void addPoint(int x, int y)
        {
                _points.add(new Point(x, y));
                if (_maxX == null || x > _maxX.intValue()) _maxX = new Integer(x);
                if (_minX == null || x < _minX.intValue()) _minX = new Integer(x);
                if (_maxY == null || y > _maxY.intValue()) _maxY = new Integer(y);
                if (_minY == null || y < _minY.intValue()) _minY = new Integer(y);
        }
        
        /** Gets the point at the given index in this polygon. */
        public Point getPoint(int index)
        {
                if (0 <= index && index < getPointCount()) return _points.get(index).clone();
                
                return null;
        }
        
        /** Returns the number of points in this polygon. */
        public int getPointCount()
        {
                return _points.size();
        }
        
        /** Returns a copy of the points of this polygon as an array. */
        public Point[] toArray()
        {
                Point[] ret = new Point[_points.size()];
                
                for (int i = 0; i < _points.size(); i++) {
                        ret[i] = _points.get(i).clone();
                }
                
                return ret;
        }
        
        @Override
        public PolygonBounds translate(int x, int y)
        {
                for (Point p : _points) p.add(x, y);
                
                if (_maxX != null) _maxX = new Integer(_maxX.intValue() + x);
                if (_minX != null) _minX = new Integer(_minX.intValue() + x);
                if (_maxY != null) _maxY = new Integer(_maxY.intValue() + y);
                if (_minY != null) _minY = new Integer(_minY.intValue() + y);
                
                return this;
        }
        
        /**
         * Rotates all of the points in this polygon about the given x/y coordinate.
         * 
         * @param angle Clockwise angle of rotation in radians.
         */ 
        public PolygonBounds rotate(double angle, int x, int y)
        {
                // Rotate each point
                for (Point p : _points) {
                        p.rotate(angle, x, y);
                }
                
                // Non-trivial change to mins/maxs, so recalculate
                recalculateExtents();
                
                return this;
        }
        
        /**
         * Rotates the polygon around a point.
         * 
         * @param angle
         *              The clockwise angle to rotate the polygon through (in radians).
         * 
         * @param cor
         *              The centre of rotation.
         */
        public void rotate(double angle, Point cor)
        {
                rotate(angle, cor.getX(), cor.getY());
        }
        
        /**
         * Code adapted from java.awt.Polygon.contains(double x, double y).
         * 
         * @author cts16
         */
        @Override
        public boolean contains(int x, int y) {
                int npoints = _points.size();
                if (npoints <= 2) {
            return false;
        }
                
        int hits = 0;

        int lastx = _points.get(npoints - 1).getX();
        int lasty = _points.get(npoints - 1).getY();
        int curx, cury;

        // Walk the edges of the polygon
        for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
            curx = _points.get(i).getX();
            cury = _points.get(i).getY();

            if (cury == lasty) {
                continue;
            }

            int leftx;
            if (curx < lastx) {
                if (x >= lastx) {
                    continue;
                }
                leftx = curx;
            } else {
                if (x >= curx) {
                    continue;
                }
                leftx = lastx;
            }

            double test1, test2;
            if (cury < lasty) {
                if (y < cury || y >= lasty) {
                    continue;
                }
                if (x < leftx) {
                    hits++;
                    continue;
                }
                test1 = x - curx;
                test2 = y - cury;
            } else {
                if (y < lasty || y >= cury) {
                    continue;
                }
                if (x < leftx) {
                    hits++;
                    continue;
                }
                test1 = x - lastx;
                test2 = y - lasty;
            }

            if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
                hits++;
            }
        }

        return ((hits & 1) != 0);
        }
        
        @Override
        public int getMaxX() {
                return _maxX != null ? _maxX : 0;
        }

        @Override
        public int getMinX() {
                return _minX != null ? _minX : 0;
        }

        @Override
        public int getMaxY() {
                return _maxY != null ? _maxY : 0;
        }

        @Override
        public int getMinY() {
                return _minY != null ? _minY : 0;
        }

        @Override
        public boolean equals(Bounds other) {
                if (other instanceof PolygonBounds) {
                        PolygonBounds p = (PolygonBounds) other;
                        if (p._points.size() == this._points.size()) {
                                for (int i = 0; i < p._points.size(); i++) {
                                        if (!(p._points.get(i).equals(this._points.get(i)))) return false;
                                }
                                return true;
                        }
                }
                
                return false;
        }
        
        /** Convenience method to create a polygon in the shape of a diamond. */
        public static PolygonBounds getDiamond(int width, int height)
        {
                PolygonBounds diamond = new PolygonBounds();
                
                diamond.addPoint(0, -height / 2);
                diamond.addPoint(width / 2, 0);
                diamond.addPoint(0, height / 2);
                diamond.addPoint(-width / 2, 0);
                
                return diamond;
        }
        
        /** Convenience method to create a polygon in the shape of a triangle. */
        public static PolygonBounds getTriangle(int base, int height)
        {
                PolygonBounds triangle = new PolygonBounds();
                
                triangle.addPoint(0, -height / 2);
                triangle.addPoint(base / 2, height / 2);
                triangle.addPoint(-base / 2, height / 2);
                
                return triangle;
        }

        @Override
        public boolean intersects(AxisAlignedBoxBounds other) {
                // Check if any polygon points are inside the box
                for (Point p : _points) {
                        if (other.contains(p)) return true;
                }
                
                // Check if any of the border lines intersect
                Line[] boxLines = other.getBorderLines();
                Line[] polyLines = getBorderLines();
                if (Line.anyIntersections(boxLines, polyLines, Line.PIXEL_ERROR)) return true;
                
                // Check if any of the box points are inside the polygon
                // (only test p1 as p2 is the p1 of another line)
                for (Line boxLine : boxLines) {
                        if (contains(boxLine.getFirstEnd())) return true;
                }
                
                // If all tests fail, no intersection
                return false;
        }

        @Override
        public boolean intersects(CombinationBounds other) {
                // Defer to the CombinationBounds routine
                return other.intersects(this);
        }

        @Override
        public boolean intersects(EllipticalBounds other) {
                // Defer to the EllipticalBounds routine
                return other.intersects(this);
        }

        @Override
        public boolean intersects(PolygonBounds other) {
                // Check if any of the border lines intersect
                Line[] otherLines = other.getBorderLines();
                Line[] thisLines = getBorderLines();
                if (Line.anyIntersections(otherLines, thisLines, Line.PIXEL_ERROR)) return true;
                
                // If no line intersections, one polygon must be inside the other to intersect
                return other.contains(thisLines[0].getFirstEnd()) || this.contains(otherLines[0].getFirstEnd());
        }
        
        /** Gets an array of the vertices that make up this polygon. */
        public Point[] getVertices()
        {
                Point[] ret = new Point[_points.size()];
                
                for (int i = 0; i < _points.size(); i++) {
                        ret[i] = _points.get(i).clone();
                }
                
                return ret;
        }
        
        /** Gets an array of lines that represent the (closed) border of this polygon. */
        public Line[] getBorderLines()
        {
                return getBorderLines(true);
        }
        
        /**
         * Gets an array of lines that represent the border of this polygon.
         * 
         * @param autoClose
         *              Whether to automatically create a line from the last point to the 
         *              first to close this polygon (ignored if first and last point are equal).
         * 
         * @return
         *              The array of border lines.
         */
        public Line[] getBorderLines(boolean autoClose)
        {
                // Don't need to autoClose if first and last points are equal
                autoClose = autoClose && _points.get(0).equals(_points.get(_points.size() - 1));
                
                // Calculate how many lines we will need to generate
                int nLines = _points.size();
                if (!autoClose) nLines--;
                
                // Generate the lines
                Line[] lines = new Line[nLines];
                for (int i = 0; i < nLines; i++) {
                        Point p1 = new Point(_points.get(i));
                        Point p2 = new Point(_points.get((i + 1) % _points.size()));
                        lines[i] = new Line(p1, p2);
                }
                
                return lines;
        }
        
        @Override
        public double getArea()
        {
                if (_points.size() < 3) return 0.0;
                
                double area = 0.0;
                
                for (int i = 0; i < _points.size(); i++) {
                        Point p1 = _points.get(i);
                        Point p2 = _points.get((i + 1) % _points.size());
                        area += p1.getX() * p2.getY() - p2.getX() * p1.getY();
                }
                
                return Math.abs(area / 2);
        }

        @Override
        public boolean perimeterContains(Point p, double error) {
                Line[] lines = getBorderLines();
                
                for (Line line : lines) {
                        if (line.contains(p, error)) return true;
                }
                
                return false;
        }

        @Override
        public boolean completelyContains(AxisAlignedBoxBounds other)
        {
                // Treat the box as a polygon
                return completelyContains(other.getPolygon());
        }

        @Override
        public boolean completelyContains(CombinationBounds other)
        {
                // Can't contain nothing
                if (other == null) return false;
                
                // Must contain all sub-bounds of the combination bounds
                for (Bounds bounds : other._bounds) {
                        if (!completelyContains(bounds)) return false;
                }
                
                return true;
        }

        @Override
        public boolean completelyContains(EllipticalBounds other)
        {
                // Can't contain nothing
                if (other == null) return false;
                
                // No polygon vertices can be inside the ellipse
                for (Point vertex : _points) {
                        if (other.contains(vertex)) return false;
                }
                
                // No boundary lines can intersect the ellipse
                for (Line line : getBorderLines()) {
                        if (other.isIntersectedByLine(line)) return false;
                }
                
                return true;
        }

        @Override
        public boolean completelyContains(PolygonBounds other)
        {
                // Can't contain nothing
                if (other == null) return false;
                
                // Must contain all points of other
                for (Point p : other._points) {
                        if (!contains(p)) return false;
                }
                
                // Can't be any line intersections
                Line[] thisLines = getBorderLines();
                Line[] otherLines = other.getBorderLines();
                if (Line.anyIntersections(thisLines, otherLines, Line.PIXEL_ERROR)) return false;
                
                return true;
        }
        
        /** Whether the given point is a vertex of this polygon. */
        public boolean isVertex(Point p)
        {
                return _points.contains(p);
        }
        
        /** Whether or not this polygon is closed (first and last points are equal). */
        public boolean isClosed()
        {
                return _points.get(0).equals(_points.get(getPointCount() - 1));
        }
        
        /** Closes this polygon (adds the first point as the last). */
        public PolygonBounds close()
        {
                if (!isClosed()) addPoint(_points.get(0).clone());
                
                return this;
        }
        
        /** Creates a polygon that represents the same area as a box bounds. */
        public static PolygonBounds fromBox(AxisAlignedBoxBounds box)
        {
                if (box == null) return null;
                
                // Get the corners of the box
                Point[] corners = box.getCorners();
                
                // Add the corners to a new polygon
                PolygonBounds ret = new PolygonBounds();
                for (Point corner : corners) ret.addPoint(corner);
                
                return ret.close();
        }
        
        /**
         * Creates a polygon that approximates the given ellipse.
         * 
         * @param nSegments
         *              The number of segments the resulting polygon should have. Must be at least 3.
         */ 
        public static PolygonBounds fromEllipse(EllipticalBounds ellipse, int nSegments)
        {
                if (ellipse == null || nSegments < 3) return null;
                
                int centreX = ellipse.getCentre().getX();
                int centreY = ellipse.getCentre().getY();
                double xRadius = ellipse.getDiameters().width / 2.0;
                double yRadius = ellipse.getDiameters().height / 2.0;
                double radians = 0.0;
                
                PolygonBounds ret = new PolygonBounds();
                for (int i = 0; i < nSegments; i++) {
                        int x = (int) (xRadius * Math.cos(radians)) + centreX;
                        int y = (int) (yRadius * Math.sin(radians)) + centreY;
                        ret.addPoint(x, y);
                        radians += (2.0 * Math.PI) / nSegments;
                }
                
                return ret.close();
        }
        
        @Override
        public PolygonBounds clone()
        {
                return new PolygonBounds(this);
        }
        
        /**
         * Recalculates the min/max x/y coordinates. Normally this should be done incrementally
         * as points are added, but sometimes you just need to completely redo them.
         */
        private void recalculateExtents()
        {
                _maxX = _minX = _maxY = _minY = null;
                
                for (Point p : _points) {
                        if (_maxX == null || p.getX() > _maxX.intValue()) _maxX = new Integer(p.getX());
                        if (_minX == null || p.getX() < _minX.intValue()) _minX = new Integer(p.getX());
                        if (_maxY == null || p.getY() > _maxY.intValue()) _maxY = new Integer(p.getY());
                        if (_minY == null || p.getY() < _minY.intValue()) _minY = new Integer(p.getY());
                }
        }
        
        public String toString() {
                StringBuilder sb = new StringBuilder("PolygonBounds with: ");
                sb.append("[MinX: " + getMinX() + "]");
                sb.append("[MinY: " + getMinY() + "]");
                sb.append("[MaxX: " + getMaxX() + "]");
                sb.append("[MaxY: " + getMaxY() + "]");
                return sb.toString();
        }

}