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