src/xo-shapes.c

   1 /*
   2  *  This program is free software; you can redistribute it and/or
   3  *  modify it under the terms of the GNU General Public
   4  *  License as published by the Free Software Foundation; either
   5  *  version 2 of the License, or (at your option) any later version.
   6  *
   7  *  This software is distributed in the hope that it will be useful,
   8  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  10  *  General Public License for more details.
  11  *
  12  *  You should have received a copy of the GNU General Public License
  13  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #  include <config.h>
  18 #endif
  19
  20 #include <math.h>
  21 #include <string.h>
  22 #include <gtk/gtk.h>
  23 #include <libgnomecanvas/libgnomecanvas.h>
  24
  25 #include "xournal.h"
  26 #include "xo-shapes.h"
  27 #include "xo-paint.h"
  28
  29 typedef struct Inertia {
  30   double mass, sx, sy, sxx, sxy, syy;
  31 } Inertia;
  32
  33 typedef struct RecoSegment {
  34   struct Item *item;
  35   int startpt, endpt;
  36   double xcenter, ycenter, angle, radius;
  37   double x1, y1, x2, y2;
  38   gboolean reversed;
  39 } RecoSegment;
  40
  41 struct RecoSegment recognizer_queue[MAX_POLYGON_SIDES+1];
  42 int recognizer_queue_length;
  43 struct UndoItem *last_item_checker; // check if queue is stale
  44
  45 void reset_recognizer(void)
  46 {
  47   recognizer_queue_length = 0;
  48   last_item_checker = NULL;
  49 }
  50
  51 /* compute mass and moments of a stroke */
  52
  53 void incr_inertia(double *pt, struct Inertia *s, int coef)
  54 {
  55   double dm;
  56   dm = coef*hypot(pt[2]-pt[0], pt[3]-pt[1]);
  57   s->mass += dm;
  58   s->sx += dm*pt[0];
  59   s->sy += dm*pt[1];
  60   s->sxx += dm*pt[0]*pt[0];
  61   s->syy += dm*pt[1]*pt[1];
  62   s->sxy += dm*pt[0]*pt[1];
  63 }
  64
  65 void calc_inertia(double *pt, int start, int end, struct Inertia *s)
  66 {
  67   int i;
  68
  69   s->mass = s->sx = s->sy = s->sxx = s->sxy = s->syy = 0.;
  70   for (i=start, pt+=2*start; i<end; i++, pt+=2) incr_inertia(pt, s, 1);
  71 }
  72
  73 /* compute normalized quantities */
  74
  75 inline double center_x(struct Inertia s)
  76 {
  77   return s.sx/s.mass;
  78 }
  79
  80 inline double center_y(struct Inertia s)
  81 {
  82   return s.sy/s.mass;
  83 }
  84
  85 inline double I_xx(struct Inertia s)
  86 {
  87   if (s.mass <= 0.) return 0.;
  88   return (s.sxx - s.sx*s.sx/s.mass)/s.mass;
  89 }
  90
  91 inline double I_xy(struct Inertia s)
  92 {
  93   if (s.mass <= 0.) return 0.;
  94   return (s.sxy - s.sx*s.sy/s.mass)/s.mass;
  95 }
  96
  97 inline double I_yy(struct Inertia s)
  98 {
  99   if (s.mass <= 0.) return 0.;
 100   return (s.syy - s.sy*s.sy/s.mass)/s.mass;
 101 }
 102
 103 inline double I_rad(struct Inertia s)
 104 {
 105   double ixx = I_xx(s), iyy = I_yy(s);
 106   if (ixx+iyy <= 0.) return 0.;
 107   return sqrt(ixx+iyy);
 108 }
 109
 110 inline double I_det(struct Inertia s)
 111 {
 112   double ixx = I_xx(s), iyy = I_yy(s), ixy = I_xy(s);
 113   if (s.mass <= 0.) return 0.;
 114   if (ixx+iyy <= 0.) return 0.;
 115   return 4*(ixx*iyy-ixy*ixy)/(ixx+iyy)/(ixx+iyy);
 116 }
 117
 118 /* check if something is a polygonal line with at most nsides sides */
 119
 120 int find_polygonal(double *pt, int start, int end, int nsides, int *breaks, struct Inertia *ss)
 121 {
 122   struct Inertia s, s1, s2;
 123   int k, i1, i2, n1, n2;
 124   double det1, det2;
 125
 126   if (end == start) return 0; // no way
 127   if (nsides <= 0) return 0;
 128   if (end-start<5) nsides = 1; // too small for a polygon
 129
 130   // look for a linear piece that's big enough
 131   for (k=0; k<nsides; k++) {
 132     i1 = start + (k*(end-start))/nsides;
 133     i2 = start + ((k+1)*(end-start))/nsides;
 134     calc_inertia(pt, i1, i2, &s);
 135     if (I_det(s) < LINE_MAX_DET) break;
 136   }
 137   if (k==nsides) return 0; // failed!
 138
 139   // grow the linear piece we found
 140   while (1) {
 141     if (i1>start) {
 142       s1 = s;
 143       incr_inertia(pt+2*(i1-1), &s1, 1);
 144       det1 = I_det(s1);
 145     }
 146     else det1 = 1.;
 147     if (i2<end) {
 148       s2 = s;
 149       incr_inertia(pt+2*i2, &s2, 1);
 150       det2 = I_det(s2);
 151     }
 152     else det2 = 1.;
 153     if (det1<det2 && det1<LINE_MAX_DET) { i1--; s=s1; }
 154     else if (det2<det1 && det2<LINE_MAX_DET) { i2++; s=s2; }
 155     else break;
 156   }
 157
 158   if (i1>start) {
 159     n1 = find_polygonal(pt, start, i1, (i2==end)?(nsides-1):(nsides-2), breaks, ss);
 160     if (n1 == 0) return 0; // it doesn't work
 161   }
 162   else n1 = 0;
 163
 164   breaks[n1] = i1;
 165   breaks[n1+1] = i2;
 166   ss[n1] = s;
 167
 168   if (i2<end) {
 169     n2 = find_polygonal(pt, i2, end, nsides-n1-1, breaks+n1+1, ss+n1+1);
 170     if (n2 == 0) return 0;
 171   }
 172   else n2 = 0;
 173
 174   return n1+n2+1;
 175 }
 176
 177 /* improve on the polygon found by find_polygonal() */
 178
 179 void optimize_polygonal(double *pt, int nsides, int *breaks, struct Inertia *ss)
 180 {
 181   int i;
 182   double cost, newcost;
 183   struct Inertia s1, s2;
 184   gboolean improved;
 185
 186   for (i=1; i<nsides; i++) {
 187     // optimize break between sides i and i+1
 188     cost = I_det(ss[i-1])*I_det(ss[i-1])+I_det(ss[i])*I_det(ss[i]);
 189     s1 = ss[i-1]; s2 = ss[i];
 190     improved = FALSE;
 191     while (breaks[i]>breaks[i-1]+1) {
 192       // try moving the break to the left
 193       incr_inertia(pt+2*(breaks[i]-1), &s1, -1);
 194       incr_inertia(pt+2*(breaks[i]-1), &s2, 1);
 195       newcost = I_det(s1)*I_det(s1)+I_det(s2)*I_det(s2);
 196       if (newcost >= cost) break;
 197       improved = TRUE;
 198       cost = newcost;
 199       breaks[i]--;
 200       ss[i-1] = s1;
 201       ss[i] = s2;
 202     }
 203     if (improved) continue;
 204     s1 = ss[i-1]; s2 = ss[i];
 205     while (breaks[i]<breaks[i+1]-1) {
 206       // try moving the break to the right
 207       incr_inertia(pt+2*breaks[i], &s1, 1);
 208       incr_inertia(pt+2*breaks[i], &s2, -1);
 209       newcost = I_det(s1)*I_det(s1)+I_det(s2)*I_det(s2);
 210       if (newcost >= cost) break;
 211       cost = newcost;
 212       breaks[i]++;
 213       ss[i-1] = s1;
 214       ss[i] = s2;
 215     }
 216   }
 217 }
 218
 219 /* find the geometry of a recognized segment */
 220
 221 void get_segment_geometry(double *pt, int start, int end, struct Inertia *s, struct RecoSegment *r)
 222 {
 223   double a, b, c, lmin, lmax, l;
 224   int i;
 225
 226   r->xcenter = center_x(*s);
 227   r->ycenter = center_y(*s);
 228   a = I_xx(*s); b = I_xy(*s); c = I_yy(*s);
 229   /* max angle for inertia quadratic form solves: tan(2t) = 2b/(a-c) */
 230   r->angle = atan2(2*b, a-c)/2;
 231   r->radius = sqrt(3*(a+c));
 232
 233   lmin = lmax = 0.;
 234   for (i=start, pt+=2*start; i<=end; i++, pt+=2) {
 235     l = (pt[0]-r->xcenter)*cos(r->angle)+(pt[1]-r->ycenter)*sin(r->angle);
 236     if (l<lmin) lmin = l;
 237     if (l>lmax) lmax = l;
 238   }
 239   r->x1 = r->xcenter + lmin*cos(r->angle);
 240   r->y1 = r->ycenter + lmin*sin(r->angle);
 241   r->x2 = r->xcenter + lmax*cos(r->angle);
 242   r->y2 = r->ycenter + lmax*sin(r->angle);
 243 }
 244
 245 /* test if we have a circle; inertia has been precomputed by caller */
 246
 247 double score_circle(double *pt, int start, int end, struct Inertia *s)
 248 {
 249   double sum, x0, y0, r0, dm, deltar;
 250   int i;
 251
 252   if (s->mass == 0.) return 0;
 253   sum = 0.;
 254   x0 = center_x(*s); y0 = center_y(*s); r0 = I_rad(*s);
 255   for (i=start, pt+=2*start; i<end; i++, pt+=2) {
 256     dm = hypot(pt[2]-pt[0], pt[3]-pt[1]);
 257     deltar = hypot(pt[0]-x0, pt[1]-y0) - r0;
 258     sum += dm * fabs(deltar);
 259   }
 260   return sum/(s->mass*r0);
 261 }
 262
 263 /* replace strokes by various shapes */
 264
 265 void make_circle_shape(double x0, double y0, double r)
 266 {
 267   int npts, i;
 268   struct Item *item;
 269   struct UndoErasureData *erasure;
 270
 271   npts = (int)(2*r);
 272   if (npts<12) npts = 12; // min. number of points
 273   realloc_cur_path(npts+1);
 274   ui.cur_path.num_points = npts+1;
 275   for (i=0;i<=npts; i++) {
 276     ui.cur_path.coords[2*i] = x0 + r*cos((2*M_PI*i)/npts);
 277     ui.cur_path.coords[2*i+1] = y0 + r*sin((2*M_PI*i)/npts);
 278   }
 279 }
 280
 281 void calc_edge_isect(struct RecoSegment *r1, struct RecoSegment *r2, double *pt)
 282 {
 283   double t;
 284   t = (r2->xcenter - r1->xcenter) * sin(r2->angle) -
 285       (r2->ycenter - r1->ycenter) * cos(r2->angle);
 286   t /= sin(r2->angle-r1->angle);
 287   pt[0] = r1->xcenter + t*cos(r1->angle);
 288   pt[1] = r1->ycenter + t*sin(r1->angle);
 289 }
 290
 291 void remove_recognized_strokes(struct RecoSegment *rs, int num_old_items)
 292 {
 293   struct Item *old_item;
 294   int i, shift;
 295   struct UndoErasureData *erasure;
 296
 297   old_item = NULL;
 298   prepare_new_undo();
 299   undo->type = ITEM_RECOGNIZER;
 300   undo->layer = ui.cur_layer;
 301   undo->erasurelist = NULL;
 302   shift = 0;
 303
 304   for (i=0; i<num_old_items; i++) {
 305     if (rs[i].item == old_item) continue; // already done
 306     old_item = rs[i].item;
 307     erasure = g_new(struct UndoErasureData, 1);
 308     erasure->item = old_item;
 309     erasure->npos = g_list_index(ui.cur_layer->items, old_item) + (shift++);
 310     erasure->nrepl = 0;
 311     erasure->replacement_items = NULL;
 312     undo->erasurelist = g_list_append(undo->erasurelist, erasure);
 313     if (old_item->canvas_item != NULL)
 314       gtk_object_destroy(GTK_OBJECT(old_item->canvas_item));
 315     ui.cur_layer->items = g_list_remove(ui.cur_layer->items, old_item);
 316     ui.cur_layer->nitems--;
 317   }
 318 }
 319
 320 struct Item *insert_recognized_curpath(void)
 321 {
 322   struct Item *item;
 323   int i;
 324   struct UndoErasureData *erasure;
 325
 326   erasure = (struct UndoErasureData *)(undo->erasurelist->data);
 327   item = g_new(struct Item, 1);
 328   item->type = ITEM_STROKE;
 329   g_memmove(&(item->brush), &(erasure->item->brush), sizeof(struct Brush));
 330   item->brush.variable_width = FALSE;
 331   subdivide_cur_path();
 332   item->path = gnome_canvas_points_new(ui.cur_path.num_points);
 333   g_memmove(item->path->coords, ui.cur_path.coords, 2*ui.cur_path.num_points*sizeof(double));
 334   item->widths = NULL;
 335   update_item_bbox(item);
 336   ui.cur_path.num_points = 0;
 337
 338   erasure->nrepl++;
 339   erasure->replacement_items = g_list_append(erasure->replacement_items, item);
 340   ui.cur_layer->items = g_list_append(ui.cur_layer->items, item);
 341   ui.cur_layer->nitems++;
 342   make_canvas_item_one(ui.cur_layer->group, item);
 343   return item;
 344 }
 345
 346
 347 /* test if segments form standard shapes */
 348
 349 gboolean try_rectangle(void)
 350 {
 351   struct RecoSegment *rs, *r1, *r2;
 352   int i;
 353   double dist, avg_angle;
 354
 355   // first, we need whole strokes to combine to 4 segments...
 356   if (recognizer_queue_length<4) return FALSE;
 357   rs = recognizer_queue + recognizer_queue_length - 4;
 358   if (rs->startpt!=0) return FALSE;
 359
 360   // check edges make angles ~= Pi/2 and vertices roughly match
 361   avg_angle = 0.;
 362   for (i=0; i<=3; i++) {
 363     r1 = rs+i; r2 = rs+(i+1)%4;
 364     if (fabs(fabs(r1->angle-r2->angle)-M_PI/2) > RECTANGLE_ANGLE_TOLERANCE)
 365       return FALSE;
 366     avg_angle += r1->angle;
 367     if (r2->angle > r1->angle) avg_angle += (i+1)*M_PI/2;
 368     else avg_angle -= (i+1)*M_PI/2;
 369     // test if r1 points away from r2 rather than towards it
 370     r1->reversed = ((r1->x2-r1->x1)*(r2->xcenter-r1->xcenter)+
 371                    (r1->y2-r1->y1)*(r2->ycenter-r1->ycenter)) < 0;
 372   }
 373   for (i=0; i<=3; i++) {
 374     r1 = rs+i; r2 = rs+(i+1)%4;
 375     dist = hypot((r1->reversed?r1->x1:r1->x2) - (r2->reversed?r2->x2:r2->x1),
 376                  (r1->reversed?r1->y1:r1->y2) - (r2->reversed?r2->y2:r2->y1));
 377     if (dist > RECTANGLE_LINEAR_TOLERANCE*(r1->radius+r2->radius)) return FALSE;
 378   }
 379
 380   // make a rectangle of the correct size and slope
 381   avg_angle = avg_angle/4;
 382   if (fabs(avg_angle)<SLANT_TOLERANCE) avg_angle = 0.;
 383   if (fabs(avg_angle)>M_PI/2-SLANT_TOLERANCE) avg_angle = M_PI/2;
 384   realloc_cur_path(5);
 385   ui.cur_path.num_points = 5;
 386   for (i=0; i<=3; i++) rs[i].angle = avg_angle+i*M_PI/2;
 387   for (i=0; i<=3; i++) calc_edge_isect(rs+i, rs+(i+1)%4, ui.cur_path.coords+2*i+2);
 388   ui.cur_path.coords[0] = ui.cur_path.coords[8];
 389   ui.cur_path.coords[1] = ui.cur_path.coords[9];
 390
 391   remove_recognized_strokes(rs, 4);
 392   insert_recognized_curpath();
 393   return TRUE;
 394 }
 395
 396 gboolean try_arrow(void)
 397 {
 398   struct RecoSegment *rs;
 399   int i, j;
 400   double alpha[3], dist, pt[2], tmp, delta;
 401   double x1, y1, x2, y2, angle;
 402   gboolean rev[3];
 403
 404   // first, we need whole strokes to combine to nsides segments...
 405   if (recognizer_queue_length<3) return FALSE;
 406   rs = recognizer_queue + recognizer_queue_length - 3;
 407   if (rs->startpt!=0) return FALSE;
 408
 409   // check arrow head not too big, and orient main segment
 410   for (i=1; i<=2; i++) {
 411     if (rs[i].radius > ARROW_MAXSIZE*rs[0].radius) return FALSE;
 412     rev[i] = (hypot(rs[i].xcenter-rs->x1, rs[i].ycenter-rs->y1) <
 413               hypot(rs[i].xcenter-rs->x2, rs[i].ycenter-rs->y2));
 414   }
 415   if (rev[1]!=rev[2]) return FALSE;
 416   if (rev[1]) {
 417     x1 = rs->x2; y1 = rs->y2; x2 = rs->x1; y2 = rs->y1;
 418     angle = rs->angle + M_PI;
 419   }
 420   else {
 421     x1 = rs->x1; y1 = rs->y1; x2 = rs->x2; y2 = rs->y2;
 422     angle = rs->angle;
 423   }
 424
 425   // check arrow head not too big, and angles roughly ok
 426   for (i=1; i<=2; i++) {
 427     rs[i].reversed = FALSE;
 428     alpha[i] = rs[i].angle - angle;
 429     while (alpha[i]<-M_PI/2) { alpha[i]+=M_PI; rs[i].reversed = !rs[i].reversed; }
 430     while (alpha[i]>M_PI/2) { alpha[i]-=M_PI; rs[i].reversed = !rs[i].reversed; }
 431 #ifdef RECOGNIZER_DEBUG
 432     printf("DEBUG: arrow: alpha[%d] = %.1f degrees\n", i, alpha[i]*180/M_PI);
 433 #endif
 434     if (fabs(alpha[i])<ARROW_ANGLE_MIN || fabs(alpha[i])>ARROW_ANGLE_MAX) return FALSE;
 435   }
 436
 437   // check arrow head segments are roughly symmetric
 438   if (alpha[1]*alpha[2]>0 || fabs(alpha[1]+alpha[2]) > ARROW_ASYMMETRY_MAX_ANGLE) return FALSE;
 439   if (rs[1].radius/rs[2].radius > 1+ARROW_ASYMMETRY_MAX_LINEAR) return FALSE;
 440   if (rs[2].radius/rs[1].radius > 1+ARROW_ASYMMETRY_MAX_LINEAR) return FALSE;
 441
 442   // check vertices roughly match
 443   calc_edge_isect(rs+1, rs+2, pt);
 444   for (j=1; j<=2; j++) {
 445     dist = hypot(pt[0]-(rs[j].reversed?rs[j].x1:rs[j].x2),
 446                  pt[1]-(rs[j].reversed?rs[j].y1:rs[j].y2));
 447 #ifdef RECOGNIZER_DEBUG
 448     printf("DEBUG: linear tolerance: tip[%d] = %.2f\n", j, dist/rs[j].radius);
 449 #endif
 450     if (dist>ARROW_TIP_LINEAR_TOLERANCE*rs[j].radius) return FALSE;
 451   }
 452   dist = (pt[0]-x2)*sin(angle)-(pt[1]-y2)*cos(angle);
 453   dist /= rs[1].radius + rs[2].radius;
 454 #ifdef RECOGNIZER_DEBUG
 455   printf("DEBUG: sideways gap tolerance = %.2f\n", dist);
 456 #endif
 457   if (fabs(dist)>ARROW_SIDEWAYS_GAP_TOLERANCE) return FALSE;
 458   dist = (pt[0]-x2)*cos(angle)+(pt[1]-y2)*sin(angle);
 459   dist /= rs[1].radius + rs[2].radius;
 460 #ifdef RECOGNIZER_DEBUG
 461   printf("DEBUG: main linear gap = %.2f\n", dist);
 462 #endif
 463   if (dist<ARROW_MAIN_LINEAR_GAP_MIN || dist>ARROW_MAIN_LINEAR_GAP_MAX) return FALSE;
 464
 465   // make an arrow of the correct size and slope
 466   if (fabs(rs->angle)<SLANT_TOLERANCE) { // nearly horizontal
 467     angle = angle - rs->angle;
 468     y1 = y2 = rs->ycenter;
 469   }
 470   if (rs->angle>M_PI/2-SLANT_TOLERANCE) { // nearly vertical
 471     angle = angle - (rs->angle-M_PI/2);
 472     x1 = x2 = rs->xcenter;
 473   }
 474   if (rs->angle<-M_PI/2+SLANT_TOLERANCE) { // nearly vertical
 475     angle = angle - (rs->angle+M_PI/2);
 476     x1 = x2 = rs->xcenter;
 477   }
 478   delta = fabs(alpha[1]-alpha[2])/2;
 479   dist = (hypot(rs[1].x1-rs[1].x2, rs[1].y1-rs[1].y2) +
 480           hypot(rs[2].x1-rs[2].x2, rs[2].y1-rs[2].y2))/2;
 481
 482   realloc_cur_path(2);
 483   ui.cur_path.num_points = 2;
 484   ui.cur_path.coords[0] = x1; ui.cur_path.coords[1] = y1;
 485   ui.cur_path.coords[2] = x2; ui.cur_path.coords[3] = y2;
 486   remove_recognized_strokes(rs, 3);
 487   insert_recognized_curpath();
 488
 489   realloc_cur_path(3);
 490   ui.cur_path.num_points = 3;
 491   ui.cur_path.coords[0] = x2 - dist*cos(angle+delta);
 492   ui.cur_path.coords[1] = y2 - dist*sin(angle+delta);
 493   ui.cur_path.coords[2] = x2;
 494   ui.cur_path.coords[3] = y2;
 495   ui.cur_path.coords[4] = x2 - dist*cos(angle-delta);
 496   ui.cur_path.coords[5] = y2 - dist*sin(angle-delta);
 497   insert_recognized_curpath();
 498
 499   return TRUE;
 500 }
 501
 502 gboolean try_closed_polygon(int nsides)
 503 {
 504   struct RecoSegment *rs, *r1, *r2;
 505   int i;
 506   double dist, pt[2];
 507
 508   // first, we need whole strokes to combine to nsides segments...
 509   if (recognizer_queue_length<nsides) return FALSE;
 510   rs = recognizer_queue + recognizer_queue_length - nsides;
 511   if (rs->startpt!=0) return FALSE;
 512
 513   // check vertices roughly match
 514   for (i=0; i<nsides; i++) {
 515     r1 = rs+i; r2 = rs+(i+1)%nsides;
 516     // test if r1 points away from r2 rather than towards it
 517     calc_edge_isect(r1, r2, pt);
 518     r1->reversed = (hypot(pt[0]-r1->x1,pt[1]-r1->y1) < hypot(pt[0]-r1->x2,pt[1]-r1->y2));
 519   }
 520   for (i=0; i<nsides; i++) {
 521     r1 = rs+i; r2 = rs+(i+1)%nsides;
 522     calc_edge_isect(r1, r2, pt);
 523     dist = hypot((r1->reversed?r1->x1:r1->x2)-pt[0],(r1->reversed?r1->y1:r1->y2)-pt[1])
 524          + hypot((r2->reversed?r2->x2:r2->x1)-pt[0],(r2->reversed?r2->y2:r2->y1)-pt[1]);
 525     if (dist > POLYGON_LINEAR_TOLERANCE*(r1->radius+r2->radius)) return FALSE;
 526   }
 527
 528   // make a polygon of the correct size and slope
 529   realloc_cur_path(nsides+1);
 530   ui.cur_path.num_points = nsides+1;
 531   for (i=0; i<nsides; i++)
 532     calc_edge_isect(rs+i, rs+(i+1)%nsides, ui.cur_path.coords+2*i+2);
 533   ui.cur_path.coords[0] = ui.cur_path.coords[2*nsides];
 534   ui.cur_path.coords[1] = ui.cur_path.coords[2*nsides+1];
 535
 536   remove_recognized_strokes(rs, nsides);
 537   insert_recognized_curpath();
 538   return TRUE;
 539 }
 540
 541 /* the main pattern recognition function, called after finalize_stroke() */
 542 void recognize_patterns(void)
 543 {
 544   struct Item *it;
 545   struct Inertia s, ss[4];
 546   struct RecoSegment *rs;
 547   int n, i;
 548   int brk[5];
 549   double score;
 550
 551   if (!undo || undo->type!=ITEM_STROKE) return;
 552   if (undo->next != last_item_checker) reset_recognizer(); // reset queue
 553   if (last_item_checker!=NULL && ui.cur_layer != last_item_checker->layer) reset_recognizer();
 554
 555   it = undo->item;
 556   calc_inertia(it->path->coords, 0, it->path->num_points-1, &s);
 557 #ifdef RECOGNIZER_DEBUG
 558   printf("DEBUG: Mass=%.0f, Center=(%.1f,%.1f), I=(%.0f,%.0f, %.0f), "
 559      "Rad=%.2f, Det=%.4f \n",
 560      s.mass, center_x(s), center_y(s), I_xx(s), I_yy(s), I_xy(s), I_rad(s), I_det(s));
 561 #endif
 562
 563   // first see if it's a polygon
 564   n = find_polygonal(it->path->coords, 0, it->path->num_points-1, MAX_POLYGON_SIDES, brk, ss);
 565   if (n>0) {
 566     optimize_polygonal(it->path->coords, n, brk, ss);
 567 #ifdef RECOGNIZER_DEBUG
 568     printf("DEBUG: Polygon, %d edges: ", n);
 569     for (i=0; i<n; i++)
 570       printf("DEBUG: %d-%d (M=%.0f, det=%.4f) ", brk[i], brk[i+1], ss[i].mass, I_det(ss[i]));
 571     printf("\n");
 572 #endif
 573     /* update recognizer segment queue (most recent at end) */
 574     while (n+recognizer_queue_length > MAX_POLYGON_SIDES) {
 575       // remove oldest polygonal stroke
 576       i=1;
 577       while (i<recognizer_queue_length && recognizer_queue[i].startpt!=0) i++;
 578       recognizer_queue_length-=i;
 579       g_memmove(recognizer_queue, recognizer_queue+i,
 580               recognizer_queue_length * sizeof(struct RecoSegment));
 581     }
 582 #ifdef RECOGNIZER_DEBUG
 583     printf("DEBUG: Queue now has %d + %d edges\n", recognizer_queue_length, n);
 584 #endif
 585     rs = recognizer_queue + recognizer_queue_length;
 586     recognizer_queue_length += n;
 587     for (i=0; i<n; i++) {
 588       rs[i].item = it;
 589       rs[i].startpt = brk[i];
 590       rs[i].endpt = brk[i+1];
 591       get_segment_geometry(it->path->coords, brk[i], brk[i+1], ss+i, rs+i);
 592     }
 593     if (try_rectangle()) { reset_recognizer(); return; }
 594     if (try_arrow()) { reset_recognizer(); return; }
 595     if (try_closed_polygon(3)) { reset_recognizer(); return; }
 596     if (try_closed_polygon(4)) { reset_recognizer(); return; }
 597     if (n==1) { // current stroke is a line
 598       if (fabs(rs->angle)<SLANT_TOLERANCE) { // nearly horizontal
 599         rs->angle = 0.;
 600         rs->y1 = rs->y2 = rs->ycenter;
 601       }
 602       if (fabs(rs->angle)>M_PI/2-SLANT_TOLERANCE) { // nearly vertical
 603         rs->angle = (rs->angle>0)?(M_PI/2):(-M_PI/2);
 604         rs->x1 = rs->x2 = rs->xcenter;
 605       }
 606       realloc_cur_path(2);
 607       ui.cur_path.num_points = 2;
 608       ui.cur_path.coords[0] = rs->x1;
 609       ui.cur_path.coords[1] = rs->y1;
 610       ui.cur_path.coords[2] = rs->x2;
 611       ui.cur_path.coords[3] = rs->y2;
 612       remove_recognized_strokes(rs, 1);
 613       rs->item = insert_recognized_curpath();
 614     }
 615     last_item_checker = undo;
 616     return;
 617   }
 618
 619   // not a polygon: maybe a circle ?
 620   reset_recognizer();
 621   if (I_det(s)>CIRCLE_MIN_DET) {
 622     score = score_circle(it->path->coords, 0, it->path->num_points-1, &s);
 623 #ifdef RECOGNIZER_DEBUG
 624     printf("DEBUG: Circle score: %.2f\n", score);
 625 #endif
 626     if (score < CIRCLE_MAX_SCORE) {
 627       make_circle_shape(center_x(s), center_y(s), I_rad(s));
 628       recognizer_queue[0].item = it;
 629       remove_recognized_strokes(recognizer_queue, 1);
 630       insert_recognized_curpath();
 631     }
 632   }
 633 }
 634