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);
121 // Check whether distAB is 0.0 - if so, find furthest point from startxy and compress from start to here and here to end
124 final int furthestIndex = getFurthestPointIndex(inSegStart, inSegEnd);
125 if (furthestIndex > inSegStart)
127 compressSegment(inFlags, inSegStart, furthestIndex, inThreshold);
128 compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
133 double maxDist = -1.0, dist = -1.0;
134 int furthestIndex = -1;
135 for (int i=inSegStart+1; i<inSegEnd; i++)
137 if (inFlags[i] == 0) // unknown status
139 XYpoint currPoint = new XYpoint(_track.getX(i), _track.getY(i));
140 XYpoint ac = startxy.vectorTo(currPoint);
141 double distAP = ab.dot(ac) / dist2AB;
142 // calc distance from point to line depending on distAP
144 dist = ac.len(); // outside line segment AB on the A side
146 else if (distAP > 1.0) {
147 dist = endxy.vectorTo(currPoint).len(); // outside on the B side
150 // P lies between A and B so use dot product
151 dist = Math.abs(perpendicular.dot(ac));
160 // Check furthest point and see if it's further than the threshold
161 if (maxDist > inThreshold)
163 inFlags[furthestIndex] = 1;
164 // Make recursive calls for bit before and bit after kept point
165 compressSegment(inFlags, inSegStart, furthestIndex, inThreshold);
166 compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
172 * @return specific gui components for dialog
174 protected Component getSpecificGuiComponents()
176 return getSpecificGuiComponents("dialog.compress.douglaspeucker.paramdesc", "2000");
180 * @return title key for box
182 protected String getTitleTextKey()
184 return "dialog.compress.douglaspeucker.title";
188 * Find the index of the point furthest away from the start and end points
189 * @param inStartIndex start index of segment to check
190 * @param inEndIndex end index of segment to check
191 * @return index of furthest point, or -1 if none found
193 private int getFurthestPointIndex(int inStartIndex, int inEndIndex)
195 int furthestIndex = -1;
196 if (inStartIndex >= 0 && inEndIndex > inStartIndex)
198 final DataPoint startPoint = _track.getPoint(inStartIndex);
199 double maxDist = 0.0;
200 // Loop over points between start and end
201 for (int i=inStartIndex+1; i<inEndIndex; i++)
203 DataPoint p = _track.getPoint(i);
206 double distFromStart = DataPoint.calculateRadiansBetween(startPoint, p);
207 if (distFromStart > maxDist)
210 maxDist = distFromStart;
215 return furthestIndex;