/**
 * $Id: mxCurve.java,v 1.32 2010/07/19 09:07:08 david Exp $
 * Copyright (c) 2009-2010, David Benson, Gaudenz Alder
 */
package com.mxgraph.util;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

public class mxCurve
{
	/**
	 * A collection of arrays of curve points
	 */
	protected Map<String, mxPoint[]> points;

	// Rectangle just completely enclosing branch and label/
	protected double minXBounds = 10000000;

	protected double maxXBounds = 0;

	protected double minYBounds = 10000000;

	protected double maxYBounds = 0;

	/**
	 * An array of arrays of intervals. These intervals define the distance
	 * along the edge (0 to 1) that each point lies
	 */
	protected Map<String, double[]> intervals;

	/**
	 * The curve lengths of the curves
	 */
	protected Map<String, Double> curveLengths;

	/**
	 * Defines the key for the central curve index
	 */
	public static String CORE_CURVE = "Center_curve";

	/**
	 * Defines the key for the label curve index
	 */
	public static String LABEL_CURVE = "Label_curve";;

	/**
	 * Offset of the label curve from the curve the label curve is based on.
	 * If you wish to set this value, do so directly after creation of the curve.
	 * The first time the curve is used the label curve will be created with 
	 * whatever value is contained in this variable. Changes to it after that point 
	 * will have no effect.
	 */
	protected double labelBuffer = mxConstants.DEFAULT_LABEL_BUFFER;

	/**
	 * The points this curve is drawn through. These are typically control
	 * points and are at distances from each other that straight lines
	 * between them do not describe a smooth curve. This class takes
	 * these guiding points and creates a finer set of internal points
	 * that visually appears to be a curve when linked by straight lines
	 */
	public List<mxPoint> guidePoints = new ArrayList<mxPoint>();

	/**
	 * Whether or not the curve currently holds valid values
	 */
	protected boolean valid = false;

	/**
	 * 
	 */
	public void setLabelBuffer(double buffer)
	{
		labelBuffer = buffer;
	}

	/**
	 * 
	 */
	public mxRectangle getBounds()
	{
		if (!valid)
		{
			createCoreCurve();
		}
		return new mxRectangle(minXBounds, minYBounds, maxXBounds - minXBounds,
				maxYBounds - minYBounds);
	}

	/**
	 * 
	 */
	public mxCurve()
	{
	}

	/**
	 * 
	 */
	public mxCurve(List<mxPoint> points)
	{
		guidePoints = points;
	}

	/**
	 * Calculates the index of the lower point on the segment
	 * that contains the point <i>distance</i> along the 
	 */
	protected int getLowerIndexOfSegment(String index, double distance)
	{
		double[] curveIntervals = getIntervals(index);

		if (curveIntervals == null)
		{
			return 0;
		}
		int numIntervals = curveIntervals.length;

		if (distance <= 0.0 || numIntervals < 2)
		{
			return 0;
		}

		if (distance >= 1.0)
		{
			return numIntervals - 2;
		}

		// Pick a starting index roughly where you expect the point
		// to be
		int testIndex = (int) (numIntervals * distance);

		if (testIndex >= numIntervals)
		{
			testIndex = numIntervals - 1;
		}

		// The max and min indices tested so far
		int lowerLimit = -1;
		int upperLimit = numIntervals;

		// It cannot take more than the number of intervals to find
		// the correct segment
		for (int i = 0; i < numIntervals; i++)
		{
			double segmentDistance = curveIntervals[testIndex];
			double multiplier = 0.5;

			if (distance < segmentDistance)
			{
				upperLimit = Math.min(upperLimit, testIndex);
				multiplier = -0.5;
			}
			else if (distance > segmentDistance)
			{
				lowerLimit = Math.max(lowerLimit, testIndex);
			}
			else
			{
				// Values equal
				if (testIndex == 0)
				{
					lowerLimit = 0;
					upperLimit = 1;
				}
				else
				{
					lowerLimit = testIndex - 1;
					upperLimit = testIndex;
				}
			}

			int indexDifference = upperLimit - lowerLimit;

			if (indexDifference == 1)
			{
				break;
			}

			testIndex = (int) (testIndex + indexDifference * multiplier);

			if (testIndex == lowerLimit)
			{
				testIndex = lowerLimit + 1;
			}

			if (testIndex == upperLimit)
			{
				testIndex = upperLimit - 1;
			}
		}

		if (lowerLimit != upperLimit - 1)
		{
			return -1;
		}

		return lowerLimit;
	}

