git.maemo.org Git - him-cellwriter/blob - src/stroke.c

   1
   2 /*
   3
   4 cellwriter -- a character recognition input method
   5 Copyright (C) 2007 Michael Levin <risujin@risujin.org>
   6
   7 This program is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU General Public License
   9 as published by the Free Software Foundation; either version 2
  10 of the License, or (at your option) any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  20
  21 */
  22
  23 #include "config.h"
  24 #include <string.h>
  25 #include <math.h>
  26 #include <gtk/gtk.h>
  27 #include "common.h"
  28 #include "recognize.h"
  29
  30 /*
  31         Stroke functions
  32 */
  33
  34 /* Distance from the line formed by the two neighbors of a point, which, if
  35    not exceeded, will cause the point to be culled during simplification */
  36 #define SIMPLIFY_THRESHOLD 0.5
  37
  38 /* Granularity of stroke point array in points */
  39 #define POINTS_GRAN 64
  40
  41 /* Size of a stroke structure */
  42 #define STROKE_SIZE(size) (sizeof (Stroke) + (size) * sizeof (Point))
  43
  44 void process_stroke(Stroke *stroke)
  45 /* Generate cached parameters of a stroke */
  46 {
  47         int i;
  48         float distance;
  49
  50         if (stroke->processed)
  51                 return;
  52         stroke->processed = TRUE;
  53
  54         /* Dot strokes */
  55         if (stroke->len == 1) {
  56                 vec2_set(&stroke->center, stroke->points[0].x,
  57                          stroke->points[0].y);
  58                 stroke->spread = 0.f;
  59                 return;
  60         }
  61
  62         stroke->min_x = stroke->max_x = stroke->points[0].x;
  63         stroke->min_y = stroke->max_y = stroke->points[0].y;
  64         for (i = 0, distance = 0.; i < stroke->len - 1; i++) {
  65                 Vec2 v;
  66                 float weight;
  67
  68                 /* Angle */
  69                 vec2_set(&v, stroke->points[i + 1].x - stroke->points[i].x,
  70                          stroke->points[i + 1].y - stroke->points[i].y);
  71                 stroke->points[i].angle = vec2_angle(&v);
  72
  73                 /* Point contribution to spread */
  74                 if (stroke->points[i + 1].x < stroke->min_x)
  75                         stroke->min_x = stroke->points[i + 1].x;
  76                 if (stroke->points[i + 1].y < stroke->min_y)
  77                         stroke->min_y = stroke->points[i + 1].y;
  78                 if (stroke->points[i + 1].x > stroke->max_x)
  79                         stroke->max_x = stroke->points[i + 1].x;
  80                 if (stroke->points[i + 1].y > stroke->max_y)
  81                         stroke->max_y = stroke->points[i + 1].y;
  82
  83                 /* Segment contribution to center */
  84                 vec2_set(&v, stroke->points[i + 1].x - stroke->points[i].x,
  85                          stroke->points[i + 1].y - stroke->points[i].y);
  86                 distance += weight = vec2_mag(&v);
  87                 vec2_set(&v, stroke->points[i + 1].x + stroke->points[i].x,
  88                          stroke->points[i + 1].y + stroke->points[i].y);
  89                 vec2_scale(&v, &v, weight / 2.);
  90                 vec2_sum(&stroke->center, &stroke->center, &v);
  91         }
  92         vec2_scale(&stroke->center, &stroke->center, 1. / distance);
  93         stroke->points[i].angle = stroke->points[i - 1].angle;
  94         stroke->distance = distance;
  95
  96         /* Stroke spread */
  97         stroke->spread = stroke->max_x - stroke->min_x;
  98         if (stroke->max_y - stroke->min_y > stroke->spread)
  99                 stroke->spread = stroke->max_y - stroke->min_y;
 100 }
 101
 102 void clear_stroke(Stroke *stroke)
 103 /* Clear cached parameters */
 104 {
 105         int size;
 106
 107         size = stroke->size;
 108         memset(stroke, 0, sizeof (*stroke));
 109         stroke->size = size;
 110 }
 111
 112 Stroke *stroke_new(int size)
 113 /* Allocate memory for a new stroke */
 114 {
 115         Stroke *stroke;
 116
 117         if (size < POINTS_GRAN)
 118                 size = POINTS_GRAN;
 119         stroke = g_malloc(STROKE_SIZE(size));
 120         stroke->size = size;
 121         clear_stroke(stroke);
 122         return stroke;
 123 }
 124
 125 static void reverse_copy_points(Point *dest, const Point *src, int len)
 126 {
 127         int i;
 128
 129         for (i = 0; i < len; i++) {
 130                 ANGLE angle = 0;
 131
 132                 if (i < len - 1)
 133                         angle = src[len - i - 2].angle + ANGLE_PI;
 134                 dest[i] = src[len - i - 1];
 135                 dest[i].angle = angle;
 136         }
 137 }
 138
 139 Stroke *stroke_clone(const Stroke *src, int reverse)
 140 {
 141         Stroke *stroke;
 142
 143         if (!src)
 144                 return NULL;
 145         stroke = stroke_new(src->size);
 146         if (!reverse)
 147                 memcpy(stroke, src, STROKE_SIZE(src->size));
 148         else {
 149                 memcpy(stroke, src, sizeof (Stroke));
 150                 reverse_copy_points(stroke->points, src->points, src->len);
 151         }
 152         return stroke;
 153 }
 154
 155 void stroke_free(Stroke *stroke)
 156 {
 157         g_free(stroke);
 158 }
 159
 160 void glue_stroke(Stroke **pa, const Stroke *b, int reverse)
 161 /* Glue B onto the end of A preserving processed properties */
 162 {
 163         Vec2 glue_seg, glue_center, b_center;
 164         Point start;
 165         Stroke *a;
 166         float glue_mag;
 167
 168         a = *pa;
 169
 170         /* If there is no stroke to glue to, just copy */
 171         if (!a || a->len < 1) {
 172                 if (a->len < 1)
 173                         stroke_free(a);
 174                 *pa = stroke_clone(b, reverse);
 175                 return;
 176         }
 177
 178         /* Allocate memory */
 179         if (a->size < a->len + b->len) {
 180                 a->size = a->len + b->len;
 181                 a = g_realloc(a, STROKE_SIZE(a->size));
 182         }
 183
 184         /* Gluing two strokes creates a new segment between them */
 185         start = reverse ? b->points[b->len - 1] : b->points[0];
 186         vec2_set(&glue_seg, start.x - a->points[a->len - 1].x,
 187                  start.y - a->points[a->len - 1].y);
 188         vec2_set(&glue_center, (start.x + a->points[a->len - 1].x) / 2,
 189                  (start.y + a->points[a->len - 1].y) / 2);
 190         glue_mag = vec2_mag(&glue_seg);
 191
 192         /* Compute new spread */
 193         if (b->min_x < a->min_x)
 194                 a->min_x = b->min_x;
 195         if (b->max_x > a->max_x)
 196                 a->max_x = b->max_x;
 197         if (b->min_y < a->min_y)
 198                 a->min_y = b->min_y;
 199         if (b->max_y > a->max_y)
 200                 a->max_y = b->max_y;
 201         a->spread = a->max_x - a->min_x;
 202         if (a->max_y - a->min_y > a->spread)
 203                 a->spread = a->max_y - a->min_y;
 204
 205         /* Compute new center point */
 206         vec2_scale(&a->center, &a->center, a->distance);
 207         vec2_scale(&b_center, &b->center, b->distance);
 208         vec2_scale(&glue_center, &glue_center, glue_mag);
 209         vec2_set(&a->center, a->center.x + b_center.x + glue_center.x,
 210                  a->center.y + b_center.y + glue_center.y);
 211         vec2_scale(&a->center, &a->center,
 212                    1.f / (a->distance + b->distance + glue_mag));
 213
 214         /* Copy points */
 215         if (!reverse || b->len < 2)
 216                 memcpy(a->points + a->len, b->points, b->len * sizeof (Point));
 217         else
 218                 reverse_copy_points(a->points + a->len, b->points, b->len);
 219
 220         a->points[a->len - 1].angle = vec2_angle(&glue_seg);
 221         a->distance += glue_mag + b->distance;
 222         a->len += b->len;
 223         *pa = a;
 224 }
 225
 226 void draw_stroke(Stroke **ps, int x, int y)
 227 /* Add a point in scaled coordinates to a stroke */
 228 {
 229         /* Create a new stroke if necessary */
 230         if (!(*ps))
 231                 *ps = stroke_new(0);
 232
 233         /* If we run out of room, resample the stroke to fit */
 234         if ((*ps)->len >= POINTS_MAX) {
 235                 Stroke *new_stroke;
 236
 237                 new_stroke = sample_stroke(NULL, *ps, POINTS_MAX - POINTS_GRAN,
 238                                            POINTS_MAX);
 239                 stroke_free(*ps);
 240                 *ps = new_stroke;
 241         }
 242
 243         /* Range limits */
 244         if (x <= -SCALE / 2)
 245                 x = -SCALE / 2 + 1;
 246         if (x >= SCALE / 2)
 247                 x = SCALE / 2 - 1;
 248         if (y <= -SCALE / 2)
 249                 y = -SCALE / 2 + 1;
 250         if (y >= SCALE / 2)
 251                 y = SCALE / 2 - 1;
 252
 253         /* Do we need more memory? */
 254         if ((*ps)->len >= (*ps)->size) {
 255                 (*ps)->size += POINTS_GRAN;
 256                 *ps = g_realloc(*ps, STROKE_SIZE((*ps)->size));
 257         }
 258
 259         (*ps)->points[(*ps)->len].x = x;
 260         (*ps)->points[(*ps)->len++].y = y;
 261 }
 262
 263 void smooth_stroke(Stroke *s)
 264 /* Smooth stroke points by moving each point halfway toward the line between
 265    its two neighbors */
 266 {
 267         int i, last_x, last_y;
 268
 269         last_x = s->points[0].x;
 270         last_y = s->points[0].y;
 271         for (i = 1; i < s->len - 1; i++) {
 272                 Vec2 a, b, c, m, ab, ac, am;
 273
 274                 if (last_x == s->points[i + 1].x &&
 275                     last_y == s->points[i + 1].y) {
 276                         last_x = s->points[i].x;
 277                         last_y = s->points[i].y;
 278                         continue;
 279                 }
 280                 vec2_set(&a, last_x, last_y);
 281                 vec2_set(&b, s->points[i].x, s->points[i].y);
 282                 vec2_set(&c, s->points[i + 1].x, s->points[i + 1].y);
 283                 vec2_sub(&ac, &c, &a);
 284                 vec2_sub(&ab, &b, &a);
 285                 vec2_proj(&am, &ab, &ac);
 286                 vec2_sum(&m, &a, &am);
 287                 vec2_avg(&b, &b, &m, 0.5);
 288                 last_x = s->points[i].x;
 289                 last_y = s->points[i].y;
 290                 s->points[i].x = b.x + 0.5;
 291                 s->points[i].y = b.y + 0.5;
 292         }
 293 }
 294
 295 void simplify_stroke(Stroke *s)
 296 /* Remove excess points between neighbors */
 297 {
 298         int i;
 299
 300         for (i = 1; i < s->len - 1; i++) {
 301                 Vec2 l, w;
 302                 double dist, mag, dot;
 303
 304                 /* Vector l is a unit vector from point i - 1 to point i + 1 */
 305                 vec2_set(&l, s->points[i - 1].x - s->points[i + 1].x,
 306                          s->points[i - 1].y - s->points[i + 1].y);
 307                 mag = vec2_norm(&l, &l);
 308
 309                 /* Vector w is a vector from point i - 1 to point i */
 310                 vec2_set(&w, s->points[i - 1].x - s->points[i].x,
 311                          s->points[i - 1].y - s->points[i].y);
 312
 313                 /* Do not touch mid points that are not in between their
 314                    neighbors */
 315                 dot = vec2_dot(&l, &w);
 316                 if (dot < 0. || dot > mag)
 317                         continue;
 318
 319                 /* Remove any points that are less than some threshold away
 320                    from their neighbor points */
 321                 dist = vec2_cross(&w, &l);
 322                 if (dist < SIMPLIFY_THRESHOLD && dist > -SIMPLIFY_THRESHOLD) {
 323                         memmove(s->points + i, s->points + i + 1,
 324                                 (--s->len - i) * sizeof (*s->points));
 325                         i--;
 326                 }
 327         }
 328 }
 329
 330 void dump_stroke(Stroke *stroke)
 331 {
 332         int i;
 333
 334         /* Print stats */
 335         g_message("Stroke data --");
 336         g_debug("Distance: %g", stroke->distance);
 337         g_debug("  Center: (%g, %g)", stroke->center.x, stroke->center.y);
 338         g_debug("  Spread: %d", stroke->spread);
 339         g_message("%d points --", stroke->len);
 340
 341         /* Print point data */
 342         for (i = 0; i < stroke->len; i++)
 343                 g_debug("%3d: (%4d,%4d)\n",
 344                         i, stroke->points[i].x, stroke->points[i].y);
 345 }
 346
 347 Stroke *sample_stroke(Stroke *out, Stroke *in, int points, int size)
 348 /* Recreate the stroke by sampling at regular distance intervals.
 349    Sampled strokes always have angle data. */
 350 {
 351         Vec2 v;
 352         double dist_i, dist_j, dist_per;
 353         int i, j, len;
 354
 355         if (!in || in->len < 1) {
 356                 g_warning("Attempted to sample an invalid stroke");
 357                 return NULL;
 358         }
 359
 360         /* Check ranges */
 361         if (size >= POINTS_MAX) {
 362                 g_warning("Stroke sized to maximum length possible");
 363                 size = POINTS_MAX;
 364         }
 365         if (points >= POINTS_MAX) {
 366                 g_warning("Stroke sampled to maximum length possible");
 367                 points = POINTS_MAX;
 368         }
 369         if (size < 1)
 370                 size = 1;
 371         if (points < 1)
 372                 points = 1;
 373
 374         /* Allocate memory and copy cached data */
 375         if (!out)
 376                 out = g_malloc(STROKE_SIZE(size));
 377         out->size = size;
 378         len = out->size < points ? out->size - 1 : points - 1;
 379         out->len = len + 1;
 380         out->spread = in->spread;
 381         out->center = in->center;
 382
 383         /* Special case for sampling a single point */
 384         if (in->len <= 1 || points <= 1) {
 385                 for (i = 0; i < len + 1; i++)
 386                         out->points[i] = in->points[0];
 387                 out->distance = 0.;
 388                 return out;
 389         }
 390
 391         dist_per = in->distance / (points - 1);
 392         out->distance = in->distance;
 393         vec2_set(&v, in->points[1].x - in->points[0].x,
 394                  in->points[1].y - in->points[0].y);
 395         dist_j = vec2_mag(&v);
 396         dist_i = dist_per;
 397         out->points[0] = in->points[0];
 398         for (i = 1, j = 0; i < len; i++) {
 399
 400                 /* Advance our position */
 401                 while (dist_i >= dist_j) {
 402                         if (j >= in->len - 2)
 403                                 goto finish;
 404                         dist_i -= dist_j;
 405                         j++;
 406                         vec2_set(&v, in->points[j + 1].x - in->points[j].x,
 407                                  in->points[j + 1].y - in->points[j].y);
 408                         dist_j = vec2_mag(&v);
 409                 }
 410
 411                 /* Interpolate points */
 412                 out->points[i].x = in->points[j].x +
 413                                    (in->points[j + 1].x - in->points[j].x) *
 414                                    dist_i / dist_j;
 415                 out->points[i].y = in->points[j].y +
 416                                    (in->points[j + 1].y - in->points[j].y) *
 417                                    dist_i / dist_j;
 418                 out->points[i].angle = in->points[j].angle;
 419
 420                 dist_i += dist_per;
 421         }
 422 finish:
 423         for (; i < len + 1; i++)
 424                 out->points[i] = in->points[j + 1];
 425
 426         return out;
 427 }
 428
 429 void sample_strokes(Stroke *a, Stroke *b, Stroke **as, Stroke **bs)
 430 /* Sample multiple strokes to equal lengths */
 431 {
 432         double dist;
 433         int points;
 434
 435         /* Find the sample length */
 436         dist = a->distance;
 437         if (b->distance > dist)
 438                 dist = b->distance;
 439         points = 1 + dist / FINE_RESOLUTION;
 440         if (points > POINTS_MAX)
 441                 points = POINTS_MAX;
 442
 443         *as = sample_stroke(NULL, a, points, points);
 444         *bs = sample_stroke(NULL, b, points, points);
 445 }
 446