content: package tim.prune.function.compress.methods;
  
  import tim.prune.data.DataPoint;
  import tim.prune.data.MarkingData;
  import tim.prune.data.NumberUtils;
  import tim.prune.data.Track;
  import tim.prune.function.compress.CompressionMethodType;
  import tim.prune.function.compress.TrackDetails;
  import tim.prune.function.compress.XYpoint;
  
  public class DouglasPeuckerMethod extends CompressionMethod
  {
  	private final int _factor;
  
  	public DouglasPeuckerMethod(int factor) {
  		_factor = factor;
  	}
  
  	public DouglasPeuckerMethod(String inString) {
  		_factor = recogniseString(inString) ? NumberUtils.getIntOrZero(inString.substring(4)) : (int) NumberUtils.getDoubleOrZero(inString);
  	}
  
  	public CompressionMethodType getType() {
  		return CompressionMethodType.DOUGLAS_PEUCKER;
  	}
  
  	public String getParam() {
  		return "" + Math.abs(_factor);
  	}
  
  	public int compress(Track inTrack, TrackDetails inDetails, MarkingData inMarkings)
  	{
  		// Parse parameter
  		double param = _factor <= 0 ? 1.0 : (1.0 / _factor);
  		double threshold = inDetails.getTrackSpan() * param;
  
  		int numPoints = inTrack.getNumPoints();
  		int origNumDeleted = inMarkings.getNumDeleted();
  		// Convert inFlags into keepFlags
  		int[] keepFlags = new int[numPoints];
  		int segStart = -1, segEnd = -1;
  		// Loop over all points in track
  		for (int i=0; i<numPoints; i++)
  		{
  			DataPoint currPoint = inTrack.getPoint(i);
  			if (currPoint.getSegmentStart())
  			{
  				// new segment found, so process previous one
  				if (segStart > -1 && segEnd > segStart)
  				{
  					keepFlags[segEnd] = 1; // keep
  					compressSegment(inTrack, keepFlags, segStart, segEnd, threshold);
  					segStart = segEnd = -1;
  				}
  			}
  			if (inMarkings.isPointMarkedForDeletion(i)) {
  				keepFlags[i] = -1; // already deleted
  			}
  			else if (currPoint.isWaypoint() || currPoint.hasMedia() || currPoint.getSegmentStart()) {
  				keepFlags[i] = 1; // keep
  			}
  			// Don't consider points which are already marked as deleted, ignore waypoints
  			if (!inMarkings.isPointMarkedForDeletion(i) && !currPoint.isWaypoint())
  			{
  				// remember starts and ends
  				if (segStart < 0) {segStart = i;}
  				else {segEnd = i;}
  			}
  		}
  		// Last segment, if any
  		if (segStart >= 0 && segEnd > segStart) {
  			keepFlags[segEnd] = 1; // keep
  			compressSegment(inTrack, keepFlags, segStart, segEnd, threshold);
  		}
  		// Convert keepFlags back into inFlags
  		for (int i=1; i<numPoints; i++)
  		{
  			if (keepFlags[i] < 1) {
  				inMarkings.markPointForDeletion(i);
  			}
  		}
  		return inMarkings.getNumDeleted() - origNumDeleted;
  	}
  
  	/**
  	 * Compress the given segment (recursively)
  	 * @param inTrack the track to compress
  	 * @param inFlags int array of deletion flags for entire track
  	 * @param inSegStart index of start of segment
  	 * @param inSegEnd index of end of segment
  	 * @param inThreshold threshold to use
  	 */
  	private void compressSegment(Track inTrack, int[] inFlags, int inSegStart, int inSegEnd,
  		double inThreshold)
  	{
  		// System.out.println("Compress segment " + inSegStart + "-" + inSegEnd);
  		final int numPoints = inSegEnd - inSegStart + 1;
  		if (numPoints < 3) {
  			 // segment too short to compress
  			return;
  		}
  		// Calculate parameters of straight line between first and last
  		XYpoint startxy = new XYpoint(inTrack.getX(inSegStart), inTrack.getY(inSegStart));
  		XYpoint endxy = new XYpoint(inTrack.getX(inSegEnd), inTrack.getY(inSegEnd));
  		XYpoint ab = startxy.vectorTo(endxy);
  		final double dist2AB = ab.len2();
  		// create unit vector perpendicular to AB
  		final double distAB = ab.len();
  		XYpoint perpendicular = new XYpoint(ab.y/distAB, -ab.x/distAB);
  		// Check whether distAB is 0.0 - if so, find furthest point from startxy and compress from start to here and here to end
  		if (distAB <= 0.0)
  		{
  			final int furthestIndex = getFurthestPointIndex(inTrack, inSegStart, inSegEnd);
  			if (furthestIndex > inSegStart)
  			{
  				compressSegment(inTrack, inFlags, inSegStart, furthestIndex, inThreshold);
  				compressSegment(inTrack, inFlags, furthestIndex, inSegEnd, inThreshold);
  			}
  			return;
  		}
  
  		double maxDist = -1.0;
  		int furthestIndex = -1;
  		for (int i=inSegStart+1; i<inSegEnd; i++)
  		{
  			if (inFlags[i] == 0) // unknown status
  			{
  				XYpoint currPoint = new XYpoint(inTrack.getX(i), inTrack.getY(i));
  				XYpoint ac = startxy.vectorTo(currPoint);
  				double distAP = ab.dot(ac) / dist2AB;
  				// calc distance from point to line depending on distAP
  				final double dist;
  				if (distAP < 0.0) {
  					dist = ac.len(); // outside line segment AB on the A side
  				}
  				else if (distAP > 1.0) {
  					dist = endxy.vectorTo(currPoint).len(); // outside on the B side
  				}
  				else {
  					// P lies between A and B so use dot product
  					dist = Math.abs(perpendicular.dot(ac));
  				}
  				if (dist > maxDist)
  				{
  					maxDist = dist;
  					furthestIndex = i;
  				}
  			}
  		}
  		// Check furthest point and see if it's further than the threshold
  		if (maxDist > inThreshold)
  		{
  			inFlags[furthestIndex] = 1;
  			// Make recursive calls for bit before and bit after kept point
  			compressSegment(inTrack, inFlags, inSegStart, furthestIndex, inThreshold);
  			compressSegment(inTrack, inFlags, furthestIndex, inSegEnd, inThreshold);
  		}
  	}
  
  	/**
  	 * Find the index of the point furthest away from the start and end points
  	 * @param inTrack the track to compress
  	 * @param inStartIndex start index of segment to check
  	 * @param inEndIndex end index of segment to check
  	 * @return index of furthest point, or -1 if none found
  	 */
  	private int getFurthestPointIndex(Track inTrack, int inStartIndex, int inEndIndex)
  	{
  		int furthestIndex = -1;
  		if (inStartIndex >= 0 && inEndIndex > inStartIndex)
  		{
  			final DataPoint startPoint = inTrack.getPoint(inStartIndex);
  			double maxDist = 0.0;
  			// Loop over points between start and end
  			for (int i=inStartIndex+1; i<inEndIndex; i++)
  			{
  				DataPoint p = inTrack.getPoint(i);
  				if (p.isWaypoint()) {
  					continue;
  				}
  				double distFromStart = DataPoint.calculateRadiansBetween(startPoint, p);
  				if (distFromStart > maxDist)
  				{
  					furthestIndex = i;
  					maxDist = distFromStart;
  				}
  			}
  		}
  		return furthestIndex;
  	}
  
  	public String getSettingsString() {
  		return getType().getKey() + _factor;
  	}
  
  	static boolean recogniseString(String inString) {
  		return recogniseString(inString, CompressionMethodType.DOUGLAS_PEUCKER);
  	}
  }
  