	/**
	 * Returns a unit vector parallel to the curve at the specified
	 * distance along the curve. To obtain the angle the vector makes
	 * with (1,0) perform Math.atan(segVectorY/segVectorX).
	 * @param index the curve index specifying the curve to analyse
	 * @param distance the distance from start to end of curve (0.0...1.0)
	 * @return a unit vector at the specified point on the curve represented
	 * 		as a line, parallel with the curve
	 */
	public mxLine getCurveParallel(String index, double distance)
	{
		mxPoint[] pointsCurve = getCurvePoints(index);
		double[] curveIntervals = getIntervals(index);

		if (pointsCurve != null && pointsCurve.length > 0
				&& curveIntervals != null && distance >= 0.0 && distance <= 1.0)
		{
			// If the curve is zero length, it will only have one point
			// We can't calculate in this case
			if (pointsCurve.length == 1)
			{
				mxPoint point = pointsCurve[0];
				return new mxLine(new mxPoint(point.getX(), point.getY()),
						new mxPoint(1, 0));
			}

			int lowerLimit = getLowerIndexOfSegment(index, distance);
			mxPoint firstPointOfSeg = pointsCurve[lowerLimit];
			double segVectorX = pointsCurve[lowerLimit + 1].getX()
					- firstPointOfSeg.getX();
			double segVectorY = pointsCurve[lowerLimit + 1].getY()
					- firstPointOfSeg.getY();
			double distanceAlongSeg = (distance - curveIntervals[lowerLimit])
					/ (curveIntervals[lowerLimit + 1] - curveIntervals[lowerLimit]);
			double segLength = Math.sqrt(segVectorX * segVectorX + segVectorY
					* segVectorY);
			mxPoint startPoint = new mxPoint(firstPointOfSeg.getX()
					+ segVectorX * distanceAlongSeg, firstPointOfSeg.getY()
					+ segVectorY * distanceAlongSeg);
			mxPoint endPoint = new mxPoint(segVectorX / segLength, segVectorY
					/ segLength);
			return new mxLine(startPoint, endPoint);
		}
		else
		{
			return new mxLine(new mxPoint(0, 0), new mxPoint(1, 0));
		}
	}

	/**
	 * Returns a section of the curve as an array of points
	 * @param index the curve index specifying the curve to analyse
	 * @param start the start position of the curve segment (0.0...1.0)
	 * @param end the end position of the curve segment (0.0...1.0)
	 * @return a sequence of point representing the curve section or null
	 * 			if it cannot be calculated
	 */
	public mxPoint[] getCurveSection(String index, double start, double end)
	{
		mxPoint[] pointsCurve = getCurvePoints(index);
		double[] curveIntervals = getIntervals(index);

		if (pointsCurve != null && pointsCurve.length > 0
				&& curveIntervals != null && start >= 0.0 && start <= 1.0
				&& end >= 0.0 && end <= 1.0)
		{
			// If the curve is zero length, it will only have one point
			// We can't calculate in this case
			if (pointsCurve.length == 1)
			{
				mxPoint point = pointsCurve[0];
				return new mxPoint[] { new mxPoint(point.getX(), point.getY()) };
			}

			int lowerLimit = getLowerIndexOfSegment(index, start);
			mxPoint firstPointOfSeg = pointsCurve[lowerLimit];
			double segVectorX = pointsCurve[lowerLimit + 1].getX()
					- firstPointOfSeg.getX();
			double segVectorY = pointsCurve[lowerLimit + 1].getY()
					- firstPointOfSeg.getY();
			double distanceAlongSeg = (start - curveIntervals[lowerLimit])
					/ (curveIntervals[lowerLimit + 1] - curveIntervals[lowerLimit]);
			double segLength = Math.sqrt(segVectorX * segVectorX + segVectorY
					* segVectorY);
			mxPoint startPoint = new mxPoint(firstPointOfSeg.getX()
					+ segVectorX * distanceAlongSeg, firstPointOfSeg.getY()
					+ segVectorY * distanceAlongSeg);

			List<mxPoint> result = new ArrayList<mxPoint>();
			result.add(startPoint);

			double current = start;
			current = curveIntervals[++lowerLimit];			

			while (current <= end)
			{
				mxPoint nextPointOfSeg = pointsCurve[lowerLimit];
				result.add(nextPointOfSeg);
				current = curveIntervals[++lowerLimit];
			}

			// Add whatever proportion of the last segment has to 
			// be added to make the exactly end distance
			if (lowerLimit > 0 && lowerLimit < pointsCurve.length && end > curveIntervals[lowerLimit-1])
			{
				firstPointOfSeg = pointsCurve[lowerLimit - 1];
				segVectorX = pointsCurve[lowerLimit].getX()
						- firstPointOfSeg.getX();
				segVectorY = pointsCurve[lowerLimit].getY()
						- firstPointOfSeg.getY();
				distanceAlongSeg = (end - curveIntervals[lowerLimit-1])
						/ (curveIntervals[lowerLimit] - curveIntervals[lowerLimit-1]);
				segLength = Math.sqrt(segVectorX * segVectorX
						+ segVectorY * segVectorY);
				mxPoint endPoint = new mxPoint(firstPointOfSeg.getX()
						+ segVectorX * distanceAlongSeg, firstPointOfSeg.getY()
						+ segVectorY * distanceAlongSeg);
				result.add(endPoint);
			}

			mxPoint[] resultArray = new mxPoint[result.size()];
			return result.toArray(resultArray);
		}
		else
		{
			return null;
		}
	}

