gengpro0.d

   1 /* Invisible Vector Library
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 // Protractor gesture recognizer, v0
  19 module iv.gengpro0 /*is aliced*/;
  20 private:
  21 import iv.alice;
  22
  23 // ////////////////////////////////////////////////////////////////////////// //
  24 import std.range;
  25
  26
  27 // ////////////////////////////////////////////////////////////////////////// //
  28 public alias GengFloat = float;
  29
  30
  31 // ////////////////////////////////////////////////////////////////////////// //
  32 public enum MinGestureMatch = 1.5;
  33
  34
  35 // ////////////////////////////////////////////////////////////////////////// //
  36 // DO NOT CHANGE!
  37 enum NormalizedPoints = 16; // the paper says that this is enough for protractor to work ok
  38 alias GengPatternPoints = GengFloat[NormalizedPoints*2];
  39
  40
  41 // ////////////////////////////////////////////////////////////////////////// //
  42 enum MinPointDistance = 4;
  43
  44
  45 // ////////////////////////////////////////////////////////////////////////// //
  46 // ignore possible overflows here
  47 import std.traits : isFloatingPoint;
  48
  49 GengFloat distance(FP) (in FP x0, in FP y0, in FP x1, in FP y1) if (isFloatingPoint!FP) {
  50   import std.math : sqrt;
  51   immutable dx = x1-x0;
  52   immutable dy = y1-y0;
  53   return sqrt(dx*dx+dy*dy);
  54 }
  55
  56
  57 // ////////////////////////////////////////////////////////////////////////// //
  58 public class PTGlyph {
  59 private:
  60   GengPatternPoints patpoints;
  61   GengFloat[] points; // [0]:x, [1]:y, [2]:x, [3]:y, etc...
  62   bool mNormalized; // true: `patpoints` is ok
  63   bool mOriented = true;
  64   string mName;
  65
  66   private static normBlkAttr (void* ptr) {
  67     import core.memory : GC;
  68     pragma(inline, true);
  69     if (ptr !is null && ptr is GC.addrOf(ptr)) GC.setAttr(ptr, GC.BlkAttr.NO_INTERIOR);
  70   }
  71
  72 public:
  73   this () nothrow @safe @nogc {}
  74   this (string aname, bool aoriented=true) nothrow @safe @nogc { mName = aname; mOriented = aoriented; }
  75   this (string aname, in GengPatternPoints apat, bool aoriented) nothrow @safe @nogc {
  76     mName = aname;
  77     patpoints[] = apat[];
  78     mNormalized = true;
  79     mOriented = aoriented;
  80   }
  81
  82 final:
  83   @property bool valid () const pure nothrow @safe @nogc { pragma(inline, true); return (mNormalized || points.length >= 4); }
  84   @property bool normalized () const pure nothrow @safe @nogc { pragma(inline, true); return mNormalized; }
  85   @property bool oriented () const pure nothrow @safe @nogc { pragma(inline, true); return mOriented; }
  86   @property void oriented (bool v) pure nothrow @safe @nogc { pragma(inline, true); if (!mNormalized) mOriented = v; } // can't be changed for normalized glyphs
  87
  88   @property string name () const pure nothrow @safe @nogc { pragma(inline, true); return mName; }
  89   @property void name (string v) @safe nothrow @nogc { pragma(inline, true); mName = v; }
  90
  91   usize length () const pure nothrow @safe @nogc { pragma(inline, true); return (mNormalized ? NormalizedPoints : points.length/2); }
  92   alias opDollar = length;
  93
  94   auto x (usize idx) const pure nothrow @safe @nogc {
  95     pragma(inline, true);
  96     if (!mNormalized) {
  97       return (idx*2 < points.length ? points[idx*2] : typeof(points[0]).nan);
  98     } else {
  99       return (idx < NormalizedPoints ? patpoints[idx*2] : typeof(points[0]).nan);
 100     }
 101   }
 102
 103   auto y (usize idx) const pure nothrow @safe @nogc {
 104     pragma(inline, true);
 105     if (!mNormalized) {
 106       return (idx*2 < points.length ? points[idx*2+1] : typeof(points[0]).nan);
 107     } else {
 108       return (idx < NormalizedPoints ? patpoints[idx*2+1] : typeof(points[0]).nan);
 109     }
 110   }
 111
 112   auto clear () nothrow {
 113     if (points.length) { points.length = 0; points.assumeSafeAppend; }
 114     mNormalized = false;
 115     mName = null;
 116     return this;
 117   }
 118
 119   auto clone () const {
 120     auto res = new PTGlyph(mName);
 121     res.mNormalized = mNormalized;
 122     res.mOriented = mOriented;
 123     res.patpoints[] = patpoints[];
 124     if (points.length > 0) {
 125       res.points = points.dup;
 126       normBlkAttr(res.points.ptr);
 127     }
 128     return res;
 129   }
 130
 131   auto addPoint (int x, int y) {
 132     if (mNormalized) throw new Exception("can't add point to normalized glyph");
 133     if (points.length > 0) {
 134       // check distance and don't add points that are too close to each other
 135       immutable lx = x-points[$-2], ly = y-points[$-1];
 136       if (lx*lx+ly*ly < MinPointDistance*MinPointDistance) return this;
 137     }
 138     auto optr = points.ptr;
 139     points ~= x;
 140     if (optr != points.ptr) { normBlkAttr(points.ptr); optr = points.ptr; }
 141     points ~= y;
 142     if (optr != points.ptr) { normBlkAttr(points.ptr); optr = points.ptr; }
 143     mNormalized = false;
 144     return this;
 145   }
 146
 147   auto normalize (bool dropPoints=true) {
 148     if (!mNormalized) {
 149       if (points.length < 4) throw new Exception("glyph must have at least two points");
 150       buildNormPoints(patpoints, points, mOriented);
 151       mNormalized = true;
 152       if (dropPoints) {
 153         points.length = 0;
 154         points.assumeSafeAppend;
 155       }
 156     }
 157     return this;
 158   }
 159
 160   // this: template
 161   GengFloat match (const(PTGlyph) sample) const pure nothrow @safe @nogc {
 162     if (sample is null || !sample.valid || !valid) return -GengFloat.infinity;
 163     if (mNormalized) {
 164       // this is normalized
 165       return match(patpoints, sample);
 166     } else {
 167       // this is not normalized
 168       GengPatternPoints v1 = void;
 169       buildNormPoints(v1, points, mOriented);
 170       return match(v1, sample);
 171     }
 172   }
 173
 174   string patpointsToString () {
 175     import std.string : format;
 176     return format("%s", patpoints);
 177   }
 178
 179 private:
 180   // this: template
 181   static GengFloat match (in GengPatternPoints tpl, const(PTGlyph) sample) pure nothrow @safe @nogc {
 182     if (sample is null || !sample.valid) return -GengFloat.infinity;
 183     if (sample.mNormalized) {
 184       return match(tpl, sample.patpoints);
 185     } else {
 186       GengPatternPoints spts = void;
 187       buildNormPoints(spts, sample.points, sample.mOriented);
 188       return match(tpl, spts);
 189     }
 190   }
 191
 192   static GengFloat match (in GengPatternPoints v0, in GengPatternPoints v1) pure nothrow @safe @nogc {
 193     return 1.0/optimalCosineDistance(v0, v1);
 194   }
 195
 196   static GengFloat optimalCosineDistance (in GengPatternPoints v0, in GengPatternPoints v1) pure nothrow @safe @nogc {
 197     import std.math : atan, acos, cos, sin;
 198     GengFloat a = 0.0, b = 0.0;
 199     foreach (immutable idx; 0..NormalizedPoints) {
 200       a += v0[idx*2+0]*v1[idx*2+0]+v0[idx*2+1]*v1[idx*2+1];
 201       b += v0[idx*2+0]*v1[idx*2+1]-v0[idx*2+1]*v1[idx*2+0];
 202     }
 203     immutable GengFloat angle = atan(b/a);
 204     return acos(a*cos(angle)+b*sin(angle));
 205   }
 206
 207   // glyph length (not point counter!)
 208   static GengFloat glyphLength (in GengFloat[] points) pure nothrow @safe @nogc {
 209     GengFloat res = 0.0;
 210     if (points.length >= 4) {
 211       // don't want to bring std.algo here
 212       GengFloat px = points[0], py = points[1];
 213       foreach (immutable idx; 2..points.length/2) {
 214         immutable cx = points[idx*2+0], cy = points[idx*2+1];
 215         res += distance(px, py, cx, cy);
 216         px = cx;
 217         py = cy;
 218       }
 219     }
 220     return res;
 221   }
 222
 223   static void resample (out GengPatternPoints ptres, in GengFloat[] points) pure @safe nothrow @nogc {
 224     assert(points.length >= 4);
 225     immutable GengFloat I = glyphLength(points)/(NormalizedPoints-1); // interval length
 226     GengFloat D = 0.0;
 227     GengFloat prx = points[0];
 228     GengFloat pry = points[1];
 229     // add first point as-is
 230     ptres[0] = prx;
 231     ptres[1] = pry;
 232     usize ptpos = 2, oppos = 2;
 233     while (oppos < points.length) {
 234       immutable GengFloat cx = points[oppos], cy = points[oppos+1];
 235       immutable d = distance(prx, pry, cx, cy);
 236       if (D+d >= I) {
 237         immutable dd = (I-D)/d;
 238         immutable qx = prx+dd*(cx-prx);
 239         immutable qy = pry+dd*(cy-pry);
 240         assert(ptpos < NormalizedPoints*2);
 241         ptres[ptpos++] = qx;
 242         ptres[ptpos++] = qy;
 243         // use 'q' as previous point
 244         prx = qx;
 245         pry = qy;
 246         D = 0.0;
 247       } else {
 248         D += d;
 249         prx = cx;
 250         pry = cy;
 251         oppos += 2;
 252       }
 253     }
 254     // somtimes we fall a rounding-error short of adding the last point, so add it if so
 255     if (ptpos/2 == NormalizedPoints-1) {
 256       ptres[ptpos++] = points[$-2];
 257       ptres[ptpos++] = points[$-1];
 258     }
 259     assert(ptpos == NormalizedPoints*2);
 260   }
 261
 262   // stroke is not required to be centered, but it must be resampled
 263   static void vectorize (out GengPatternPoints vres, in GengPatternPoints ptx, bool orientationSensitive)
 264   pure nothrow @safe @nogc
 265   {
 266     import std.math : atan2, cos, sin, floor, sqrt, PI;
 267     GengPatternPoints pts;
 268     GengFloat indAngle, delta;
 269     GengFloat cx = 0.0, cy = 0.0;
 270     // center it
 271     foreach (immutable idx; 0..NormalizedPoints) {
 272       cx += ptx[idx*2+0];
 273       cy += ptx[idx*2+1];
 274     }
 275     cx /= NormalizedPoints;
 276     cy /= NormalizedPoints;
 277     foreach (immutable idx; 0..NormalizedPoints) {
 278       pts[idx*2+0] = ptx[idx*2+0]-cx;
 279       pts[idx*2+1] = ptx[idx*2+1]-cy;
 280     }
 281     indAngle = atan2(pts[1], pts[0]); // always must be done for centered stroke
 282     if (orientationSensitive) {
 283       immutable base_orientation = (PI/4.0)*floor((indAngle+PI/8.0)/(PI/4.0));
 284       delta = base_orientation-indAngle;
 285     } else {
 286       delta = indAngle;
 287     }
 288     immutable GengFloat cosd = cos(delta);
 289     immutable GengFloat sind = sin(delta);
 290     GengFloat sum = 0.0;
 291     foreach (immutable idx; 0..NormalizedPoints) {
 292       immutable nx = pts[idx*2+0]*cosd-pts[idx*2+1]*sind;
 293       immutable ny = pts[idx*2+1]*cosd+pts[idx*2+0]*sind;
 294       vres[idx*2+0] = nx;
 295       vres[idx*2+1] = ny;
 296       sum += nx*nx+ny*ny;
 297     }
 298     immutable GengFloat magnitude = sqrt(sum);
 299     foreach (immutable idx; 0..NormalizedPoints*2) vres[idx] /= magnitude;
 300   }
 301
 302   static void buildNormPoints (out GengPatternPoints vres, in GengFloat[] points, bool orientationSensitive)
 303   pure nothrow @safe @nogc
 304   {
 305     assert(points.length >= 4);
 306     GengPatternPoints tmp = void;
 307     resample(tmp, points);
 308     vectorize(vres, tmp, orientationSensitive);
 309   }
 310
 311 public:
 312   PTGlyph findMatch(R) (auto ref R grng, GengFloat* outscore=null) const
 313   if (isInputRange!R && !isInfinite!R && is(ElementType!R : PTGlyph))
 314   {
 315     GengFloat bestScore = -GengFloat.infinity;
 316     PTGlyph res = null;
 317     if (outscore !is null) *outscore = GengFloat.nan;
 318     if (valid) {
 319       // build normalized `this` glyph in pts
 320       GengPatternPoints pts = void;
 321       if (this.mNormalized) {
 322         pts[] = this.patpoints[];
 323       } else {
 324         buildNormPoints(pts, points, mOriented);
 325       }
 326       while (!grng.empty) {
 327         auto gs = grng.front;
 328         grng.popFront;
 329         if (gs is null || !gs.valid) continue;
 330         GengFloat score = match(pts, gs);
 331         if (score >= MinGestureMatch && score > bestScore) {
 332           bestScore = score;
 333           res = gs;
 334         }
 335       }
 336     }
 337     if (res !is null && outscore !is null) *outscore = bestScore;
 338     return res;
 339   }
 340 }
 341
 342
 343 // ////////////////////////////////////////////////////////////////////////// //
 344 import iv.vfs;
 345
 346
 347 public void gstLibLoad(R) (auto ref R orng, VFile st) if (isOutputRange!(R, PTGlyph)) {
 348   auto sign = st.readNum!ulong();
 349   if (sign != 0x304244525450384BUL && sign != 0x314244525450384BUL) throw new Exception("invalid library signature"); // "K8PTRDB0"/1
 350   ubyte ver = ((sign>>56)-0x30)&0xff;
 351   auto cnt = st.readNum!uint();
 352   if (cnt > 0x7fff_ffff) throw new Exception("too many glyphs");
 353   if (cnt == 0) return;
 354   foreach (immutable idx; 0..cnt) {
 355     // name
 356     auto len = st.readNum!uint();
 357     if (len > 1024) throw new Exception("glyph name too long");
 358     string name;
 359     if (len > 0) {
 360       auto buf = new char[](len);
 361       st.rawReadExact(buf);
 362       name = cast(string)buf; // it is safe to cast here
 363     }
 364     // template
 365     GengPatternPoints pts = void;
 366     foreach (ref pt; pts) {
 367       pt = st.readNum!float();
 368       if (pt != pt) throw new Exception("invalid number"); // nan check
 369     }
 370     bool oriented = true;
 371     if (ver == 1) oriented = (st.readNum!ubyte != 0);
 372     auto g = new PTGlyph(name, pts, oriented);
 373     put(orng, g);
 374   }
 375 }
 376
 377
 378 public PTGlyph[] gstLibLoad (VFile fl) {
 379   static struct ORng {
 380     PTGlyph[] gls;
 381     void put (PTGlyph g) nothrow { if (g !is null && g.valid) gls ~= g; }
 382   }
 383   auto r = ORng();
 384   gstLibLoad(r, fl);
 385   return (r.gls.length ? r.gls : null);
 386 }
 387
 388
 389 // ////////////////////////////////////////////////////////////////////////// //
 390 public void gstLibSave(R) (VFile st, auto ref R grng) if (isInputRange!R && !isInfinite!R && is(ElementType!R : PTGlyph)) {
 391   st.writeNum!ulong(0x314244525450384BuL); // "K8PTRDB1"
 392   static if (hasLength!R) {
 393     auto cnt = grng.length;
 394     if (cnt > 0x7fff_ffff) throw new Exception("too many glyphs");
 395     st.writeNum!uint(cast(uint)cnt);
 396   } else {
 397     usize cnt = 0;
 398     auto cntpos = st.tell;
 399     st.writeNum!uint(0);
 400   }
 401   while (!grng.empty) {
 402     auto g = grng.front;
 403     grng.popFront;
 404     if (g is null || !g.valid) throw new Exception("can't save invalid glyph");
 405     // name
 406     if (g.name.length > 1024) throw new Exception("glyph name too long");
 407     st.writeNum!uint(cast(uint)g.name.length);
 408     st.rawWriteExact(g.name);
 409     // points
 410     GengPatternPoints pts = void;
 411     if (g.mNormalized) {
 412       pts[] = g.patpoints[];
 413     } else {
 414       g.buildNormPoints(pts, g.points, g.mOriented);
 415     }
 416     foreach (immutable pt; pts) st.writeNum!float(cast(float)pt);
 417     st.writeNum!ubyte(g.mOriented ? 1 : 0);
 418     static if (!hasLength!R) {
 419       if (cnt == 0x7fff_ffff) throw new Exception("too many glyphs");
 420       ++cnt;
 421     }
 422   }
 423   static if (!hasLength!R) {
 424     auto cpos = st.tell;
 425     st.seek(cntpos);
 426     st.writeNum!uint(cast(uint)cnt);
 427     st.seek(cpos);
 428   }
 429 }