src/ui/GestureReader.cc

   1 /* Shopper
   2  * Copyright (C) 2008 David Greaves
   3  *
   4  * This software is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public License
   6  * as published by the Free Software Foundation; either version 2.1 of
   7  * the License, or (at your option) any later version.
   8  *
   9  * This software is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this software; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
  17  * 02110-1301 USA
  18  *
  19  */
  20 //#define DEBUG_SHOPPER 1
  21 #include "shopper.h"           // automake, i8n, gettext
  22 #include "GestureReader.h"
  23
  24 // This class is used to record gesture events
  25 //
  26 // There are 2 main functions:
  27 //
  28 // Recording
  29 // =========
  30 // This records a path of points
  31 // These can be press, release and move
  32 // as some gestures may have multiple strokes
  33 //
  34 // Matching
  35 // ========
  36 // Based on an idea by Johan Thelin
  37 //
  38 // smooths/dejitters the points on entry
  39 // Then creates a stroke pattern
  40 // Then matches against the supplied list
  41 //
  42 // If this fails then the stroke pattern is simplified
  43 //
  44
  45 #define STROKECODELEN 4  // length of code strings including \0 (pad short codes with \0s, not ' ')
  46 // Lookup table for GestureReader::Point::Direction
  47 static const char* StrokeCodes =". \0\0u \0\0r \0\0d \0\0l \0\0ur \0dr \0dl \0ul \0";
  48 // Lookup table for GestureReader::Point::pointType
  49 //static const char* TouchCodes =".. \0R \0\0P \0\0* \0\0. \0\0";  // release/press
  50
  51
  52 GestureReader::Point::Point():
  53         x(0),
  54         y(0),
  55         len2(0),
  56         direction(None),
  57         type(Invalid) {};
  58
  59 GestureReader::Point::Point( int _x, int _y, int _len2,
  60                                                          Point::Direction _dir, Point::Type _type) :
  61         x(_x), y(_y), len2(_len2), direction(_dir), type(_type)
  62 {}
  63
  64 struct GestureReader::Private
  65 {
  66         QList<Point> points;  // this is replaced during smoothing
  67         QString strokes;
  68         int lastX, lastY;
  69         int smallestStrokeLen;  // calculated during generateStrokes...
  70         int SmoothLimit2;
  71 };
  72
  73 // Fwd declare local private helper
  74 GestureReader::Point::Direction calcDirection(int dx, int dy);
  75
  76 // class GestureReader : public QObject
  77 // public:
  78 GestureReader::GestureReader()
  79 {
  80         p = new Private;
  81         p->SmoothLimit2 = 900; // 30^2 - no segments < 30 pixels long
  82 }
  83
  84 GestureReader::~GestureReader()
  85 {
  86         delete p;
  87 }
  88
  89 ////////////////////////////////////////////////////////////////
  90 // Creating a path
  91 void GestureReader::start(int x, int y)
  92 {
  93         _ENTER;
  94         p->points.clear();
  95         p->points.append( Point(x, y, 0, Point::None, Point::Start) );
  96         p->lastX = x;
  97         p->lastY = y;
  98 }
  99
 100 void GestureReader::addPoint(int x, int y, Point::Type type)
 101 {
 102 //      _ENTER;
 103         int dx = x - p->lastX;
 104         int dy = y - p->lastY;
 105         int len2 = dx*dx + dy*dy;
 106         if (len2 < p->SmoothLimit2) { // ignore jitter
 107                 // If we jittered to an Release/Press then use the last X/Y
 108                 if (type == Point::Press || type == Point::Release)
 109                         p->points.append( Point(p->lastX, p->lastY, 0, Point::None, type) );
 110                 return;
 111         }
 112
 113         // Ensure all movement is recorded using Point::Move and up/down is static.
 114         p->points.append( Point(x, y, len2, calcDirection( dx, dy), Point::Move) );
 115
 116         // Movement registered and recorded.
 117         p->lastX = x;
 118         p->lastY = y;
 119
 120         // an Release/Press if needed
 121         if (type == Point::Press || type == Point::Release)
 122                 p->points.append( Point(x,y,0, Point::None, type) );
 123
 124 }
 125
 126 ////////////////////////////////////////////////////////////////
 127 // silly helper functions
 128 int abs(int Nbr){ return (Nbr >= 0 ? Nbr : -Nbr); }
 129
 130 int sqr(int Nbr)
 131 {
 132         if (Nbr == 1) return 1;
 133         Nbr = abs(Nbr);
 134         int Number = Nbr / 2;
 135         int lastGuess;
 136         do {lastGuess = Number; Number = (Number + Nbr / Number) / 2;
 137         } while( abs(Number - lastGuess) > 1);
 138         return Number;
 139 }
 140
 141 ////////////////////////////////////////////////////////////////
 142 // Analyse points
 143
 144 GestureReader::Point::Direction calcDirection(int dx, int dy)
 145 {
 146 //      _ENTER;
 147         // Handle the 0 cases to avoid problems....
 148         if (dx == 0){
 149                 if (dy > 0)
 150                         return GestureReader::Point::Down;
 151                 else
 152                         return GestureReader::Point::Up;
 153         } else if (dy == 0) {
 154                 if (dx > 0)
 155                         return GestureReader::Point::Right;
 156                 else
 157                         return GestureReader::Point::Left;
 158         }
 159
 160         //  tan(theta) = opposite / adjacent
 161         //  scale by 10000 for a little accuracy - it's rough but good enough
 162         int ratio = 10000 * dx / -dy;
 163
 164         // Nb using -ve dy - this means the model below is based on a
 165         // traditional set of axis, X increasing to right, Y increasing
 166         // vertically....
 167
 168         if ( ratio < -22998 )  //tan -66.5 = -2.2998
 169                 return (dx > 0) ?
 170                         GestureReader::Point::Right :
 171                         GestureReader::Point::Left ;
 172
 173         if ( ratio < -4142 )  //tan -22.5 = -0.4142
 174                 return (dx > 0) ?
 175                         GestureReader::Point::DownRight :
 176                         GestureReader::Point::UpLeft ;
 177
 178         if ( ratio < 0 )      // axis
 179                 return (dx > 0) ?
 180                         GestureReader::Point::Down :
 181                         GestureReader::Point::Up ;
 182
 183         if ( ratio < 4142 )   //tan -22.5 = -0.4142
 184                 return (dx > 0) ?
 185                         GestureReader::Point::Up :
 186                         GestureReader::Point::Down ;
 187
 188         if ( ratio < 22998 )  //tan 66.5 = 2.2998
 189                 return (dx > 0) ?
 190                         GestureReader::Point::UpRight :
 191                         GestureReader::Point::DownLeft ;
 192         else
 193                 return (dx > 0) ?
 194                         GestureReader::Point::Right :
 195                         GestureReader::Point::Left ;
 196 }
 197
 198
 199 Gesture GestureReader::matchOne(QList<Gesture> gs)
 200 {
 201         QString myShape;
 202
 203 //      foreach (Point o, p->points) {
 204 //              DEBUG("\n\nPath " << "x,y  : "<<o.x<<","<<o.y<< "  len2 : "<<o.len2
 205 //                        << "  dir  : "<<StrokeCodes+o.direction * STROKECODELEN
 206 //                        << "  type : "<<TouchCodes+o.type * STROKECODELEN);
 207 //      }
 208
 209         int n = 0;
 210         do { // until simplified
 211
 212                 // This generates strokes and condenses the list at the same time.
 213                 myShape = generateStrokes();
 214
 215                 foreach (Gesture g, gs) {
 216                         // has to be one passed in as they are enriched with
 217                         // connection info
 218                         DEBUG("Compare g.shape(" << g.shape() <<") == '"<< myShape <<"'" );
 219                         if (g.shape() == myShape) {
 220                                 return g;
 221                         }
 222                 }
 223
 224                 // Now remove shortest paths
 225                 n = 0;
 226                 {
 227                         QMutableListIterator<Point> *i = new QMutableListIterator<Point>(p->points);
 228                         while (i->hasNext()) {
 229                                 if (i->next().type == Point::Move) {
 230                                         if (i->value().len2 == p->smallestStrokeLen) {
 231                                                 i->remove();
 232                                                 p->smallestStrokeLen = 0;  // reset to 0 so we only remove 1 path
 233                                         } else {
 234                                                 n++;                       // count undeleted paths
 235                                         }
 236                                 }
 237                         }
 238                         delete i;
 239                 }
 240
 241 //              foreach (Point o, p->points) {
 242 //                      DEBUG("\n\nPath " << "x,y  : "<<o.x<<","<<o.y<< "  len2 : "<<o.len2
 243 //                                << "  dir  : "<<StrokeCodes+o.direction * STROKECODELEN
 244 //                                << "  type : "<<TouchCodes+o.type * STROKECODELEN);
 245 //              }
 246
 247         } while (n >= 1); // simplify down to 1 stroke
 248
 249         return Gesture("");
 250 }
 251
 252 QString GestureReader::generateStrokes()
 253 {
 254         _ENTER;
 255         QString strokes;
 256         strokes = "";
 257         QList<Point> condensed;
 258         Point oo;
 259         p->smallestStrokeLen = 999999999;
 260         { // this block ensures the iterator goes out of scope and destructs before we delete the list
 261                 QListIterator<Point> o(p->points);
 262                 while (o.hasNext()) {
 263                         oo = o.next();
 264                         if (oo.type != Point::Move) {
 265                                 condensed.append(oo);
 266                                 // write out the touch code
 267 // Don't do multi-stroke .... yet...
 268 //                      strokes += TouchCodes+o.value().type * STROKECODELEN;
 269                         } else { // a Move
 270 //                              DEBUG("Condensing ... len:" << oo.len2);
 271                                 while (o.hasNext()
 272                                            && o.peekNext().type == Point::Move
 273                                            && o.peekNext().direction == oo.direction)
 274                                 {
 275                                         oo.len2 = sqr(oo.len2) + sqr(o.peekNext().len2); // join
 276                                         oo.len2 *= oo.len2;
 277 //                                      DEBUG("removing path len: " << o.peekNext().len2);
 278                                         o.next();
 279                                 }
 280 //                              DEBUG("Condensed ... len:" << oo.len2);
 281                                 condensed.append(oo);
 282                                 // write out the stroke
 283                                 strokes += StrokeCodes+oo.direction * STROKECODELEN;
 284                                 // Whilst we're here, keep an eye out for the shortest stroke
 285                                 if (oo.len2 && oo.len2 < p->smallestStrokeLen) p->smallestStrokeLen = oo.len2;
 286                         }
 287                 }
 288         }
 289         // replace the list
 290         p->points = condensed;
 291         DEBUG("Found " << strokes);
 292         return strokes;
 293 }