	/**
	 * Returns whether or not the rectangle passed in hits any part of this
	 * curve.
	 * @param rect the rectangle to detect for a hit
	 * @return whether or not the rectangle hits this curve
	 */
	public boolean intersectsRect(mxRectangle rect)
	{
		// To save CPU, we can test if the rectangle intersects the entire
		// bounds of this curve
		//if (this.getBounds().intersectsRect(rect))
		if (!getBounds().getRectangle().intersects(rect.getRectangle()))
		{
			return false;
		}

		mxPoint[] pointsCurve = getCurvePoints(mxCurve.CORE_CURVE);

		if (pointsCurve != null && pointsCurve.length > 1)
		{
			// First check for any of the curve points lying within the 
			// rectangle, then for any of the curve segments intersecting 
			// with the rectangle sides
			for (int i = 1; i < pointsCurve.length; i++)
			{
				if (rect.contains(pointsCurve[i].getX(), pointsCurve[i].getY())
						|| rect.contains(pointsCurve[i - 1].getX(),
								pointsCurve[i - 1].getY()))
				{
					return true;
				}
			}

			for (int i = 1; i < pointsCurve.length; i++)
			{
				if (rect.intersectLine(pointsCurve[i].getX(), pointsCurve[i]
						.getY(), pointsCurve[i - 1].getX(), pointsCurve[i - 1]
						.getY()) != null)
				{
					return true;
				}
			}
		}

		return false;
	}

	/**
	 * Returns the point at which this curve intersects the boundary of 
	 * the given rectangle, if it does so. If it does not intersect, 
	 * null is returned. If it intersects multiple times, the first 
	 * intersection from the start end of the curve is returned.
	 * 
	 * @param index the curve index specifying the curve to analyse
	 * @param rect the whose boundary is to be tested for intersection
	 * with this curve
	 * @return the point at which this curve intersects the boundary of 
	 * the given rectangle, if it does so. If it does not intersect, 
	 * null is returned.
	 */
	public mxPoint intersectsRectPerimeter(String index, mxRectangle rect)
	{
		mxPoint result = null;
		mxPoint[] pointsCurve = getCurvePoints(index);

		if (pointsCurve != null && pointsCurve.length > 1)
		{
			int crossingSeg = intersectRectPerimeterSeg(index, rect);

			if (crossingSeg != -1)
			{
				result = intersectRectPerimeterPoint(index, rect, crossingSeg);
			}
		}

		return result;
	}

	/**
	 * Returns the distance from the start of the curve at which this 
	 * curve intersects the boundary of the given rectangle, if it does 
	 * so. If it does not intersect, a negative value is returned. 
	 * If it intersects multiple times, the first intersection from 
	 * the start end of the curve is returned.
	 * 
	 * @param index the curve index specifying the curve to analyse
	 * @param rect the whose boundary is to be tested for intersection
	 * with this curve
	 * @return the distance along the curve from the start at which
	 * the intersection occurs
	 */
	public double intersectsRectPerimeterDist(String index, mxRectangle rect)
	{
		double result = -1;
		mxPoint[] pointsCurve = getCurvePoints(index);
		double[] curveIntervals = getIntervals(index);

		if (pointsCurve != null && pointsCurve.length > 1)
		{
			int segIndex = intersectRectPerimeterSeg(index, rect);
			mxPoint intersectPoint = null;

			if (segIndex != -1)
			{
				intersectPoint = intersectRectPerimeterPoint(index, rect,
						segIndex);
			}

			if (intersectPoint != null)
			{
				double startSegX = pointsCurve[segIndex - 1].getX();
				double startSegY = pointsCurve[segIndex - 1].getY();
				double distToStartSeg = curveIntervals[segIndex - 1]
						* getCurveLength(index);
				double intersectOffsetX = intersectPoint.getX() - startSegX;
				double intersectOffsetY = intersectPoint.getY() - startSegY;
				double lenToIntersect = Math.sqrt(intersectOffsetX
						* intersectOffsetX + intersectOffsetY
						* intersectOffsetY);
				result = distToStartSeg + lenToIntersect;
			}
		}

		return result;
	}

