+++ /dev/null
-package tim.prune.function.compress;
-
-import java.awt.Component;
-import java.awt.event.ActionListener;
-
-import tim.prune.data.DataPoint;
-import tim.prune.data.Track;
-
-/**
- * Douglas-Peucker algorithm for compresssion
- */
-public class DouglasPeuckerAlgorithm extends SingleParameterAlgorithm
-{
- /**
- * Constructor
- * @param inTrack track object
- * @param inDetails track details object
- * @param inListener listener to attach to activation control
- */
- public DouglasPeuckerAlgorithm(Track inTrack, TrackDetails inDetails, ActionListener inListener)
- {
- super(inTrack, inDetails, inListener);
- }
-
- /**
- * Perform the compression and work out which points should be deleted
- * @param inFlags deletion flags from previous algorithms
- * @return number of points deleted
- */
- protected int compress(boolean[] inFlags)
- {
- // Parse parameter
- double param = getParameter();
- // Use 1/x if x greater than 1
- if (param > 1.0) param = 1.0 / param;
- if (param <= 0.0 || param >= 1.0) {
- // Parameter isn't valid, don't delete any
- return 0;
- }
- double threshold = _trackDetails.getTrackSpan() * param;
-
- int numPoints = _track.getNumPoints();
- int origNumDeleted = countFlags(inFlags);
- // 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 = _track.getPoint(i);
- if (currPoint.getSegmentStart())
- {
- // new segment found, so process previous one
- if (segStart > -1 && segEnd > segStart)
- {
- keepFlags[segEnd] = 1; // keep
- compressSegment(keepFlags, segStart, segEnd, threshold);
- segStart = segEnd = -1;
- }
- }
- if (inFlags[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 (!inFlags[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(keepFlags, segStart, segEnd, threshold);
- }
- // Convert keepFlags back into inFlags
- for (int i=1; i<numPoints; i++) {
- if (keepFlags[i] < 1) inFlags[i] = true;
- }
- return countFlags(inFlags) - origNumDeleted;
- }
-
-
- /**
- * Count the number of true flags in the given array
- * @param inFlags array of boolean flags
- * @return number of flags which are set to true
- */
- private static int countFlags(boolean[] inFlags)
- {
- int numDeleted = 0;
- for (int i=0; i<inFlags.length; i++) {
- if (inFlags[i]) numDeleted++;
- }
- return numDeleted;
- }
-
- /**
- * Compress the given segment (recursively)
- * @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(int[] inFlags, int inSegStart, int inSegEnd,
- double inThreshold)
- {
- // System.out.println("Compress segment " + inSegStart + "-" + inSegEnd);
- final int numPoints = inSegEnd - inSegStart + 1;
- if (numPoints < 3) {return;} // segment too short to compress
- // Calculate parameters of straight line between first and last
- XYpoint startxy = new XYpoint(_track.getX(inSegStart), _track.getY(inSegStart));
- XYpoint endxy = new XYpoint(_track.getX(inSegEnd), _track.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(inSegStart, inSegEnd);
- if (furthestIndex > inSegStart)
- {
- compressSegment(inFlags, inSegStart, furthestIndex, inThreshold);
- compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
- }
- return;
- }
-
- double maxDist = -1.0, dist = -1.0;
- int furthestIndex = -1;
- for (int i=inSegStart+1; i<inSegEnd; i++)
- {
- if (inFlags[i] == 0) // unknown status
- {
- XYpoint currPoint = new XYpoint(_track.getX(i), _track.getY(i));
- XYpoint ac = startxy.vectorTo(currPoint);
- double distAP = ab.dot(ac) / dist2AB;
- // calc distance from point to line depending on distAP
- 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(inFlags, inSegStart, furthestIndex, inThreshold);
- compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
- }
- }
-
-
- /**
- * @return specific gui components for dialog
- */
- protected Component getSpecificGuiComponents()
- {
- return getSpecificGuiComponents("dialog.compress.douglaspeucker.paramdesc", "2000");
- }
-
- /**
- * @return title key for box
- */
- protected String getTitleTextKey()
- {
- return "dialog.compress.douglaspeucker.title";
- }
-
- /**
- * Find the index of the point furthest away from the start and end points
- * @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(int inStartIndex, int inEndIndex)
- {
- int furthestIndex = -1;
- if (inStartIndex >= 0 && inEndIndex > inStartIndex)
- {
- final DataPoint startPoint = _track.getPoint(inStartIndex);
- double maxDist = 0.0;
- // Loop over points between start and end
- for (int i=inStartIndex+1; i<inEndIndex; i++)
- {
- DataPoint p = _track.getPoint(i);
- if (!p.isWaypoint())
- {
- double distFromStart = DataPoint.calculateRadiansBetween(startPoint, p);
- if (distFromStart > maxDist)
- {
- furthestIndex = i;
- maxDist = distFromStart;
- }
- }
- }
- }
- return furthestIndex;
- }
-}
projects / GpsPrune.git / blobdiff