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                 // Check whether distAB is 0.0 - if so, find furthest point from startxy and compress from start to here and here to end
 122                 if (distAB <= 0.0)
 123                 {
 124                         final int furthestIndex = getFurthestPointIndex(inSegStart, inSegEnd);
 125                         if (furthestIndex > inSegStart)
 126                         {
 127                                 compressSegment(inFlags, inSegStart, furthestIndex, inThreshold);
 128                                 compressSegment(inFlags, furthestIndex, inSegEnd, inThreshold);
 129                         }
 130                         return;
 131                 }
 132
 133                 double maxDist = -1.0, dist = -1.0;
 134                 int furthestIndex = -1;
 135                 for (int i=inSegStart+1; i<inSegEnd; i++)
 136                 {
 137                         if (inFlags[i] == 0) // unknown status
 138                         {
 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
 143                                 if (distAP < 0.0) {
 144                                         dist = ac.len(); // outside line segment AB on the A side
 145                                 }
 146                                 else if (distAP > 1.0) {
 147                                         dist = endxy.vectorTo(currPoint).len(); // outside on the B side
 148                                 }
 149                                 else {
 150                                         // P lies between A and B so use dot product
 151                                         dist = Math.abs(perpendicular.dot(ac));
 152                                 }
 153                                 if (dist > maxDist)
 154                                 {
 155                                         maxDist = dist;
 156                                         furthestIndex = i;
 157                                 }
 158                         }
 159                 }
 160                 // Check furthest point and see if it's further than the threshold
 161                 if (maxDist > inThreshold)
 162                 {
 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);
 167                 }
 168         }
 169
 170
 171         /**
 172          * @return specific gui components for dialog
 173          */
 174         protected Component getSpecificGuiComponents()
 175         {
 176                 return getSpecificGuiComponents("dialog.compress.douglaspeucker.paramdesc", "2000");
 177         }
 178
 179         /**
 180          * @return title key for box
 181          */
 182         protected String getTitleTextKey()
 183         {
 184                 return "dialog.compress.douglaspeucker.title";
 185         }
 186
 187         /**
 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
 192          */
 193         private int getFurthestPointIndex(int inStartIndex, int inEndIndex)
 194         {
 195                 int furthestIndex = -1;
 196                 if (inStartIndex >= 0 && inEndIndex > inStartIndex)
 197                 {
 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++)
 202                         {
 203                                 DataPoint p = _track.getPoint(i);
 204                                 if (!p.isWaypoint())
 205                                 {
 206                                         double distFromStart = DataPoint.calculateRadiansBetween(startPoint, p);
 207                                         if (distFromStart > maxDist)
 208                                         {
 209                                                 furthestIndex = i;
 210                                                 maxDist = distFromStart;
 211                                         }
 212                                 }
 213                         }
 214                 }
 215                 return furthestIndex;
 216         }
 217 }