	/**
	 * Utility method to determine within which segment the specified rectangle
	 * intersects the specified curve
	 * 
	 * @param index the curve index specifying the curve to analyse
	 * @param rect the whose boundary is to be tested for intersection
	 * with this curve
	 * @return the point at which this curve intersects the boundary of 
	 * the given rectangle, if it does so. If it does not intersect, 
	 * -1 is returned
	 */
	protected int intersectRectPerimeterSeg(String index, mxRectangle rect)
	{
		mxPoint[] pointsCurve = getCurvePoints(index);

		if (pointsCurve != null && pointsCurve.length > 1)
		{
			for (int i = 1; i < pointsCurve.length; i++)
			{
				if (rect.intersectLine(pointsCurve[i].getX(), pointsCurve[i]
						.getY(), pointsCurve[i - 1].getX(), pointsCurve[i - 1]
						.getY()) != null)
				{
					return i;
				}
			}
		}

		return -1;
	}

	/**
	 * Returns the point at which this curve segment intersects the boundary 
	 * of the given rectangle, if it does so. If it does not intersect, 
	 * null is returned.
	 * 
	 * @param curveIndex the curve index specifying the curve to analyse
	 * @param rect the whose boundary is to be tested for intersection
	 * with this curve
	 * @param indexSeg the segments on this curve being checked
	 * @return the point at which this curve segment  intersects the boundary 
	 * of the given rectangle, if it does so. If it does not intersect, 
	 * null is returned.
	 */
	protected mxPoint intersectRectPerimeterPoint(String curveIndex,
			mxRectangle rect, int indexSeg)
	{
		mxPoint result = null;
		mxPoint[] pointsCurve = getCurvePoints(curveIndex);

		if (pointsCurve != null && pointsCurve.length > 1 && indexSeg >= 0
				&& indexSeg < pointsCurve.length)
		{
			double p1X = pointsCurve[indexSeg - 1].getX();
			double p1Y = pointsCurve[indexSeg - 1].getY();
			double p2X = pointsCurve[indexSeg].getX();
			double p2Y = pointsCurve[indexSeg].getY();

			result = rect.intersectLine(p1X, p1Y, p2X, p2Y);
		}

		return result;
	}

