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 curves (Catmull-Rom Curves). This class
 * uses Processing's implementation for curves and uses always Processing's
 * default values for curveTightness=0 and curveDetail=20.
 * 
 * @author Diana Lange
 */
public class Curve implements RShape {

	/**
	 * Control point which is needed to draw a curve between coordinates[0] and
	 * coordinates[1]. Catmull-Rom Curves need to know how the curve evolves and
	 * how the previous steps have been to calculate the form of the curve.
	 */
	private PVector controlZero;

	/**
	 * Control point which is needed to draw a curve between coordinates[last -
	 * 1] and coordinates[last]. Catmull-Rom Curves need to know how the curve
	 * evolves and how the previous steps have been to calculate the form of the
	 * curve.
	 */
	private PVector controlLast;

	/**
	 * The coordinates that discribe this curve.
	 */
	private PVector[] coordinates;

	/**
	 * Processing's matrix for curves with preset for curveTightness = 0. For
	 * this class the curveTightness will always be 0 so this matrix never needs
	 * to change.
	 */
	private static float[][] curveBaseMatrix = { { -0.5f, 1.5f, -1.5f, 0.5f }, { 1f, -2.5f, 2f, -0.5f },
			{ -0.5f, 0, 0.5f, 0 }, { 0f, 1f, 0f, 0f } };

	/**
	 * 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;

	/**
	 * The true length of the curve.
	 */
	private Float arcLength = null;

	/**
	 * The arclength for each curve segment.
	 */
	private ArrayList<SegmentRange> ranges;

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

	/**
	 * Builds an empty shape. The coordinates have to be set manually.
	 * 
	 * @param parent
	 *            The PApplet object.
	 */
	public Curve(PApplet parent) {

		this.parent = parent;
		this.ranges = new ArrayList<SegmentRange>();
	}

	/**
	 * Builds an curve that follows the given coordinates.
	 * 
	 * @param parent
	 *            The PApplet object.
	 * @param coordinates
	 *            The coordinates of this curve.
	 */
	public Curve(PApplet parent, PVector[] coordinates) {
		if (coordinates.length < 3) {
			System.err.println("You can't build a curve with less than 3 points");
		}

		this.parent = parent;
		this.coordinates = coordinates;
		this.computeControlZero();
		this.computeControlLast();
		this.ranges = new ArrayList<SegmentRange>();
	}

	// Getters

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

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

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

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

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

	/*
	 * (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;
	}

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

	/*
	 * (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 Curve copy() {
		Curve copyCurve = new Curve(parent);
		copyCurve.coordinates = new PVector[this.coordinates.length];
		for (int i = 0; i < this.coordinates.length; i++) {
			copyCurve.coordinates[i] = new PVector(this.coordinates[i].x, this.coordinates[i].y);
		}

		copyCurve.controlZero = new PVector(this.controlZero.x, this.controlZero.y);
		copyCurve.controlLast = new PVector(this.controlLast.x, this.controlLast.y);

		return copyCurve;
	}

	/**
	 * Returns the true length of this curve.
	 * 
	 * @return The length of the curve.
	 */
	public Float getArcLength() {
		if (arcLength == null) {
			computeArcLength();
		}

		return arcLength;
	}

	// Setter

