package net.returnvoid.graphics.shape;

import java.util.ArrayList;

import net.returnvoid.tools.RMath;
import processing.core.PApplet;
import processing.core.PVector;

/**
 * A class for building and transforming lines.
 * 
 * @author Diana Lange
 *
 */
public class Line implements RShape {

	/**
	 * The coordinates (start and end) of this line.
	 */
	private PVector[] coordinates;

	/**
	 * The PApplet object for drawing thinks.
	 */
	protected PApplet parent;

	/**
	 * The minimal x-location of this shape (defines the bounding box). Can be
	 * null. If this is null, the shape has been updated (e.g. was rotated) and
	 * the min / max locations & bounding box have to be re-calculated.
	 */
	private Float minX = null;

	/**
	 * The maximal x-location of this shape (defines the bounding box).
	 */
	private Float maxX = null;

	/**
	 * The minimal y-location of this shape (defines the bounding box).
	 */
	private Float minY = null;

	/**
	 * The maximal y-location of this shape (defines the bounding box).
	 */
	private Float maxY = null;

	/**
	 * The bounding box of this shape. Will be null until getBoundingBox() is
	 * called.
	 */
	private Rect boundingBox = null;

	/**
	 * Builds an empty shape. The coordinates have to be set manually.
	 * 
	 * @param parent
	 *            The PApplet object.
	 */
	private Line(PApplet parent) {
		this.parent = parent;

	}

	/**
	 * Builds a new line with the given parameters.
	 * 
	 * @param parent
	 *            The PApplet object.
	 * @param start
	 *            The start-location of the line.
	 * @param end
	 *            The end-location of the line.
	 */
	public Line(PApplet parent, PVector start, PVector end) {
		this.parent = parent;
		this.coordinates = new PVector[2];
		this.coordinates[0] = start;
		this.coordinates[1] = end;
	}

	/**
	 * Builds a new line with the given parameters.
	 * 
	 * @param parent
	 *            The PApplet object.
	 * @param startX
	 *            The start-x-location of the line.
	 * @param startY
	 *            The start-y-location of the rectangle (top-left corner).
	 * @param endX
	 *            The end-x-location of the line.
	 * @param endY
	 *            The end-y-location of the line.
	 */
	public Line(PApplet parent, float startX, float startY, float endX, float endY) {
		this(parent, new PVector(startX, startY), new PVector(endX, endY));
	}

	/**
	 * Builds a new line with the given parameters.
	 * 
	 * @param parent
	 *            The PApplet object.
	 * @param start
	 *            The start-location of the line.
     * @param angle
	 *            The rotation of the line (in radians).
	 * @param length
	 *            The length of the line.
	 */
	public Line(PApplet parent, PVector start, float angle, float length) {
		this(parent, start, new PVector((float) (start.x + Math.cos(angle) * length),
				(float) (start.y + Math.sin(angle) * length)));
	}