	/**
	 * Calculates the position of an absolute in terms relative
	 * to this curve.
	 * 
	 * @param absPoint the point whose relative point is to calculated
	 * @param index the index of the curve whom the relative position is to be 
	 * calculated from
	 * @return an mxRectangle where the x is the distance along the curve 
	 * (0 to 1), y is the orthogonal offset from the closest segment on the 
	 * curve and (wdith, height) is an additional cartisian offset applied
	 * after the other calculations
	 */
	public mxRectangle getRelativeFromAbsPoint(mxPoint absPoint, String index)
	{
		// Work out which segment the absolute point is closest to
		mxPoint[] currentCurve = getCurvePoints(index);
		double[] currentIntervals = getIntervals(index);
		int closestSegment = 0;
		double closestSegDistSq = 10000000;

		for (int i = 1; i < currentCurve.length; i++)
		{
			mxLine segment = new mxLine(currentCurve[i - 1], currentCurve[i]);
			double segDistSq = segment.ptSegDistSq(absPoint);

			if (segDistSq < closestSegDistSq)
			{
				closestSegDistSq = segDistSq;
				closestSegment = i - 1;
			}
		}

		// Get the distance (squared) from the point to the
		// infinately extrapolated line created by the closest
		// segment. If that value is the same as the distance
		// to the segment then an orthogonal offset from some
		// point on the line will intersect the point. If they
		// are not equal, an additional cartesian offset is
		// required
		mxPoint startSegPt = currentCurve[closestSegment];
		mxPoint endSegPt = currentCurve[closestSegment + 1];

		mxLine closestSeg = new mxLine(startSegPt, endSegPt);
		double lineDistSq = closestSeg.ptLineDistSq(absPoint);

		double orthogonalOffset = Math.sqrt(Math.min(lineDistSq,
				closestSegDistSq));
		double segX = endSegPt.getX() - startSegPt.getX();
		double segY = endSegPt.getY() - startSegPt.getY();
		double segDist = Math.sqrt(segX * segX + segY * segY);
		double segNormX = segX / segDist;
		double segNormY = segY / segDist;
		// The orthogonal offset could be in one of two opposite vectors
		// Try both solutions, one will be closer to one of the segment
		// end points (unless the point is on the line)
		double candidateOffX1 = (absPoint.getX() - segNormY * orthogonalOffset)
				- endSegPt.getX();
		double candidateOffY1 = (absPoint.getY() + segNormX * orthogonalOffset)
				- endSegPt.getY();
		double candidateOffX2 = (absPoint.getX() + segNormY * orthogonalOffset)
				- endSegPt.getX();
		double candidateOffY2 = (absPoint.getY() - segNormX * orthogonalOffset)
				- endSegPt.getY();

		double candidateDist1 = (candidateOffX1 * candidateOffX1)
				+ (candidateOffY1 * candidateOffY1);
		double candidateDist2 = (candidateOffX2 * candidateOffX2)
				+ (candidateOffY2 * candidateOffY2);

		double orthOffsetPointX = 0;
		double orthOffsetPointY = 0;

		if (candidateDist2 < candidateDist1)
		{
			orthogonalOffset = -orthogonalOffset;
		}

		orthOffsetPointX = absPoint.getX() - segNormY * orthogonalOffset;
		orthOffsetPointY = absPoint.getY() + segNormX * orthogonalOffset;

		double distAlongEdge = 0;
		double cartOffsetX = 0;
		double cartOffsetY = 0;

		if (closestSegDistSq != lineDistSq)
		{
			// The orthogonal offset does not move the point onto the
			// segment. Work out an additional cartesian offset that moves
			// the offset point onto the closest end point of the
			// segment

			// Not exact distances, but the equation holds
			double distToStartPoint = Math.abs(orthOffsetPointX
					- startSegPt.getX())
					+ Math.abs(orthOffsetPointY - startSegPt.getY());
			double distToEndPoint = Math
					.abs(orthOffsetPointX - endSegPt.getX())
					+ Math.abs(orthOffsetPointY - endSegPt.getY());
			if (distToStartPoint < distToEndPoint)
			{
				distAlongEdge = currentIntervals[closestSegment];
				cartOffsetX = orthOffsetPointX - startSegPt.getX();
				cartOffsetY = orthOffsetPointY - startSegPt.getY();
			}
			else
			{
				distAlongEdge = currentIntervals[closestSegment + 1];
				cartOffsetX = orthOffsetPointX - endSegPt.getX();
				cartOffsetY = orthOffsetPointY - endSegPt.getY();
			}
		}
		else
		{
			// The point, when orthogonally offset, lies on the segment
			// work out what proportion along the segment, and therefore
			// the entire curve, the offset point lies.
			double segmentLen = Math.sqrt((endSegPt.getX() - orthOffsetPointX)
					* (endSegPt.getX() - orthOffsetPointX)
					+ (startSegPt.getY() - orthOffsetPointY)
					* (startSegPt.getY() - orthOffsetPointY));
			double offsetLen = Math.sqrt((orthOffsetPointX - endSegPt.getX())
					* (orthOffsetPointX - endSegPt.getX())
					+ (orthOffsetPointY - endSegPt.getY())
					* (orthOffsetPointY - endSegPt.getY()));
			double proportionAlongSeg = segmentLen / offsetLen;
			double segProportingDiff = currentIntervals[closestSegment + 1]
					- currentIntervals[closestSegment];
			distAlongEdge = currentIntervals[closestSegment]
					+ segProportingDiff * proportionAlongSeg;
		}

		if (distAlongEdge > 1.0)
		{
			distAlongEdge = 1.0;
		}

		return new mxRectangle(distAlongEdge, orthogonalOffset, cartOffsetX,
				cartOffsetY);
	}

