1 package tim.prune.function.compress;
3 import java.awt.Component;
4 import java.awt.event.ActionListener;
6 import tim.prune.data.DataPoint;
7 import tim.prune.data.Track;
10 * Douglas-Peucker algorithm for compresssion
12 public class DouglasPeuckerAlgorithm extends SingleParameterAlgorithm
16 * @param inTrack track object
17 * @param inDetails track details object
18 * @param inListener listener to attach to activation control
20 public DouglasPeuckerAlgorithm(Track inTrack, TrackDetails inDetails, ActionListener inListener)
22 super(inTrack, inDetails, inListener);
26 * Perform the compression and work out which points should be deleted
27 * @param inFlags deletion flags from previous algorithms
28 * @return number of points deleted
30 protected int compress(boolean[] inFlags)
33 double param = getParameter();
34 // Use 1/x if x greater than 1
35 if (param > 1.0) param = 1.0 / param;
36 if (param <= 0.0 || param >= 1.0) {
37 // Parameter isn't valid, don't delete any
40 double threshold = _trackDetails.getTrackSpan() * param;
42 int numPoints = _track.getNumPoints();
43 int origNumDeleted = countFlags(inFlags);
44 // Convert inFlags into keepFlags
45 int[] keepFlags = new int[numPoints];
46 int segStart = -1, segEnd = -1;
47 // Loop over all points in track
48 for (int i=0; i<numPoints; i++)
50 DataPoint currPoint = _track.getPoint(i);
51 if (currPoint.getSegmentStart())
53 // new segment found, so process previous one
54 if (segStart > -1 && segEnd > segStart)
56 keepFlags[segEnd] = 1; // keep
57 compressSegment(keepFlags, segStart, segEnd, threshold);
58 segStart = segEnd = -1;
61 if (inFlags[i]) keepFlags[i] = -1; // already deleted
62 else if (currPoint.isWaypoint() || currPoint.hasMedia() || currPoint.getSegmentStart()) {
63 keepFlags[i] = 1; // keep
65 // Don't consider points which are already marked as deleted, ignore waypoints
66 if (!inFlags[i] && !currPoint.isWaypoint())
68 // remember starts and ends
69 if (segStart < 0) {segStart = i;}
73 // Last segment, if any
74 if (segStart >= 0 && segEnd > segStart) {
75 keepFlags[segEnd] = 1; // keep
76 compressSegment(keepFlags, segStart, segEnd, threshold);
78 // Convert keepFlags back into inFlags
79 for (int i=1; i<numPoints; i++) {
80 if (keepFlags[i] < 1) inFlags[i] = true;
82 return countFlags(inFlags) - origNumDeleted;
87 * Count the number of true flags in the given array
88 * @param inFlags array of boolean flags
89 * @return number of flags which are set to true
91 private static int countFlags(boolean[] inFlags)
94 for (int i=0; i<inFlags.length; i++) {
95 if (inFlags[i]) numDeleted++;
101 * Compress the given segment (recursively)
102 * @param inFlags int array of deletion flags for entire track
103 * @param inSegStart index of start of segment
104 * @param inSegEnd index of end of segment
105 * @param inThreshold threshold to use
107 private void compressSegment(int[] inFlags, int inSegStart, int inSegEnd,
110 //System.out.println("Compress segment " + inSegStart + "-" + inSegEnd);
111 final int numPoints = inSegEnd - inSegStart + 1;
112 if (numPoints < 3) {return;} // segment too short to compress
113 // Calculate parameters of straight line between first and last
114 XYpoint startxy = new XYpoint(_track.getX(inSegStart), _track.getY(inSegStart));
115 XYpoint endxy = new XYpoint(_track.getX(inSegEnd), _track.getY(inSegEnd));
116 XYpoint ab = startxy.vectorTo(endxy);
117 final double dist2AB = ab.len2();
118 // create unit vector perpendicular to AB
119 final double distAB = ab.len();
120 XYpoint perpendicular = new XYpoint(ab.y/distAB, -ab.x/distAB);
122 double maxDist = -1.0, dist = -1.0;
123 int furthestIndex = -1;
124 for (int i=inSegStart+1; i<inSegEnd; i++)
126 if (inFlags[i] == 0) // unknown status
128 XYpoint currPoint = new XYpoint(_track.getX(i), _track.getY(i));
129 XYpoint ac = startxy.vectorTo(currPoint);
130 double distAP = ab.dot(ac) / dist2AB;
131 // calc distance from point to line depending on distAP
133 dist = ac.len(); // outside line segment AB on the A side
135 else if (distAP > 1.0) {
136 dist = endxy.vectorTo(currPoint).len(); // outside on the B side
139 // P lies between A and B so use dot product
140 dist = Math.abs(perpendicular.dot(ac));
149 // Check furthest point and see if it's further than the threshold
150 if (maxDist > inThreshold)
152 inFlags[furthestIndex] = 1;
153 // Make recursive calls for bit before and bit after kept point
154 compressSegment(inFlags, inSegStart, furthestIndex, inThreshold);
155 compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
161 * @return specific gui components for dialog
163 protected Component getSpecificGuiComponents()
165 return getSpecificGuiComponents("dialog.compress.douglaspeucker.paramdesc", "2000");
169 * @return title key for box
171 protected String getTitleTextKey()
173 return "dialog.compress.douglaspeucker.title";