	// Getters

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#size()
	 */
	@Override
	public int size() {
		return 2;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#get(int)
	 */
	@Override
	public PVector get(int i) {
		return i == 0 ? getStart() : getEnd();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getStart()
	 */
	@Override
	public PVector getStart() {
		return coordinates[0];
	}

	/**
	 * Returns the end coordinate for this shape.
	 * 
	 * @return The end location.
	 */
	public PVector getEnd() {
		return coordinates[1];
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getBoundingBox()
	 */
	@Override
	public Rect getBoundingBox() {

		if (boundingBox == null) {
			if (minX == null) {
				computeMinMax();
			}

			boundingBox = new Rect(parent, minX, minY, maxX - minX, maxY - minY);
		}

		return boundingBox;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getCenter()
	 */
	@Override
	public PVector getCenter() {
		if (minX == null) {
			computeMinMax();
		}

		return new PVector(0.5f * (minX + maxX), 0.5f * (minY + maxY));
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getX()
	 */
	@Override
	public Float getX() {
		return getStart().x;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getY()
	 */
	@Override
	public Float getY() {
		return getStart().y;
	}

	/**
	 * Returns the length (distance from start to end) of this line.
	 * 
	 * @return The length of the line.
	 */
	public float getLength() {
		return getStart().dist(getEnd());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getCoordinates()
	 */
	@Override
	public PVector[] getCoordinates() {
		return coordinates;
	}

	/**
	 * Returns a normal vector for this line.
	 * 
	 * @return The normal vector.
	 */
	public PVector getNormal() {

		return Line.getNormal(getStart(), getEnd());
	}

	/**
	 * Builds a line, that represents the normal of this line. The normal line
	 * will have its start in the middle of the current line object.
	 * 
	 * @param lineLength
	 *            The length of the normal line.
	 * @return The normal line.
	 */
	public Line getNormalLine(float lineLength) {
		PVector normalCopy = getNormal();

		normalCopy.normalize();
		normalCopy.mult(lineLength);

		// normal starts in the center of the line
		Line line = new Line(parent, normalCopy.x + PApplet.lerp(getStart().x, getEnd().x, 0.5f),
				normalCopy.y + PApplet.lerp(getStart().y, getEnd().y, 0.5f),
				PApplet.lerp(getStart().x, getEnd().x, 0.5f), PApplet.lerp(getStart().y, getEnd().y, 0.5f));
		return line;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#getRotation()
	 */
	@Override
	public Float getRotation() {
		return PApplet.atan2(getEnd().y - getStart().y, getEnd().x - getStart().x);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#copy()
	 */
	@Override
	public Line copy() {
		Line copyLine = new Line(parent);

		PVector[] copyCoordinates = new PVector[2];
		copyCoordinates[0] = new PVector(this.coordinates[0].x, this.coordinates[0].y);
		copyCoordinates[1] = new PVector(this.coordinates[1].x, this.coordinates[1].y);

		copyLine.coordinates = copyCoordinates;

		return copyLine;
	}

	// Setter

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setRotation(float)
	 */
	@Override
	public Line setRotation(float angle) {

		return rotate(coordinates[0], angle - getRotation());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * net.returnvoid.graphics.shape.RShape#setRotation(processing.core.PVector,
	 * float)
	 */
	@Override
	public Line setRotation(PVector rotationCenter, float angle) {

		return rotate(rotationCenter, angle - this.getRotation());
	}

	/**
	 * Sets the length of this line. The line will be scaled around
	 * <b>getStart()</b>.
	 * 
	 * @param length
	 *            The new length of the line (> 0).
	 * @return The current shape.
	 */
	public Line setLength(float length) {

		return scale(coordinates[0], length / getLength());
	}

	/**
	 * Sets the length of this line. The line will be scaled around
	 * <b>center</b>.
	 * 
	 * @param center
	 *            The control point for the scaling.
	 * @param length
	 *            The new length of the line (> 0).
	 * @return The current shape.
	 */
	public Line setLength(PVector center, float length) {

		return scale(center, length / getLength());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setX(float)
	 */
	@Override
	public Line setX(float x) {

		return translate(x - getCenter().x + getLength() * 0.5f, 0);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setY(float)
	 */
	@Override
	public Line setY(float y) {

		return translate(0, y - getCenter().y + getLength() * 0.5f);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setLocation(float, float)
	 */
	@Override
	public Line setLocation(float x, float y) {
		return translate(x - getCenter().x + getLength() * 0.5f, y - getCenter().y + getLength() * 0.5f);
	}

	// Calculus

	/**
	 * Returns the location of an intersection of two lines if they have an
	 * intersection. Returns null otherwise.
	 * 
	 * @param other
	 *            One line.
	 * @return The location of intersection or null.
	 */
	public PVector intersection(Line other) {
		return Line.intersection(this, other, false);
	}

	/**
	 * Returns the location of an intersection of two lines if they have an
	 * intersection. Returns null otherwise.
	 * 
	 * @param other
	 *            One line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then still null will be returned).
	 *            Otherwise all found intersections will be returned.
	 * @return The location of intersection or null.
	 */
	public PVector intersection(Line other, boolean ignoreStartEnd) {
		return Line.intersection(this, other, ignoreStartEnd);
	}

	/**
	 * Tests if two lines have an intersection.
	 * 
	 * @param other
	 *            One line.
	 * @return True, when the two lines intersect.
	 */
	public boolean hasIntersection(Line other) {
		return hasIntersection(other, false);
	}

	/**
	 * Tests if two lines have an intersection.
	 * 
	 * @param other
	 *            One line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then still false will be returned).
	 * @return True, when the two lines intersect.
	 */
	public boolean hasIntersection(Line other, boolean ignoreStartEnd) {
		PVector sec = intersection(other, ignoreStartEnd);

		if (sec == null) {
			return false;
		} else {
			return true;
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#translate(float, float)
	 */
	@Override
	public Line translate(float x, float y) {
		for (int i = 0; i < coordinates.length; i++) {
			PVector p = coordinates[i];
			p.x += x;
			p.y += y;
		}

		minX = null;
		boundingBox = null;
		return this;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#rotate(float)
	 */
	@Override
	public Line rotate(float angle) {
		return rotate(coordinates[0], angle);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#rotate(processing.core.PVector,
	 * float)
	 */
	@Override
	public Line rotate(PVector rotationCenter, float angle) {
		PVector center = rotationCenter;
		for (int i = 0; i < coordinates.length; i++) {
			PVector p = coordinates[i];
			float a = angle + PApplet.atan2(p.y - center.y, p.x - center.x);
			float d = center.dist(p);
			p.x = center.x + PApplet.cos(a) * d;
			p.y = center.y + PApplet.sin(a) * d;
		}

		minX = null;
		boundingBox = null;
		return this;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#scale(float)
	 */
	@Override
	public Line scale(float scale) {
		return scale(coordinates[0], scale);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#scale(processing.core.PVector,
	 * float)
	 */
	@Override
	public Line scale(PVector scaleCenter, float scale) {
		if (RMath.abs(scale) > 0.01) {
			// there shouldn't happen any shape deformation (i.e. angles should
			// not change but with and height of shape). To achieve this
			// the shape is rotate to 0 and the scaling is done
			// afterwards the original rotation is reseted
			PVector center = scaleCenter;
			float rotation = this.getRotation();
			if (rotation != 0) {
				this.setRotation(0);
			}

			for (int i = 0; i < coordinates.length; i++) {
				PVector p = coordinates[i];
				float a = PApplet.atan2(p.y - center.y, p.x - center.x);
				float dis = center.dist(p);
				float d = dis * scale;
				p.x = center.x + PApplet.cos(a) * d;
				p.y = center.y + PApplet.sin(a) * d;
			}

			// bounds needs to be re-calculated
			minX = null;
			boundingBox = null;
			if (rotation != 0) {
				this.setRotation(rotation);
			}

			minX = null;
			boundingBox = null;
		}

		return this;
	}

	/**
	 * Forces to calculate the bounds of this shape and store them. The bounds
	 * can be accessed by getBoundingBox().
	 */
	public void computeMinMax() {
		float[] vals = RMath.range(coordinates);
		minX = vals[0];
		maxX = vals[2];
		minY = vals[1];
		maxY = vals[3];
	}

	// Static

	/**
	 * Returns a normal vector for that is described by the given vectors.
	 * 
	 * @param p
	 *            One location (p != o).
	 * @param o
	 *            Another location (p != o).
	 * 
	 * @return The normal vector.
	 */
	static public PVector getNormal(PVector p, PVector o) {

		return new PVector(o.y - p.y, p.x - o.x);
	}

	/**
	 * Creates lines from the given point set. The first line will have its
	 * start at points[0] and its end at points[1]. The second line will have
	 * its start at points[1] and its end at points[2] and so on.
	 * 
	 * @param parent
	 *            The PApplet object.
	 * @param points
	 *            Some coordinates (points.length >= 2).
	 * @return A set of lines.
	 */
	static public Line[] toLines(PApplet parent, PVector[] points) {
		Line[] lines = new Line[points.length - 1];

		for (int i = 1; i < points.length; i++) {
			lines[i - 1] = new Line(parent, points[i - 1], points[i]);
		}

		return lines;
	}

	/**
	 * Returns the location of an intersection of two lines if they have an
	 * intersection. Returns null otherwise.
	 * 
	 * @param base
	 *            One line.
	 * @param other
	 *            Another line.
	 * @return The location of intersection or null.
	 */
	public static PVector intersection(Line base, Line other) {
		return Line.intersection(base, other, false);
	}

	/**
	 * Returns the location of an intersection of two lines if they have an
	 * intersection. Returns null otherwise.
	 * 
	 * @param base
	 *            One line.
	 * @param other
	 *            Another line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then still null will be returned).
	 *            Otherwise all found intersections will be returned.
	 * @return The location of intersection or null.
	 */
	public static PVector intersection(Line base, Line other, boolean ignoreStartEnd) {
		Line line1 = base;
		PVector start1 = line1.getStart();
		PVector dir1 = line1.toRotationVector();
		float l1 = line1.getLength();

		Line line2 = other;
		PVector start2 = line2.getStart();
		PVector dir2 = line2.toRotationVector();
		float l2 = line2.getLength();

		double skalar2 = ((double) start2.y * dir1.x - start1.y * dir1.x - dir1.y * start2.x + start1.x * dir1.y)
				/ (dir2.x * dir1.y - dir2.y * dir1.x);
		double skalar1 = ((double) start2.x + skalar2 * dir2.x - start1.x) / dir1.x;
		 

		// identical lines, maybe with different lengths
		if (Double.isInfinite(skalar2) || Double.isInfinite(skalar1)) {

			
			float x1 = 0;
			float y1 = 0;

			float leftx1 = RMath.min(line1.getStart().x, line1.getEnd().x);
			float lefty1 = leftx1 == line1.getStart().x ? line1.getStart().y : line1.getEnd().y;
			float leftx2 = RMath.min(line2.getStart().x, line2.getEnd().x);
			float lefty2 = leftx2 == line2.getStart().x ? line2.getStart().y : line2.getEnd().y;

			if (leftx1 > leftx2 || leftx1 == leftx2) {
				x1 = leftx1;
				y1 = lefty1;
			} else if (leftx1 < leftx2) {
				x1 = leftx2;
				y1 = lefty2;
			} else {
				float topy1 = RMath.min(line1.getStart().y, line1.getEnd().y);
				float topy2 = RMath.min(line2.getStart().y, line2.getEnd().y);
				float topx1 = topy1 == line1.getStart().y ? line1.getStart().x : line1.getEnd().x;
				float topx2 = topy2 == line2.getStart().y ? line2.getStart().x : line2.getEnd().x;

				if (topy1 > topy2 || topy1 == topy2) {
					x1 = topx1;
					y1 = topy1;
				} else if (topy1 < topy2) {
					x1 = topx2;
					y1 = topy2;
				} else {
					// identical top point
					x1 = topx1;
					y1 = topy1;
				}
			}

			return new PVector(x1, y1);
		} 
		
		// parallel lines
		if (Double.isNaN(skalar2) || Double.isNaN(skalar1)) {
			
			return null;
		} 
		
		if (skalar1 < 0 || skalar2 < 0) {
			// cross would be "befor" start
			return null;
		}

		PVector crossed = dir1;
		crossed.mult((float) skalar1);
		crossed.add(start1);

		// Intersection happens at the end or start of one of the lines
		if (ignoreStartEnd && (crossed.dist(start1) < 1 || crossed.dist(start2) < 1 || crossed.dist(line1.getEnd()) < 1
				|| crossed.dist(line2.getEnd()) < 1)) {
			return null;
		} else if (crossed.dist(start1) > l1 || crossed.dist(start2) > l2) {
			// no intersection -> cross would be "after" end
			return null;
		} else {

			// intersection at point crossed
			return crossed;
		}
	}

	/**
	 * Tests if two lines have an intersection.
	 * 
	 * @param base
	 *            One line.
	 * @param other
	 *            Another line.
	 * @return True, when the two lines intersect.
	 */
	static public boolean hasIntersection(Line base, Line other) {
		return Line.hasIntersection(base, other, false);
	}

	/**
	 * Tests if two lines have an intersection.
	 * 
	 * @param base
	 *            One line.
	 * @param other
	 *            Another line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then still false will be returned).
	 * @return True, when the two lines intersect.
	 */
	static public boolean hasIntersection(Line base, Line other, boolean ignoreStartEnd) {
		PVector sec = Line.intersection(base, other, ignoreStartEnd);

		if (sec == null) {
			return false;
		} else {
			return true;
		}
	}

	/**
	 * Removes lines from the given set of lines if they intersect with other
	 * lines of the list. For each intersection the line which was added later
	 * to the list of lines (i.e. has a higher index) will be removed.
	 * 
	 * @param lines
	 *            A set of lines.
	 */
	static public void removeIntersectingLines(ArrayList<Line> lines) {
		Line.removeIntersectingLines(lines, false);
	}

	/**
	 * Removes lines from the given set of lines if they intersect with other
	 * lines of the list. For each intersection the line which was added later
	 * to the list of lines (i.e. has a higher index) will be removed.
	 * 
	 * @param lines
	 *            A set of lines.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then the lines will not be removed).
	 */
	static public void removeIntersectingLines(ArrayList<Line> lines, boolean ignoreStartEnd) {
		for (int i = 0; i < lines.size(); i++) {
			for (int j = i + 1; j < lines.size(); j++) {
				PVector cross = Line.intersection(lines.get(i), lines.get(j), ignoreStartEnd);

				if (cross != null) {
					lines.remove(lines.get(j));
					j--;
				}
			}
		}
	}

	/**
	 * Removes lines from the given set of lines if they intersect with other
	 * lines of the list. The removal of the lines is done hierarchical: In each
	 * iteration the line with the most intersections is found and that line is
	 * removed. This means in each iteration just one intersection is removed.
	 * This makes the algorithm quite slow (but precise). Use
	 * removeIntersectingLines() for faster (but less precise) removal.
	 * 
	 * @param lines
	 *            A set of lines.
	 */
	static public void removeIntersectingLinesHierarchical(ArrayList<Line> lines) {
		Line.removeIntersectingLinesHierarchical(lines, false);
	}

	/**
	 * Removes lines from the given set of lines if they intersect with other
	 * lines of the list. The removal of the lines is done hierarchical: In each
	 * iteration the line with the most intersections is found and that line is
	 * removed. This means in each iteration just one intersection is removed.
	 * This makes the algorithm quite slow (but precise). Use
	 * removeIntersectingLines() for faster (but less precise) removal.
	 * 
	 * @param lines
	 *            A set of lines.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of any line will be ignored (i.e. if the intersection
	 *            happens at start / end then the lines will not be removed).
	 */
	static public void removeIntersectingLinesHierarchical(ArrayList<Line> lines, boolean ignoreStartEnd) {
		boolean intersectionFound = true;

		while (intersectionFound) {
			intersectionFound = false;
			int[] intersections = new int[lines.size()];
			for (int i = 0; i < lines.size(); i++) {
				intersections[i] = 0;
				for (int k = 0; k < lines.size(); k++) {
					if (i == k) {
						continue;
					}
					if (Line.hasIntersection(lines.get(i), lines.get(k), ignoreStartEnd)) {
						intersections[i]++;
						intersectionFound = true;
					}
				}
			}

			if (intersectionFound) {
				// find the ones with the highest # of intersections
				int maxID = 0;
				int maxIntersec = 0;
				ArrayList<Integer> indexesWithSameNumberOfIntersections = new ArrayList<Integer>();

				for (int i = 0; i < intersections.length; i++) {

					if (intersections[i] > maxIntersec) {
						indexesWithSameNumberOfIntersections.clear();
						maxID = i;
						maxIntersec = intersections[i];
						indexesWithSameNumberOfIntersections.add(i);
					} else if (intersections[i] == maxIntersec) {
						indexesWithSameNumberOfIntersections.add(i);
					}
				}

				// if there is more than one intersection with the highest # of
				// intersection, then remove the middle line. Otherwise is it
				// just one intersection with that number and that will the one
				// to be removed.
				if (indexesWithSameNumberOfIntersections.size() > 1) {
					int index = indexesWithSameNumberOfIntersections
							.get(indexesWithSameNumberOfIntersections.size() / 2);

					lines.remove(index);

				} else {
					lines.remove(maxID);
				}
			}
		}
	}

	// Drawing

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#draw()
	 */
	public Line draw() {
		parent.line(getStart().x, getStart().y, getEnd().x, getEnd().y);
		return this;
	}

	// Conversion

	/**
	 * Creates a vector that points in the same direction like this line.
	 * 
	 * @return The vector with the same angle like this line.
	 */
	public PVector toRotationVector() {
		float angle = getRotation();
		return new PVector(PApplet.cos(angle), PApplet.sin(angle));
	}

}