	/**
	 * Creates the actual 
	 */
	protected void createCoreCurve()
	{
		// Curve is marked invalid until all of the error situations have
		// been checked
		valid = false;

		if (guidePoints == null || guidePoints.isEmpty())
		{
			return;
		}
		
		for (int i = 0; i < guidePoints.size(); i++)
		{
			if (guidePoints.get(i) == null)
			{
				return;
			}
		}

		// Reset the cached bounds value
		minXBounds = minYBounds = 10000000;
		maxXBounds = maxYBounds = 0;

		mxSpline spline = new mxSpline(guidePoints);

		// Need the rough length of the spline, so we can get
		// more samples for longer edges
		double lengthSpline = spline.getLength();

		// Check for errors in the spline calculation or zero length curves
		if (Double.isNaN(lengthSpline) || !spline.checkValues()
				|| lengthSpline < 1)
		{
			return;
		}

		mxSpline1D splineX = spline.getSplineX();
		mxSpline1D splineY = spline.getSplineY();
		double baseInterval = 12.0 / lengthSpline;
		double minInterval = 1.0 / lengthSpline;

		// Store the last two spline positions. If the next position is 
		// very close to where the extrapolation of the last two points 
		// then double the interval. This diviation is terms the "flatness".
		// There is a range where the interval is kept the same, any 
		// variation from this range of flatness invokes a proportional 
		// adjustment to try to reenter the range without 
		// over compensating
		double interval = baseInterval;
		// These deviations are only tested against either 
		// dimension individually, working out the correct 
		// distance is too computationally intensive
		double minDeviation = 0.15;
		double maxDeviation = 0.3;
		double preferedDeviation = (maxDeviation + minDeviation) / 2.0;

		// x1, y1 are the position two iterations ago, x2, y2
		// the position on the last iteration
		double x1 = -1.0;
		double x2 = -1.0;
		double y1 = -1.0;
		double y2 = -1.0;

		// Store the change in interval amount between iterations.
		// If it changes the extrapolation calculation must
		// take this into account.
		double intervalChange = 1;

		List<mxPoint> coreCurve = new ArrayList<mxPoint>();
		List<Double> coreIntervals = new ArrayList<Double>();
		boolean twoLoopsComplete = false;

		for (double t = 0; t <= 1.5; t += interval)
		{
			if (t > 1.0)
			{
				// Use the point regardless of the accuracy, 
				t = 1.0001;
				mxPoint endControlPoint = guidePoints
						.get(guidePoints.size() - 1);
				mxPoint finalPoint = new mxPoint(endControlPoint.getX(),
						endControlPoint.getY());
				coreCurve.add(finalPoint);
				coreIntervals.add(t);
				updateBounds(endControlPoint.getX(), endControlPoint.getY());
				break;
			}
			// Whether or not the accuracy of the current point is acceptable
			boolean currentPointAccepted = true;

			double newX = splineX.getFastValue(t);
			double newY = splineY.getFastValue(t);

			// Check if the last points are valid (indicated by
			// dissimilar values)
			// Check we're not in the first, second or last run
			if (x1 != -1.0 && twoLoopsComplete && t != 1.0001)
			{
				// Work out how far the new spline point
				// deviates from the extrapolation created 
				// by the last two points
				double diffX = Math.abs(((x2 - x1) * intervalChange + x2)
						- newX);
				double diffY = Math.abs(((y2 - y1) * intervalChange + y2)
						- newY);

				// If either the x or y of the straight line
				// extrapolation from the last two points
				// is more than the 1D deviation allowed
				// go back and re-calculate with a smaller interval
				// It's possible that the edge has curved too fast
				// for the algorithmn. If the interval is
				// reduced to less than the minimum permitted
				// interval, it may be that it's impossible
				// to get within the deviation because of
				// the extrapolation overshoot. The minimum 
				// interval is set to draw correctly for the
				// vast majority of cases.
				if ((diffX > maxDeviation || diffY > maxDeviation)
						&& interval != minInterval)
				{
					double overshootProportion = maxDeviation
							/ Math.max(diffX, diffY);

					if (interval * overshootProportion <= minInterval)
					{
						// Set the interval 
						intervalChange = minInterval / interval;
					}
					else
					{
						// The interval can still be reduced, half 
						// the interval and go back and redo
						// this iteration
						intervalChange = overshootProportion;
					}

					t -= interval;
					interval *= intervalChange;
					currentPointAccepted = false;
				}
				else if (diffX < minDeviation && diffY < minDeviation)
				{
					intervalChange = 1.4;
					interval *= intervalChange;
				}
				else
				{
					// Try to keep the deviation around the prefered value
					double errorRatio = preferedDeviation
							/ Math.max(diffX, diffY);
					intervalChange = errorRatio / 4.0;
					interval *= intervalChange;
				}

				if (currentPointAccepted)
				{
					x1 = x2;
					y1 = y2;
					x2 = newX;
					y2 = newY;
				}
			}
			else if (x1 == -1.0)
			{
				x1 = x2 = newX;
				y1 = y2 = newY;
			}
			else if (x1 == x2 && y1 == y2)
			{
				x2 = newX;
				y2 = newY;
				twoLoopsComplete = true;
			}
			if (currentPointAccepted)
			{
				mxPoint newPoint = new mxPoint(newX, newY);
				coreCurve.add(newPoint);
				coreIntervals.add(t);
				updateBounds(newX, newY);
			}
		}

		if (coreCurve.size() < 2)
		{
			// A single point makes no sense, leave the curve as invalid
			return;
		}

		mxPoint[] corePoints = new mxPoint[coreCurve.size()];
		int count = 0;

		for (mxPoint point : coreCurve)
		{
			corePoints[count++] = point;
		}

		points = new Hashtable<String, mxPoint[]>();
		curveLengths = new Hashtable<String, Double>();
		points.put(CORE_CURVE, corePoints);
		curveLengths.put(CORE_CURVE, lengthSpline);

		double[] coreIntervalsArray = new double[coreIntervals.size()];
		count = 0;

		for (Double tempInterval : coreIntervals)
		{
			coreIntervalsArray[count++] = tempInterval.doubleValue();
		}

		intervals = new Hashtable<String, double[]>();
		intervals.put(CORE_CURVE, coreIntervalsArray);

		valid = true;
	}

