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();
	}

}