	/**
	 * Sets one of the control points, which is not seen, but used to describe
	 * the start or end of the curve.
	 * 
	 * @param which
	 *            -1 for first control point (Control point which is needed to
	 *            draw a curve between coordinates[0] and coordinates[1]) or 1
	 *            for last control point (Control point which is needed to draw
	 *            a curve between coordinates[last-1] and coordinates[last]).
	 * @param p
	 *            The control point.
	 * @return The current curve.
	 */
	public Curve setControlPoint(int which, PVector p) {
		if (which < 0) {
			controlZero = p;
		} else {
			controlLast = p;
		}

		return this;
	}

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

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

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * net.returnvoid.graphics.shape.RShape#setRotation(processing.core.PVector,
	 * float)
	 */
	@Override
	public Curve setRotation(PVector rotationCenter, float angle) {
		return rotate(rotationCenter, angle - getRotation());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setX(float)
	 */
	@Override
	public Curve setX(float x) {
		return translate(x - getX(), 0);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setY(float)
	 */
	@Override
	public Curve setY(float y) {
		return translate(0, y - getY());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#setLocation(float, float)
	 */
	@Override
	public Curve setLocation(float x, float y) {
		return translate(x - getX(), y - getY());
	}

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

		return setLength(getStart(), newLength);

	}

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

		if (newLength > this.size() * 2 && RMath.abs(this.getLength() - newLength) > 0.5) {
			float scale = newLength / getLength();

			return this.scale(center, scale);
		} else {
			return this;
		}

	}

	// Calculus

	/**
	 * Returns the location of an intersection a curve segment with a line if
	 * they have an intersection. Returns null otherwise. Uses just a cheap
	 * approximation (line segment instead of curve segment).
	 * 
	 * @param curveSeg
	 *            A line that represents a curve segment (line between two
	 *            points of the curve).
	 * @param other
	 *            One line.
	 * 
	 * @return The location of intersection or null.
	 */
	public PVector intersection(Line curveSeg, Line other) {
		return intersection(curveSeg, other, false);
	}

	/**
	 * Returns the location of an intersection a curve segment with a line if
	 * they have an intersection. Returns null otherwise. Uses just a cheap
	 * approximation (line segment instead of curve segment).
	 * 
	 * @param curveSeg
	 *            A line that represents a curve segment (line between two
	 *            points of the curve).
	 * @param other
	 *            One line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of the given 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 curveSeg, Line other, boolean ignoreStartEnd) {
		Line line1 = curveSeg;
		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();

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

		// parallel lines
		if (Float.isInfinite(skalar2) || Float.isInfinite(skalar1)) {
			return null;
		}

		// identical lines, maybe with different lengths
		if (Float.isNaN(skalar2) || Float.isNaN(skalar1)) {
			line1.computeMinMax();
			line2.computeMinMax();

			Rect r1 = line1.getBoundingBox();
			Rect r2 = line2.getBoundingBox();

			float x1 = RMath.max(r1.getStart().x, r2.getStart().x);
			float y1 = RMath.max(r1.getStart().y, r2.getStart().y);

			return new PVector(x1, y1);
		}

		// cross would be "befor" start
		if (skalar1 < 0 || skalar2 < 0) {

			return null;
		}

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

		// Intersection happens at the end or start of one of the lines
		if (ignoreStartEnd && (crossed.dist(start2) < l2 * 0.25 || crossed.dist(line2.getEnd()) < l2 * 0.25)) {
			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 a curve segment has a intersection with the given line. Uses
	 * just a cheap approximation (line segment instead of curve segment).
	 * 
	 * @param curveSeg
	 *            A line that represents a curve segment (line between two
	 *            points of the curve).
	 * @param other
	 *            One line.
	 * @return True, when the two lines intersect.
	 */
	public boolean hasIntersection(Line curveSeg, Line other) {
		return hasIntersection(curveSeg, other, false);
	}

	/**
	 * Tests if a curve segment has a intersection with the given line. Uses
	 * just a cheap approximation (line segment instead of curve segment).
	 * 
	 * @param curveSeg
	 *            A line that represents a curve segment (line between two
	 *            points of the curve).
	 * @param other
	 *            One line.
	 * @param ignoreStartEnd
	 *            If true, intersections that happen directly at the start or
	 *            the end of the given 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 True, when the two lines intersect.
	 */
	public boolean hasIntersection(Line curveSeg, Line other, boolean ignoreStartEnd) {
		PVector sec = intersection(curveSeg, other, ignoreStartEnd);

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

	/**
	 * Removes all lines from the given set of lines that intersect with this
	 * shape. Uses just a cheap approximation (line segment instead of curve
	 * segment).
	 * 
	 * @param toRemove
	 *            A set of lines.
	 */
	public void removeIntersectingLines(ArrayList<Line> toRemove) {
		removeIntersectingLines(toRemove, false);
	}

	/**
	 * Removes all lines from the given set of lines that intersect with this
	 * shape. Uses just a cheap approximation (line segment instead of curve
	 * segment).
	 * 
	 * @param toRemove
	 *            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 line will not be removed).
	 */
	public void removeIntersectingLines(ArrayList<Line> toRemove, boolean ignoreStartEnd) {

		for (int i = 0; i < this.size() - 1; i++) {
			Line line = new Line(parent, get(i), get(i + 1));
			for (int j = 0; j < toRemove.size(); j++) {
				if (hasIntersection(line, toRemove.get(j), ignoreStartEnd)) {
					toRemove.remove(j);
					j--;
				}
			}
		}
	}

	/**
	 * Returns the four coordinates that are needed to describe a curve segment.
	 * 
	 * @param i
	 *            The index of the coordinate that is the start of the curve
	 *            segment.
	 * @return The coordinates for the curve segment.
	 */
	private float[][] coordsByI(Integer i) {
		if (i == coordinates.length - 1) {
			return null;
		}

		// {{x1-x4}{y1-y4}}
		float[][] coords = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };

		if (i == 0) {
			coords[0][0] = controlZero.x;
			coords[1][0] = controlZero.y;
			coords[0][1] = coordinates[i].x;
			coords[1][1] = coordinates[i].y;
			coords[0][2] = coordinates[i + 1].x;
			coords[1][2] = coordinates[i + 1].y;
			coords[0][3] = coordinates[i + 2].x;
			coords[1][3] = coordinates[i + 2].y;
		} else if (i == coordinates.length - 2) {
			coords[0][0] = coordinates[i - 1].x;
			coords[1][0] = coordinates[i - 1].y;
			coords[0][1] = coordinates[i].x;
			coords[1][1] = coordinates[i].y;
			coords[0][2] = coordinates[i + 1].x;
			coords[1][2] = coordinates[i + 1].y;
			coords[0][3] = controlLast.x;
			coords[1][3] = controlLast.y;
		} else if (i < coordinates.length - 1) {
			coords[0][0] = coordinates[i - 1].x;
			coords[1][0] = coordinates[i - 1].y;
			coords[0][1] = coordinates[i].x;
			coords[1][1] = coordinates[i].y;
			coords[0][2] = coordinates[i + 1].x;
			coords[1][2] = coordinates[i + 1].y;
			coords[0][3] = coordinates[i + 2].x;
			coords[1][3] = coordinates[i + 2].y;
		}
		return coords;
	}

	/**
	 * Returns the normal information for a given location on the curve.
	 * 
	 * @param tplusi
	 *            A parameter that describes the position on the curve. i is the
	 *            index of the coordinate, t is the parameter that describes how
	 *            near the returned normal is to that coordinate. If t is 0 the
	 *            normal will be directly at the coordinate, if t is 1 the
	 *            normal will be directly at the following coordinate. For t=0.5
	 *            the normal will be in the middle of the coordinate and the
	 *            following coordinate. t and i should be summed for this
	 *            parameter, e.g. for the normal which is in the middle (t=0.5)
	 *            of coordinate[1] (i=1) and coordinate[2] tplusi should be
	 *            1+0.5=0.5
	 * @return The information for the normal in form of: [normalX, normalY,
	 *         normalAngle].
	 */
	public float[] getNormal(float tplusi) {

		tplusi = RMath.constrain(tplusi, 0, coordinates.length - 1);

		int i = (int) tplusi;
		float t = tplusi - i;

		float[][] coords = coordsByI(i);

		if (coords == null) {
			PVector normalVec = Line.getNormal(getEnd(), this.controlLast);
			return new float[] { getEnd().x, getEnd().y, normalVec.heading() };
		} else {

			PVector point = curvePoint(coords, t);
			float tangent = curveTangent(coords, t);

			return new float[] { point.x, point.y, -PApplet.PI / 2 + tangent };
		}
	}

	/**
	 * Calculates the tangent in a point of a curve segment.
	 * 
	 * @param vals
	 *            The four coordinates of a curve segment (use coordsByI()).
	 * @param t
	 *            The position on the curve segment.
	 * @return The angle of the tangent in the position.
	 */
	private float curveTangent(float[][] vals, float t) {

		// source: Processing
		float tt3 = t * t * 3;
		float t2 = t * 2;

		float[][] cb = curveBaseMatrix;
		float[] sums = { (tt3 * cb[0][0] + t2 * cb[1][0] + cb[2][0]), (tt3 * cb[0][1] + t2 * cb[1][1] + cb[2][1]),
				(tt3 * cb[0][2] + t2 * cb[1][2] + cb[2][2]), (tt3 * cb[0][3] + t2 * cb[1][3] + cb[2][3]) };

		float tx = 0;
		float ty = 0;

		for (int i = 0; i < sums.length; i++) {
			tx += vals[0][i] * sums[i];
			ty += vals[1][i] * sums[i];
		}

		return PApplet.atan2(ty, tx);
	}

	/**
	 * Calculates the tangent in a point of the curve.
	 * 
	 * @param tplusi
	 *            A parameter that describes the position on the curve and the
	 *            curve segment. i is the index of the coordinate, t is the
	 *            parameter that describes how near the returned normal is to
	 *            that coordinate. If t is 0 the normal will be directly at the
	 *            coordinate, if t is 1 the normal will be directly at the
	 *            following coordinate. For t=0.5 the normal will be in the
	 *            middle of the coordinate and the following coordinate. t and i
	 *            should be summed for this parameter, e.g. for the normal which
	 *            is in the middle (t=0.5) of coordinate[1] (i=1) and
	 *            coordinate[2] tplusi should be 1+0.5=0.5.
	 * @return The angle of the tangent in the position.
	 */
	public float curveTangent(float tplusi) {
		tplusi = RMath.constrain(tplusi, 0, coordinates.length - 1);

		int i = (int) tplusi;
		float t = tplusi - i;

		float[][] coords = coordsByI(i);

		if (coords == null) {
			Line line = new Line(parent, this.getEnd(), this.controlLast);
			return line.getRotation();
		} else {
			return curveTangent(coords, t);
		}
	}

	/**
	 * Calculates a point on the curve.
	 * 
	 * @param tplusi
	 *            A parameter that describes the position on the curve and the
	 *            curve segment. i is the index of the coordinate, t is the
	 *            parameter that describes how near the returned normal is to
	 *            that coordinate. If t is 0 the normal will be directly at the
	 *            coordinate, if t is 1 the normal will be directly at the
	 *            following coordinate. For t=0.5 the normal will be in the
	 *            middle of the coordinate and the following coordinate. t and i
	 *            should be summed for this parameter, e.g. for the normal which
	 *            is in the middle (t=0.5) of coordinate[1] (i=1) and
	 *            coordinate[2] tplusi should be 1+0.5=0.5
	 * @return The point on the curve.
	 */
	public PVector curvePoint(float tplusi) {
		tplusi = RMath.constrain(tplusi, 0, coordinates.length - 1);

		int i = (int) tplusi;
		float t = tplusi - i;

		float[][] coords = coordsByI(i);

		if (coords == null) {
			return getEnd().copy();
		} else {
			return curvePoint(coords, t);
		}
	}

	/**
	 * Calculates a point on a curve segment.
	 * 
	 * @param vals
	 *            The four coordinates of a curve segment (use coordsByI()).
	 * @param t
	 *            The position on the curve segment.
	 * @return The point on the curve.
	 */
	private PVector curvePoint(float[][] vals, float t) {

		// source: Processing
		float tt = t * t;
		float ttt = t * tt;

		float[][] cb = curveBaseMatrix;
		float[] sums = { (ttt * cb[0][0] + tt * cb[1][0] + t * cb[2][0] + cb[3][0]),
				(ttt * cb[0][1] + tt * cb[1][1] + t * cb[2][1] + cb[3][1]),
				(ttt * cb[0][2] + tt * cb[1][2] + t * cb[2][2] + cb[3][2]),
				(ttt * cb[0][3] + tt * cb[1][3] + t * cb[2][3] + cb[3][3]) };

		float x = 0;
		float y = 0;

		for (int i = 0; i < sums.length; i++) {
			x += vals[0][i] * sums[i];
			y += vals[1][i] * sums[i];
		}

		return new PVector(x, y);
	}

	/**
	 * Calculates the arc length of this curve (approx.).
	 */
	private void computeArcLength() {
		ranges.clear();

		float summedLength = 0;

		ArrayList<PVector> controlPoints = new ArrayList<PVector>();

		// 20 is Processing's preset for curveDetail -> curves
		// get drawn with small lines -> curveDetail defines
		// the length of these lines -> so this should give
		// the same line segments as Processing produces

		int steps = 30;

		/*
		 * int steps = 20; float x0 = 0; float y0 = 0;
		 * 
		 * float xplot1; float xplot2; float xplot3;
		 * 
		 * float yplot1; float yplot2; float yplot3;
		 */
		for (int i = 0; i < size() - 1; i++) {

			controlPoints.clear();

			for (int j = 0; j < steps; j++) {
				float t = i + (float) j / steps;

				controlPoints.add(this.curvePoint(t));
			}

			/**
			 * Curve draw matrix:
			 * 
			 * <pre>
			 * -0,5000  1,5000 -1,5000  0,5000
			 * 1,0000 -2,5000  2,0000 -0,5000
			 * -0,5000  0,0000  0,5000  0,0000
			 * 0,0000  1,0000  0,0000  0,0000
			 * 
			 * </pre>
			 */

			/*
			 * TODO: arc length calculation doesn't work yet correctly
			 * float[][] coords = this.coordsByI(i);
			 * 
			 * x0 = this.get(i).x; y0 = this.get(i).y;
			 * 
			 * xplot1 = 1.0f * coords[0][0] + -2.5f * coords[0][1] + 2.0f *
			 * coords[0][2] + -0.5f * coords[0][3]; xplot2 = -0.5f *
			 * coords[0][0] + 0.0f * coords[0][1] + 0.5f * coords[0][2] + 0.0f *
			 * coords[0][3]; xplot3 = 0.0f * coords[0][0] + 1.0f * coords[0][1]
			 * + 0.0f * coords[0][2] + 0.0f * coords[0][3];
			 * 
			 * yplot1 = 1.0f * coords[1][0] + -2.5f * coords[1][1] + 2.0f *
			 * coords[1][2] + -0.5f * coords[1][3]; yplot2 = -0.5f *
			 * coords[1][0] + 0.0f * coords[1][1] + 0.5f * coords[1][2] + 0.0f *
			 * coords[1][3]; yplot3 = 0.0f * coords[1][0] + 1.0f * coords[1][1]
			 * + 0.0f * coords[1][2] + 0.0f * coords[1][3];
			 * 
			 * 
			 * 
			 * for (int j = 0; j < steps; j++) { x0 += xplot1; xplot1 += xplot2;
			 * xplot2 += xplot3; y0 += yplot1; yplot1 += yplot2; yplot2 +=
			 * yplot3;
			 * 
			 * controlPoints.add(new PVector(x0, y0)); }
			 */

			// calculate the arc length of each curve segment
			LineSegments seg = new LineSegments(parent, controlPoints);
			float segmentLength = seg.getArcLength();

			// sum it up to calculate the arc length of the whole curve
			summedLength += segmentLength;

			// save this curve segments arc length and keep track of where each
			// curve segment starts in the context of the whole curve
			ranges.add(new SegmentRange(i, summedLength - segmentLength, summedLength));
		}

		this.arcLength = summedLength;
	}

	/**
	 * Maps a given arc length factor [0, getArcLength()] to a tplusi. tplusi is
	 * a parameter that describes the position on the curve and the curve
	 * segment. i is the index of the coordinate, t is the parameter that
	 * describes how near the returned normal is to that coordinate. If t is 0
	 * the normal will be directly at the coordinate, if t is 1 the normal will
	 * be directly at the following coordinate. For t=0.5 the normal will be in
	 * the middle of the coordinate and the following coordinate. t and i should
	 * be summed for this parameter, e.g. for the normal which is in the middle
	 * (t=0.5) of coordinate[1] (i=1) and coordinate[2] tplusi should be
	 * 1+0.5=0.5.
	 * 
	 * @param arclength
	 *            The arclength [0, getArcLength()].
	 * @return The tplusi factor.
	 */
	public float arcLengthToTPlusI(float arclength) {

		if (arcLength == null) {
			computeArcLength();
		}

		float t = 0;
		int index = 0;

		boolean found = false;
		for (int i = 0; i < ranges.size(); i++) {
			if (arclength >= ranges.get(i).beginRange && arclength <= ranges.get(i).endRange) {
				t = ranges.get(i).getT(arclength);
				index = ranges.get(i).index;
				found = true;
				break;
			}
		}

		if (!found) {
			index = coordinates.length - 1;
			t = 1;
		}

		return index + t;
	}

	/**
	 * 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];
	}

	/**
	 * Computes the first control point. The control point is needed to draw a
	 * curve between coordinates[0] and coordinates[1]. Catmull-Rom Curves need
	 * to know how the curve evolves and how the previous steps have been to
	 * calculate the form of the curve.
	 */
	private void computeControlZero() {
		float a = PApplet.atan2(getStart().y - coordinates[1].y, getStart().x - coordinates[1].x);
		float s = getStart().dist(coordinates[1]);
		this.controlZero = RMath.polarToCartesian(getStart(), a, s);
	}

	/**
	 * Computes the last control point. The control point is needed to draw a
	 * curve between coordinates[last-1] and coordinates[last]. Catmull-Rom
	 * Curves need to know how the curve evolves and how the previous steps have
	 * been to calculate the form of the curve.
	 */
	private void computeControlLast() {
		float a = PApplet.atan2(getEnd().y - coordinates[coordinates.length - 2].y,
				getEnd().x - coordinates[coordinates.length - 2].x);
		float s = coordinates[coordinates.length - 2].dist(getEnd());
		this.controlLast = RMath.polarToCartesian(getEnd(), a, s);
	}

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

		this.controlLast.x += x;
		this.controlLast.y += y;
		this.controlZero.x += x;
		this.controlZero.y += y;

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

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

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

		PVector center = rotationCenter;

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

		a = angle + PApplet.atan2(controlLast.y - center.y, controlLast.x - center.x);
		d = center.dist(controlLast);
		this.controlLast.x = center.x + PApplet.cos(a) * d;
		this.controlLast.y = center.y + PApplet.sin(a) * d;

		a = angle + PApplet.atan2(controlZero.y - center.y, controlZero.x - center.x);
		d = center.dist(controlZero);
		this.controlZero.x = center.x + PApplet.cos(a) * d;
		this.controlZero.y = center.y + PApplet.sin(a) * d;

		// this.computeControlLast();
		// this.computeControlZero();
		minX = null;
		boundingBox = null;
		return this;
	}

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

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#scale(processing.core.PVector,
	 * float)
	 */
	@Override
	public Curve scale(PVector scaleCenter, float scale) {
		return scale(scaleCenter, scale, scale);
	}

	/**
	 * Scales the shape by the given scaling factors. For scaling factor < 1 the
	 * shape will shrink. For scaling factors > 1 the shape will expand. The
	 * scaling center will be the given location <b>scaleCenter</b>.
	 * 
	 * @param scaleCenter
	 *            The scaling center.
	 * @param scaleX
	 *            The horizontal scaling.
	 * @param scaleY
	 *            The vertical scaling.
	 * @return The current shape.
	 */
	public Curve scale(PVector scaleCenter, float scaleX, float scaleY) {
		if (RMath.abs(scaleX) > 0.01 && RMath.abs(scaleY) > 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);
			}

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

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

			this.computeControlZero();
			this.computeControlLast();
		}

		return this;
	}

	// Drawing

	/*
	 * (non-Javadoc)
	 * 
	 * @see net.returnvoid.graphics.shape.RShape#draw()
	 */
	@Override
	public Curve draw() {
		parent.beginShape();
		parent.curveVertex(controlZero.x, controlZero.y);
		for (int i = 0; i < coordinates.length; i++) {
			parent.curveVertex(coordinates[i].x, coordinates[i].y);
			// parent.ellipse(locations[i].x, locations[i].y, 10, 10);
		}
		parent.curveVertex(controlLast.x, controlLast.y);
		parent.endShape();

		return this;
	}

	// Conversion

	/**
	 * Smoothens the curve: All coordinates of the returned curve will have a
	 * equal distance to each other. The returned curve will consists of a equal
	 * amount of coordinates as the input curve.
	 * 
	 * @return The new smoothend curve.
	 */
	public Curve toSmoothedCurve() {
		return this.toLineSegments(size()).getCurve();
	}

	/**
	 * Smoothens the curve: All coordinates of the returned curve will have a
	 * equal distance to each other. The returned curve will consists of
	 * <b>details</b> coordinates (>= 3).
	 * 
	 * @param details
	 *            The number of coordinates for the returned curve.
	 * 
	 * @return The new smoothend curve.
	 */
	public Curve toSmoothedCurve(int details) {
		return this.toLineSegments(details).getCurve();
	}

	/**
	 * Smoothens the curve: All coordinates of the returned curve will have a
	 * equal distance to each other. The returned curve will consists of less or
	 * more coordinates than the input curve depending on the factor
	 * <b>detailScale</b>.
	 * 
	 * @param detailScale
	 *            A factor that describes the number of coordinates for the
	 *            returned smoothend curve. For detailScale < 1 the new curve
	 *            will have less coordinates than the input, for detailScale > 1
	 *            the curve will have more coordinates. <b>detailScale</b>
	 *            should be greater than zero.
	 * 
	 * @return The new smoothend curve.
	 */
	public Curve toSmoothedCurve(float detailScale) {
		return this.toLineSegments(detailScale).getCurve();
	}

	/**
	 * Converts this shape to a LineSegments. Does a shallow copy of the
	 * coordinates of this shape.
	 * 
	 * @return The LineSegments shape.
	 */
	public LineSegments getLineSegments() {
		return new LineSegments(parent, this.coordinates);
	}

	/**
	 * Converts this shape to a LineSegments. Does a real copy of the
	 * coordinates of this shape.
	 * 
	 * @return The LineSegments shape.
	 */
	public LineSegments toLineSegments() {
		return new LineSegments(parent, this.copy().coordinates);
	}

	/**
	 * Converts this shape to a LineSegments and optimizes the coordinates. All
	 * coordinates of the returned LineSegments will have a equal distance to
	 * each other. The returned LineSegments will consists of less or more
	 * coordinates than the input curve depending on the factor
	 * <b>detailScale</b>.
	 * 
	 * @param detailScale
	 *            A factor that describes the number of coordinates for the
	 *            returned LineSegments. For detailScale < 1 the new
	 *            LineSegments will have less coordinates than the input curve,
	 *            for detailScale > 1 the LineSegments will have more
	 *            coordinates. <b>detailScale</b> should be greater than zero.
	 * @return The LineSegments shape.
	 */
	public LineSegments toLineSegments(float detailScale) {
		return toLineSegments((int) (this.size() * detailScale));
	}

	/**
	 * Converts this shape to a LineSegments and optimizes the coordinates. All
	 * coordinates of the returned LineSegments will have a equal distance to
	 * each other. The returned LineSegments will consists of <b>details</b>
	 * coordinates.
	 * 
	 * @param details
	 *            The number of coordinates for the returned LineSegments (>=
	 *            2).
	 * @return The LineSegments shape.
	 */
	public LineSegments toLineSegments(int details) {

		// System.out.println("curve - old size: " + this.size() + ", new: " +
		// details);

		ArrayList<PVector> controlPoints = new ArrayList<PVector>();

		if (details < 3) {
			details = 3;
		}

		for (int i = 0; i < details; i++) {
			float arcLength = PApplet.map(i, 0, details - 1, 0, this.getArcLength());
			float t = this.arcLengthToTPlusI(arcLength);

			controlPoints.add(curvePoint(t));
		}

		if (getEnd().dist(controlPoints.get(controlPoints.size() - 1)) > 0.1) {
			controlPoints.add(getEnd().copy());
		}
		return new LineSegments(parent, controlPoints);
	}

	// Inner Classes

	/**
	 * A class to keep track of the arc lengths for each curve segment (needed
	 * for arc length to i+t mappings). Each instance represents a curve segment
	 * and contains the arc length of the curve segment as well as the position
	 * within the whole curve.
	 * 
	 * @author Diana Lange
	 *
	 */
	private class SegmentRange {
		/**
		 * The index of the curve segment.
		 */
		private int index;

		/**
		 * The whole curve has a arc length from the first point to this current
		 * curve segment of 'beginRange'.
		 */
		private float beginRange;

		/**
		 * The whole curve has a arc length from the first point to the end of
		 * this current curve segment of 'endRange'.
		 */
		private float endRange;

		/**
		 * Builds a new SegmentRange.
		 * 
		 * @param index
		 *            The index of the curve segment [0, coordinates.length -
		 *            1].
		 * @param beginRange
		 *            The arc length of the whole curve until this curve
		 *            segment.
		 * @param endRange
		 *            The arc length of the whole curve after this curve
		 *            segment.
		 */
		private SegmentRange(int index, float beginRange, float endRange) {
			this.index = index;
			this.beginRange = beginRange;
			this.endRange = endRange;
		}

		/**
		 * Returns the t factor by the given <b>val</b>.
		 * 
		 * @param val
		 *            A value that should be mapped to t. <b>val</b> should be
		 *            within the range of [beginRange, endRange].
		 * @return The t factor.
		 */
		private float getT(float val) {
			return PApplet.map(val, beginRange, endRange, 0, 1);
		}

		/**
		 * Returns the arc length of this curve segment.
		 * 
		 * @return The arc length.
		 */
		@SuppressWarnings("all")
		private float getArcLength() {
			return endRange - beginRange;
		}
	}

}