	public void configureLabelCurve()
	{

	}

	/** Whether or not the label curve starts from the end target
	 *  and traces to the start of the branch
	 * @return whether the label curve is reversed
	 */
	public boolean isLabelReversed()
	{
		if (valid)
		{
			mxPoint[] centralCurve = getCurvePoints(CORE_CURVE);
			double changeX = centralCurve[centralCurve.length - 1].getX()
					- centralCurve[0].getX();

			if (changeX < 0)
			{
				return true;
			}
		}

		return false;
	}

	protected void createLabelCurve()
	{
		// Place the label on the "high" side of the vector
		// joining the start and end points of the curve
		mxPoint[] currentCurve = getBaseLabelCurve();

		boolean labelReversed = isLabelReversed();

		List<mxPoint> labelCurvePoints = new ArrayList<mxPoint>();

		// Lower and upper curve start from the very ends
		// of their curves, so given that their middle points
		// are dervied from the center of the central points
		// they will contain one more point and both
		// side curves contain the same end point

		for (int i = 1; i < currentCurve.length; i++)
		{
			int currentIndex = i;
			int lastIndex = i - 1;

			if (labelReversed)
			{
				currentIndex = currentCurve.length - i - 1;
				lastIndex = currentCurve.length - i;
			}

			mxPoint segStartPoint = currentCurve[currentIndex];
			mxPoint segEndPoint = currentCurve[lastIndex];
			double segVectorX = segEndPoint.getX() - segStartPoint.getX();
			double segVectorY = segEndPoint.getY() - segStartPoint.getY();
			double segVectorLength = Math.sqrt(segVectorX * segVectorX
					+ segVectorY * segVectorY);
			double normSegVectorX = segVectorX / segVectorLength;
			double normSegVectorY = segVectorY / segVectorLength;
			double centerSegX = (segEndPoint.getX() + segStartPoint.getX()) / 2.0;
			double centerSegY = (segEndPoint.getY() + segStartPoint.getY()) / 2.0;

			if (i == 1)
			{
				// Special case to work out the very end points at
				// the start of the curve
				mxPoint startPoint = new mxPoint(segEndPoint.getX()
						- (normSegVectorY * labelBuffer), segEndPoint.getY()
						+ (normSegVectorX * labelBuffer));
				labelCurvePoints.add(startPoint);
				updateBounds(startPoint.getX(), startPoint.getY());
			}

			double pointX = centerSegX - (normSegVectorY * labelBuffer);
			double pointY = centerSegY + (normSegVectorX * labelBuffer);
			mxPoint labelCurvePoint = new mxPoint(pointX, pointY);
			updateBounds(pointX, pointX);
			labelCurvePoints.add(labelCurvePoint);

			if (i == currentCurve.length - 1)
			{
				// Special case to work out the very end points at
				// the start of the curve
				mxPoint endPoint = new mxPoint(segStartPoint.getX()
						- (normSegVectorY * labelBuffer), segStartPoint.getY()
						+ (normSegVectorX * labelBuffer));
				labelCurvePoints.add(endPoint);
				updateBounds(endPoint.getX(), endPoint.getY());
			}
		}

		mxPoint[] tmpPoints = new mxPoint[labelCurvePoints.size()];
		points
				.put(LABEL_CURVE, (mxPoint[]) labelCurvePoints
						.toArray(tmpPoints));
		populateIntervals(LABEL_CURVE);
	}

