tim/prune/function/compress/DouglasPeuckerAlgorithm.java

   1 package tim.prune.function.compress;
   2
   3 import java.awt.Component;
   4 import java.awt.event.ActionListener;
   5
   6 import tim.prune.data.DataPoint;
   7 import tim.prune.data.Track;
   8
   9 /**
  10  * Douglas-Peucker algorithm for compresssion
  11  */
  12 public class DouglasPeuckerAlgorithm extends SingleParameterAlgorithm
  13 {
  14         /**
  15          * Constructor
  16          * @param inTrack track object
  17          * @param inDetails track details object
  18          * @param inListener listener to attach to activation control
  19          */
  20         public DouglasPeuckerAlgorithm(Track inTrack, TrackDetails inDetails, ActionListener inListener)
  21         {
  22                 super(inTrack, inDetails, inListener);
  23         }
  24
  25         /**
  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
  29          */
  30         protected int compress(boolean[] inFlags)
  31         {
  32                 // Parse parameter
  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
  38                         return 0;
  39                 }
  40                 double threshold = _trackDetails.getTrackSpan() * param;
  41
  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++)
  49                 {
  50                         DataPoint currPoint = _track.getPoint(i);
  51                         if (currPoint.getSegmentStart())
  52                         {
  53                                 // new segment found, so process previous one
  54                                 if (segStart > -1 && segEnd > segStart)
  55                                 {
  56                                         keepFlags[segEnd] = 1; // keep
  57                                         compressSegment(keepFlags, segStart, segEnd, threshold);
  58                                         segStart = segEnd = -1;
  59                                 }
  60                         }
  61                         if (inFlags[i]) keepFlags[i] = -1; // already deleted
  62                         else if (currPoint.isWaypoint() || currPoint.hasMedia() || currPoint.getSegmentStart()) {
  63                                 keepFlags[i] = 1; // keep
  64                         }
  65                         // Don't consider points which are already marked as deleted, ignore waypoints
  66                         if (!inFlags[i] && !currPoint.isWaypoint())
  67                         {
  68                                 // remember starts and ends
  69                                 if (segStart < 0) {segStart = i;}
  70                                 else {segEnd = i;}
  71                         }
  72                 }
  73                 // Last segment, if any
  74                 if (segStart >= 0 && segEnd > segStart) {
  75                         keepFlags[segEnd] = 1; // keep
  76                         compressSegment(keepFlags, segStart, segEnd, threshold);
  77                 }
  78                 // Convert keepFlags back into inFlags
  79                 for (int i=1; i<numPoints; i++) {
  80                         if (keepFlags[i] < 1) inFlags[i] = true;
  81                 }
  82                 return countFlags(inFlags) - origNumDeleted;
  83         }
  84
  85
  86         /**
  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
  90          */
  91         private static int countFlags(boolean[] inFlags)
  92         {
  93                 int numDeleted = 0;
  94                 for (int i=0; i<inFlags.length; i++) {
  95                         if (inFlags[i]) numDeleted++;
  96                 }
  97                 return numDeleted;
  98         }
  99
 100         /**
 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
 106          */
 107         private void compressSegment(int[] inFlags, int inSegStart, int inSegEnd,
 108                 double inThreshold)
 109         {
 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
 122                 double maxDist = -1.0, dist = -1.0;
 123                 int furthestIndex = -1;
 124                 for (int i=inSegStart+1; i<inSegEnd; i++)
 125                 {
 126                         if (inFlags[i] == 0) // unknown status
 127                         {
 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
 132                                 if (distAP < 0.0) {
 133                                         dist = ac.len(); // outside line segment AB on the A side
 134                                 }
 135                                 else if (distAP > 1.0) {
 136                                         dist = endxy.vectorTo(currPoint).len(); // outside on the B side
 137                                 }
 138                                 else {
 139                                         // P lies between A and B so use dot product
 140                                         dist = Math.abs(perpendicular.dot(ac));
 141                                 }
 142                                 if (dist > maxDist)
 143                                 {
 144                                         maxDist = dist;
 145                                         furthestIndex = i;
 146                                 }
 147                         }
 148                 }
 149                 // Check furthest point and see if it's further than the threshold
 150                 if (maxDist > inThreshold)
 151                 {
 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);
 156                 }
 157         }
 158
 159
 160         /**
 161          * @return specific gui components for dialog
 162          */
 163         protected Component getSpecificGuiComponents()
 164         {
 165                 return getSpecificGuiComponents("dialog.compress.douglaspeucker.paramdesc", "2000");
 166         }
 167
 168         /**
 169          * @return title key for box
 170          */
 171         protected String getTitleTextKey()
 172         {
 173                 return "dialog.compress.douglaspeucker.title";
 174         }
 175 }