	/**
	 * Returns the curve the label curve is too be based on
	 */
	protected mxPoint[] getBaseLabelCurve()
	{
		return getCurvePoints(CORE_CURVE);
	}

	protected void populateIntervals(String index)
	{
		mxPoint[] currentCurve = points.get(index);

		double[] newIntervals = new double[currentCurve.length];

		double totalLength = 0.0;
		newIntervals[0] = 0;

		for (int i = 0; i < currentCurve.length - 1; i++)
		{
			double changeX = currentCurve[i + 1].getX()
					- currentCurve[i].getX();
			double changeY = currentCurve[i + 1].getY()
					- currentCurve[i].getY();
			double segLength = Math.sqrt(changeX * changeX + changeY * changeY);
			// We initially fill the intervals with the total distance to
			// the end of this segment then later normalize all the values
			totalLength += segLength;
			// The first index was populated before the loop (and is always 0)
			newIntervals[i + 1] = totalLength;
		}

		// Normalize the intervals
		for (int j = 0; j < newIntervals.length; j++)
		{
			if (j == newIntervals.length - 1)
			{
				// Make the final interval slightly over
				// 1.0 so any analysis to find the lower 
				newIntervals[j] = 1.0001;
			}
			else
			{
				newIntervals[j] = newIntervals[j] / totalLength;
			}
		}

		intervals.put(index, newIntervals);
		curveLengths.put(index, totalLength);
	}

	/**
	 * Updates the existing curve using the points passed in. 
	 * @param newPoints the new guide points
	 */
	public void updateCurve(List<mxPoint> newPoints)
	{
		boolean pointsChanged = false;

		if (newPoints.size() != guidePoints.size())
		{
			pointsChanged = true;
		}
		else
		{
			if (!guidePoints.equals(newPoints))
			{
				pointsChanged = true;
			}
		}

		if (pointsChanged)
		{
			guidePoints = newPoints;
			points = new Hashtable<String, mxPoint[]>();
		}
	}

	/**
	 * Obtains the points that make up the curve for the specified
	 * curve index. If that curve, or the core curve that other curves
	 * are based on have not yet been created, then they are lazily
	 * created
	 * @param index the key specifying the curve
	 * @return the points making up that curve
	 */
	public mxPoint[] getCurvePoints(String index)
	{
		if (points == null || points.get(CORE_CURVE) == null)
		{
			createCoreCurve();
		}

		if (valid)
		{
			if (points.get(LABEL_CURVE) == null
					&& index == LABEL_CURVE)
			{
				createLabelCurve();
			}

			return points.get(index);
		}

		return null;
	}

	public double[] getIntervals(String index)
	{
		if (intervals == null)
		{
			createCoreCurve();
		}

		if (valid)
		{
			if (points.get(LABEL_CURVE) == null
					&& index == LABEL_CURVE)
			{
				createLabelCurve();
			}

			return intervals.get(index);
		}

		return null;
	}

	public double getCurveLength(String index)
	{
		if (intervals == null)
		{
			createCoreCurve();
		}

		if (valid)
		{
			if (intervals.get(index) == null)
			{
				createLabelCurve();
			}

			return curveLengths.get(index);
		}

		return 0;
	}

	/**
	 * Updates the total bounds of this curve, increasing any dimensions,
	 * if necessary, to fit in the specified point
	 */
	protected void updateBounds(double pointX, double pointY)
	{
		minXBounds = Math.min(minXBounds, pointX);
		maxXBounds = Math.max(maxXBounds, pointX);
		minYBounds = Math.min(minYBounds, pointY);
		maxYBounds = Math.max(maxYBounds, pointY);
	}

	/**
	 * @return the guidePoints
	 */
	public List<mxPoint> getGuidePoints()
	{
		return guidePoints;
	}
}
