[Toss-devel-svn] SF.net SVN: toss:[1636] trunk/Toss

[<luk...@us...>]

Revision: 1636
          http://toss.svn.sourceforge.net/toss/?rev=1636&view=rev
Author:   lukaszkaiser
Date:     2011-12-10 23:39:15 +0000 (Sat, 10 Dec 2011)
Log Message:
-----------
New directory for game learning stuff (will move later), starting visual recognition for grid-games using OpenCV.

Added Paths:
-----------
    trunk/Toss/Learn/
    trunk/Toss/Learn/.cvsignore
    trunk/Toss/Learn/Makefile
    trunk/Toss/Learn/grid.pdf
    trunk/Toss/Learn/reco.cpp
    trunk/Toss/Learn/shapes.c
    trunk/Toss/Learn/shapes.h
    trunk/Toss/Learn/videos/
    trunk/Toss/Learn/videos/tic_tac_toe_0.3gp


Property changes on: trunk/Toss/Learn
___________________________________________________________________
Added: svn:ignore
   + # We are still using .cvsignore files as we find them easier to manage
# than svn properties. Therefore if you change .cvsignore do the following.
#     svn propset svn:ignore -F .cvsignore .

reco
*~
*.o
log*.ppm


Added: trunk/Toss/Learn/.cvsignore
===================================================================
--- trunk/Toss/Learn/.cvsignore	                        (rev 0)
+++ trunk/Toss/Learn/.cvsignore	2011-12-10 23:39:15 UTC (rev 1636)
@@ -0,0 +1,8 @@
+# We are still using .cvsignore files as we find them easier to manage
+# than svn properties. Therefore if you change .cvsignore do the following.
+#     svn propset svn:ignore -F .cvsignore .
+
+reco
+*~
+*.o
+log*.ppm

Added: trunk/Toss/Learn/Makefile
===================================================================
--- trunk/Toss/Learn/Makefile	                        (rev 0)
+++ trunk/Toss/Learn/Makefile	2011-12-10 23:39:15 UTC (rev 1636)
@@ -0,0 +1,10 @@
+all: reco
+
+shapes.o: shapes.c shapes.h
+	gcc -c shapes.c
+
+reco: reco.cpp shapes.o
+	g++ shapes.o reco.cpp -o reco `pkg-config opencv --cflags --libs`
+
+clean:
+	rm -rf reco log*.ppm *.o *~ 


Property changes on: trunk/Toss/Learn/Makefile
___________________________________________________________________
Added: svn:executable
   + *

Added: trunk/Toss/Learn/grid.pdf
===================================================================
--- trunk/Toss/Learn/grid.pdf	                        (rev 0)
+++ trunk/Toss/Learn/grid.pdf	2011-12-10 23:39:15 UTC (rev 1636)
@@ -0,0 +1,69 @@
+%PDF-1.4
+%\xD0\xD4\xC5\xD8
+1 0 obj
+<<>>
+endobj
+2 0 obj
+<<>>
+endobj
+3 0 obj
+<<  /pgfprgb [/Pattern /DeviceRGB] >>
+endobj
+6 0 obj <<
+/Length 139       
+/Filter /FlateDecode
+>>
+stream
+xڅ\x911\xC20Ew\x9F\xE2_ \x96\x83S㜠3\xE2]Z$&\xAEOڡ\x90Ш\x8Bc\xFF\xFF\xBE\x9C(\x82	\x82\x91\xE4䌥
+"T\x8CUI2\xE7dx,\xF4B\xA1Fl(	k\xF6
o\xACr\xE2\xEC\xB1\xC0e
+\xF1*,.n\xF8i\x97\xCA\xF8v3\xE8T\x95zƽ\xF6c\xCBj\x97u\xF5\x91\xFC\x978\xB4\xFC>7\x8F\xDB\xF5\xF6N\x9D@\x97\xBF\x81\x9E[m?\xE6\xF6\xD4U@
+endstream
+endobj
+5 0 obj <<
+/Type /Page
+/Contents 6 0 R
+/Resources 4 0 R
+/MediaBox [0 0 612 792]
+/Parent 7 0 R
+>> endobj
+4 0 obj <<
+ /ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R 
+/ProcSet [ /PDF ]
+>> endobj
+7 0 obj <<
+/Type /Pages
+/Count 1
+/Kids [5 0 R]
+>> endobj
+8 0 obj <<
+/Type /Catalog
+/Pages 7 0 R
+>> endobj
+9 0 obj <<
+/Producer (pdfTeX-1.40.10)
+/Creator (TeX)
+/CreationDate (D:20111210202438+01'00')
+/ModDate (D:20111210202438+01'00')
+/Trapped /False
+/PTEX.Fullbanner (This is pdfTeX, Version 3.1415926-1.40.10-2.2 (TeX Live 2009/Debian) kpathsea version 5.0.0)
+>> endobj
+xref
+0 10
+0000000000 65535 f 
+0000000015 00000 n 
+0000000035 00000 n 
+0000000055 00000 n 
+0000000430 00000 n 
+0000000326 00000 n 
+0000000108 00000 n 
+0000000521 00000 n 
+0000000578 00000 n 
+0000000627 00000 n 
+trailer
+<< /Size 10
+/Root 8 0 R
+/Info 9 0 R
+/ID [<6450C2B72902EC0DBB009F58BA2907F2> <6450C2B72902EC0DBB009F58BA2907F2>] >>
+startxref
+892
+%%EOF

Added: trunk/Toss/Learn/reco.cpp
===================================================================
--- trunk/Toss/Learn/reco.cpp	                        (rev 0)
+++ trunk/Toss/Learn/reco.cpp	2011-12-10 23:39:15 UTC (rev 1636)
@@ -0,0 +1,133 @@
+#include <opencv/cv.h>
+#include <opencv/ml.h>
+#include <opencv/cxcore.h>
+#include <opencv/cxtypes.h>
+#include <opencv/highgui.h>
+extern "C" {
+  #include "shapes.h"
+}
+#include<cstdio>
+
+#define SIZEX 146 //352 - MARGINX / 2
+#define SIZEY 130 //288 - MARGINY / 2
+#define MARGINX 22
+#define MARGINY 8
+
+void reset (char a[SIZEX][SIZEY]) {
+  for (int j = 0; j < SIZEY; j++) {
+    for (int i = 0; i < SIZEX; i++) {
+      a[i][j] = 1;
+    }
+  }
+}
+
+static int print_counter = 0;
+void print_ppm (char pic[SIZEX][SIZEY], char * prefix) {
+  char fname[80];
+  sprintf (fname, "%s%i.ppm", prefix, print_counter);
+  print_counter++;
+  FILE * f = fopen (fname, "w");
+  fprintf (f, "P3\n%i %i\n255\n", SIZEX, SIZEY);
+  for (int j = 0; j < SIZEY; j++) {
+    for (int i = 0; i < SIZEX; i++) {
+      if (pic[i][j] > 0) {
+	fprintf (f, "0 0 0 ");
+      } else {
+	fprintf (f, "255 255 255 ");
+      }
+    }
+    fprintf (f, "\n");
+  }
+  fclose (f);
+}
+
+CvPoint from_point (point p) {
+  double x = p.x + MARGINX; //(p.x * SIZEX) / (SIZEX + 2*MARGINX) + MARGINX;
+  double y = p.y + MARGINY;
+  return (cvPoint ((int) x, (int) y));
+}
+
+
+int main(int argc, char* argv[])
+{
+  char res[2000];
+  int rnbr = -2;
+
+  cvNamedWindow ("Reco", CV_WINDOW_AUTOSIZE);
+  CvCapture* capture = cvCreateFileCapture ("videos/tic_tac_toe_0.3gp");
+    //cvCreateCameraCapture( 0 );
+  IplImage* img;
+  IplImage* gray;
+  IplImage* small;
+  int data_count = 0;
+  char data[SIZEX][SIZEY];
+  unsigned int cur_data = 0;
+  int time = 0;
+  int ok_around;
+  char shape_str[SIZEX*SIZEY*24] = "";
+  int shape_str_pos = 0;
+  
+  reset (data);
+  
+  while (true) {
+    img = cvQueryFrame (capture);
+    if (!img) break;
+    gray =  cvCreateImage (cvSize (img->width, img->height), 8, 1);
+    cvCvtColor (img, gray, CV_BGR2GRAY);
+    small = cvCreateImage (cvSize (SIZEX + 2*MARGINX, SIZEY + 2*MARGINY), 8, 1);
+    cvResize (gray, small, CV_INTER_LINEAR);
+    cvCanny (small, small, 50, 100);
+    data_count = 0;
+    for (int i = 0; i < SIZEX; i++) {
+      for (int j = 0; j < SIZEY; j++) {
+	cur_data = (unsigned int) 
+	  small->imageData[(i+MARGINX) + small->widthStep * (j+MARGINY)];
+	ok_around = i == 0 || j == 0 ? 1 :
+	  data[i][j] + data[i-1][j] + data[i+1][j] +
+	  data[i][j+1] + data[i-1][j-1] + data[i+1][j-1] +
+	  data[i][j-1] + data[i-1][j+1] + data[i+1][j+1];
+	ok_around = ok_around == 0 ? 0 : 1;
+	data[i][j] = cur_data > 2 ? ok_around : 0;
+	if (data[i][j] == 1) data_count++;
+      }
+    }
+    if (time % 5 == 0 && data_count < 500) { // we see empty picture, reset
+      reset (data);
+      time = 1;
+    }
+    if (rnbr >= 0) {
+      shape p = (get_patterns())[rnbr];
+      for (int s = 0; s < p.size; s++) {
+	cvLine (small, from_point (p.shape[s].start), 
+		from_point (p.shape[s].end), CV_RGB (200, 100, 100), 3);
+      }
+    }
+    cvShowImage( "Reco", small );
+    if (time % 70 == 0) { // wait < 4s for now
+      shape_str_pos = sprintf (shape_str, "START %i ", data_count);
+      for (int i = 0; i < SIZEX; i++) {
+	for (int j = 0; j < SIZEY; j++) {
+	  if (data[i][j] == 1) {
+	    shape_str_pos += sprintf (shape_str + shape_str_pos,
+				      "(%i, %i) -- (%i, %i) ", i, j, i, j);
+	  }
+	}
+      }
+      sprintf (shape_str + shape_str_pos, " END");
+      printf ("step: %i\nsize: %i\nreco:\n", time/70, data_count);
+      print_ppm (data, (char*) "log");
+      reset (data);
+      recognize_from_string (shape_str, res, &rnbr, time/70 - 1);
+      printf ("%i\n", rnbr);
+      for (int i = 0; i < 2000; i++) res[i] = 0;
+      for (int i = 0; i < SIZEX*SIZEY*24; i++) shape_str[i] = 0;
+    }
+    time++;
+    char c = cvWaitKey (50);
+    if (c == 27) break;
+  }
+  cvReleaseCapture (&capture);
+  cvDestroyWindow ("Reco");
+  
+  return (0);
+}

Added: trunk/Toss/Learn/shapes.c
===================================================================
--- trunk/Toss/Learn/shapes.c	                        (rev 0)
+++ trunk/Toss/Learn/shapes.c	2011-12-10 23:39:15 UTC (rev 1636)
@@ -0,0 +1,1858 @@
+/* Implementation of Shape Matching.
+   This is derived from a Xournal patch by Lukasz Kaiser.
+   In the future, we could consider external libraries for Frechet distance:
+   e.g. http://www.cs.uu.nl/centers/give/multimedia/matching/shame.html */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <math.h>
+#include <pthread.h>
+
+typedef struct point_s {double x; double y;} point;
+typedef struct interval_s {point start; point end;} interval;
+
+typedef struct shape_s {
+  interval* shape;
+  int size;
+  char name[80];
+  double max_dist;
+  double correction;
+  double scale_correction;
+  double min_rotation;
+  double max_rotation;
+  double rotation_density;
+} shape;
+
+
+static pthread_mutex_t shapes_stop_mutex;
+static pthread_mutex_t shapes_working_mutex;
+static pthread_mutex_t shapes_painting_mutex;
+static int stop_signal;
+
+#define min(x, y) (y < x ? y : x)
+#define max(x, y) (y > x ? y : x)
+
+/* The metric parameter used by computing averages. */
+static double metric_k_1 = 1.4;
+static int get_metric_k_1 () { return (metric_k_1); }
+static void set_metric_k_1 (double k) { metric_k_1 = k; }
+static double metric_k_2 = 14;
+static int get_metric_k_2 () { return (metric_k_2); }
+static void set_metric_k_2 (double k) { metric_k_2 = k; }
+
+/* Compare two points (compatible for qsort). */
+static int point_cmp (const void * p1, const void * p2)
+{
+  double x1 = ((point*) p1)->x;
+  double y1 = ((point*) p1)->y;
+  double x2 = ((point*) p2)->x;
+  double y2 = ((point*) p2)->y;
+  if (x1 - x2 == 0) {
+    if (y1 - y2 > 0) { 
+      return (1);
+    } else if (y1 - y2 < 0) {
+      return (-1);
+    } else {
+      return (0);
+    }
+  } else {
+    if (x1 - x2 > 0) { 
+      return (1);
+    } else if (x1 - x2 < 0) {
+      return (-1);
+    } else {
+      return (0);
+    }
+  }
+}
+
+/* Distance from (x, y) to the interval (x1, y1) -- (x2, y2). */
+static double distance (const point p, const interval i)
+{
+  double x = p.x;
+  double y = p.y;
+  double x1 = i.start.x;
+  double y1 = i.start.y;
+  double x2 = i.end.x;
+  double y2 = i.end.y;
+
+  /* find (x3, y3) so that:
+       - (y3-y1)*(x2-x1) = (y2-y1)*(x3-x1) // (x3, y3) on the line 1-2
+       <=> y3*dx - y1*dx = x3*dy - x1*dy
+       <=> y3 = x3*(dy/dx) + y1 - x1(dy/dx) 
+       <=> x3 = y3(dx/dy) + x1 - y1(dx/dy)
+       - (x1-x3, y1-y3)*(x-x3, y-y3) = 0 // ortogonal
+       <=> (x3-x1)*(x3-x) = (y3-y1)*(y-y3)
+       <=> (x2-x1)*(x3-x) = (y1-y2)*(y3-y)
+       <=> x3*dx - x*dx = y*dy - y3*dy
+       <=> x3*dx - x*dx = y*dy - (x3*dy*dy/dx) - y1*dy + x1*dy*dy/dx
+       <=> x3*(dx*dx + dy*dy) = y*dy*dx + x*dx*dx - y1*dy*dx + x1*dy*dy
+       <=> y3*dx*dx/dy + x1*dx - y1*dx*dx/dy - x*dx = y*dy - y3*dy
+       <=> y3*(dx*dx + dy*dy) = y*dy*dy + y1*dx*dx + dx*dy*(x-x1)
+  */
+  const double dx = x2 - x1;
+  const double dy = y2 - y1;
+  const double dsq = dx*dx + dy*dy;
+  if (dsq < 0.000000001) {
+    return (sqrt ((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)));
+  } else {
+    const double x3 = (dx*dy*(y - y1) + dx*dx*x + dy*dy*x1) / dsq;
+    const double y3 = (dx*dy*(x - x1) + dx*dx*y1 + dy*dy*y) / dsq;
+    /* Use (x3, y3) if it lies on (x1,y1)--(x2,y2):
+       - (min (x1, x2) <= x3 <= max (x1, x2))
+       - (min (y1, y2) <= y3 <= max (y1, y2)), else use one of the ends.
+    */
+    if ((min (x1, x2) <= x3) && (max (x1, x2) >= x3) &&
+	(min (y1, y2) <= y3) && (max (y1, y2) >= y3)) {
+      return (sqrt ((x3-x) * (x3-x) + (y3-y) * (y3-y)));
+    } else {
+      double d1 = sqrt ((x1-x) * (x1-x) + (y1-y) * (y1-y));
+      double d2 = sqrt ((x2-x) * (x2-x) + (y2-y) * (y2-y));
+      return (min (d1, d2));
+    }
+  }
+}
+
+/* min_(intervals) distance p-interval */
+static double point_distance (const point p, const interval* ivs, const int size) 
+{
+  if (size == 0) return (0.0);
+  if (size == 1) return (distance (p, ivs[0]));
+  double x = p.x;
+  double y = p.y;
+
+  double current_min_pt_dist = 
+    distance (p, ivs[(rand() % (size/2)) + (size/2)]);
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    double x1 = ivs[i].start.x;
+    double y1 = ivs[i].start.y;
+    double x2 = ivs[i].end.x;
+    double y2 = ivs[i].end.y;
+    if (!(((x1 + current_min_pt_dist < x) && (x2 + current_min_pt_dist < x)) ||
+	  ((y1 + current_min_pt_dist < y) && (y2 + current_min_pt_dist < y)) ||
+	  ((x1 - current_min_pt_dist > x) && (x2 - current_min_pt_dist > x)) ||
+	  ((y1 - current_min_pt_dist > y) && (y2 - current_min_pt_dist > y)))) {
+      current_min_pt_dist = min (current_min_pt_dist, distance (p, ivs[i]));
+    }
+  }
+
+  return (current_min_pt_dist);
+}
+
+
+/* Calculate k-avg_(points) min_(interval) distance point-interval, where
+   k-avg is L_k metric average: k-root of sum of k-powers divided by size. */
+static double set_distance (const point* pts, const int sizep, 
+		     const interval* ivs, const int sizei)
+{
+  /* For efficiency we include k-avg computation directly here. */
+  int i = 0;
+  double sum1 = 0.0;
+  double sum2 = 0.0;
+  for (i = 0; i < sizep; i++) {
+    double dist = point_distance (pts[i], ivs, sizei);
+    sum1 += pow (dist, metric_k_1);
+    sum2 += pow (dist, metric_k_2);
+  }
+  sum1 /= sizep;
+  sum2 /= sizep;
+  sum1 = pow (sum1, 1/metric_k_1);
+  sum2 = pow (sum2, 1/metric_k_2);
+
+  return (sum1 + sum2);
+}
+
+/* Make a list of points in a shape, sort them and remove repetitions. */
+static point* shape_points (const interval* shape, const int size, int* res_size)
+{  
+  point points[2*size];
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    points[2*i] = shape[i].start;
+    points[2*i+1] = shape[i].end;
+  }
+  qsort (points, 2*size, sizeof (points[0]), point_cmp);
+
+  *res_size = 0;
+  for (i = 0; i < 2*size-1; i++) {
+    if ((points[i].x != points[i+1].x) || (points[i].y != points[i+1].y)) {
+      (*res_size)++;
+    }
+  }
+  (*res_size)++;
+
+  point* new_points = calloc ((*res_size), sizeof (point));
+  int j = 0;
+  for (i = 0; i < 2*size-1; i++) {
+    if ((points[i].x != points[i+1].x) || (points[i].y != points[i+1].y)) {
+      new_points[j] = points[i];
+      j++;
+    }
+  }
+  new_points[j] = points[2*size-1];
+
+  return (new_points);
+}
+
+/* Calculate the distance between two shapes fast using point sets. */
+static double shape_distance_fast (const interval* s1, const int size1,
+			    const point* p1, const int sizep1,
+			    const interval* s2, const int size2,
+			    const point* p2, const int sizep2)
+{
+  double d1 = set_distance (p1, sizep1, s2, size2);
+  double d2 = set_distance (p2, sizep2, s1, size1);
+
+  return (sqrt (d1*d1 + d2*d2));
+}
+
+/* Calculate the distance between two shapes. */
+static double shape_distance (const interval* s1, const int size1, 
+		       const interval* s2, const int size2)
+{
+
+  int points_size1 = 0;
+  point* points1 = shape_points (s1, size1, &points_size1);
+
+  int points_size2 = 0;
+  point* points2 = shape_points (s2, size2, &points_size2);
+
+  double res = shape_distance_fast (s1, size1, points1, points_size1,
+				    s2, size2, points2, points_size2);
+  
+  free (points1);
+  free (points2);
+
+  return (res);
+}
+
+/* Move a shape by a translation vector, given as a point. */
+static void move_shape (const point t, interval* s, const int size)
+{
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    s[i].start.x += t.x;
+    s[i].start.y += t.y;
+    s[i].end.x += t.x;
+    s[i].end.y += t.y;
+  }
+}
+
+/* Move a shape and its points by a translation vector, given as a point. */
+static void move_shape_points (const point t, interval* s, const int size,
+			point* points, const int points_size)
+{
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    s[i].start.x += t.x;
+    s[i].start.y += t.y;
+    s[i].end.x += t.x;
+    s[i].end.y += t.y;
+  }
+
+  for (i = 0; i < points_size; i++) {
+    points[i].x += t.x;
+    points[i].y += t.y;
+  }
+}
+
+/* Compute the middle (avg) of shape x and y, and the height and width. */
+static interval mid_dimen (const interval* s, const int size)
+{
+  interval res;
+  res.start.x = 0;
+  res.start.y = 0;
+  res.end.x = 0;
+  res.end.y = 0;
+  if (size == 0) return (res);
+
+  double minx = s[0].start.x;
+  double miny = s[0].start.y;
+  double maxx = s[0].start.x;
+  double maxy = s[0].start.y;
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    minx = min (minx, min (s[i].start.x, s[i].end.x));
+    miny = min (miny, min (s[i].start.y, s[i].end.y));
+    maxx = max (maxx, max (s[i].start.x, s[i].end.x));
+    maxy = max (maxy, max (s[i].start.y, s[i].end.y));
+  }
+
+  res.start.x = (minx + maxx) / 2;
+  res.start.y = (miny + maxy) / 2;
+  res.end.x = maxx - minx;
+  res.end.y = maxy - miny;
+  return (res);
+}
+
+/* Scale a shape by a scale vector, given as a point. */
+static void scale_shape (const point scale, interval* shape, const int size)
+{
+  interval mids = mid_dimen (shape, size);
+  double mx = mids.start.x;
+  double my = mids.start.y;
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    shape[i].start.x = ((shape[i].start.x - mx) * scale.x) + mx;
+    shape[i].start.y = ((shape[i].start.y - my) * scale.y) + my;
+    shape[i].end.x = ((shape[i].end.x - mx) * scale.x) + mx;
+    shape[i].end.y = ((shape[i].end.y - my) * scale.y) + my;
+  }
+}
+
+/* Scale a shape and its points by a scale vector, given as a point. */
+static void scale_shape_points (const point scale, interval* shape, const int size,
+			 point* points, const int points_size)
+{
+  interval mids = mid_dimen (shape, size);
+  double mx = mids.start.x;
+  double my = mids.start.y;
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    shape[i].start.x = ((shape[i].start.x - mx) * scale.x) + mx;
+    shape[i].start.y = ((shape[i].start.y - my) * scale.y) + my;
+    shape[i].end.x = ((shape[i].end.x - mx) * scale.x) + mx;
+    shape[i].end.y = ((shape[i].end.y - my) * scale.y) + my;
+  }
+
+  for (i = 0; i < points_size; i++) {
+    points[i].x = ((points[i].x - mx) * scale.x) + mx;
+    points[i].y = ((points[i].y - my) * scale.y) + my;
+  }
+}
+
+/* Rotate point [p] by angle [a] (in radians) around point [x, y]. */
+static void rotate_point (point* p, double a, double tx, double ty)
+{
+  double x = p->x - tx;
+  double y = p->y - ty;
+
+  p->x = (x * cos (a) - y * sin (a)) + tx;
+  p->y = (x * sin (a) + y * cos (a)) + ty;
+}
+
+/* Rotate a shape by an angle, in radians. */
+static void rotate_shape (const double angle, interval* shape, const int size)
+{
+  interval mids = mid_dimen (shape, size);
+  double mx = mids.start.x;
+  double my = mids.start.y;
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    rotate_point (&shape[i].start, angle, mx, my);
+    rotate_point (&shape[i].end, angle, mx, my);
+  }
+}
+
+/* Scale a shape and its points by a scale vector, given as a point. */
+static void rotate_shape_points (const double angle, interval* shape, const int size,
+			  point* points, const int points_size)
+{
+  interval mids = mid_dimen (shape, size);
+  double mx = mids.start.x;
+  double my = mids.start.y;
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    rotate_point (&shape[i].start, angle, mx, my);
+    rotate_point (&shape[i].end, angle, mx, my);
+  }
+
+  for (i = 0; i < points_size; i++) {
+    rotate_point (&points[i], angle, mx, my);
+  }
+}
+
+
+/* Move and scale a shape by a vector, given as an interval. */
+static void move_scale_shape (const point t, const point s, 
+		       interval* shape, const int size)
+{
+  move_shape (t, shape, size);
+  scale_shape (s, shape, size);
+}
+
+/* Move and scale a shape and its points by a vector, given as an interval. */
+static void move_scale_shape_points (const point t, const point s,
+			      interval* shape, const int size,
+			      point* points, const int points_size)
+{
+  move_shape_points (t, shape, size, points, points_size);
+  scale_shape_points (s, shape, size, points, points_size);
+}
+
+/* Move and scale and rotate a shape by a vector and an angle. */
+static void move_scale_rotate_shape (const point t, const point s, const double angle,
+			       interval* shape, const int size)
+{
+  move_shape (t, shape, size);
+  scale_shape (s, shape, size);
+  rotate_shape (angle, shape, size);
+}
+
+/* Move and scale and rotate a shape and its points by a vector and an angle. */
+static void move_scale_rotate_shape_points (const point t, const point s, 
+				     const double angle, 
+				     interval* shape, const int size,
+				     point* points, const int points_size)
+{
+  move_shape_points (t, shape, size, points, points_size);
+  scale_shape_points (s, shape, size, points, points_size);
+  rotate_shape_points (angle, shape, size, points, points_size);
+}
+
+
+/* Make shape denser to improve precision. */
+static interval* dense_shape (const interval* shape, const int size)
+{
+  interval* new_shape = calloc (2 * size, sizeof (interval));
+
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    double midx = (shape[i].start.x + shape[i].end.x) / 2;
+    double midy = (shape[i].start.y + shape[i].end.y) / 2;
+
+    new_shape[2*i].start.x = shape[i].start.x;
+    new_shape[2*i].start.y = shape[i].start.y;
+    new_shape[2*i].end.x = midx;
+    new_shape[2*i].end.y = midy;
+
+    new_shape[2*i+1].start.x = midx;
+    new_shape[2*i+1].start.y = midy;
+    new_shape[2*i+1].end.x = shape[i].end.x;
+    new_shape[2*i+1].end.y = shape[i].end.y;
+  }
+
+  return (new_shape);
+}
+
+
+/* Read shape from file. */
+static interval* fread_shape (FILE* file, int* size)
+{
+  fscanf (file, " START %i", size);
+
+  interval* shape = calloc (*size, sizeof (interval));
+  int i = 0;
+  for (i = 0; i < *size; i++) {
+    double x1, y1, x2, y2;
+    fscanf (file, " (%lf, %lf) -- (%lf, %lf)", &x1, &y1, &x2, &y2);
+    shape[i].start.x = x1;
+    shape[i].start.y = y1;
+    shape[i].end.x = x2;
+    shape[i].end.y = y2;
+  }  
+  fscanf (file, " END");
+
+  return (shape);
+}
+
+/* Move a string [n] spaces forward. */
+static int move_by_space (const int n, const char* s)
+{
+  int i = 0;
+  int j = 0;
+  for (j = 0; j < n; j++) {
+    while (s[i] == ' ') i++;
+    while (s[i] != ' ') i++;
+  }
+  return (i);
+}
+
+/* Read shape from string. */
+static interval* sread_shape (const char* str, int* size, int* offset)
+{
+  sscanf (str + *offset, " START %i", size);
+  *offset += move_by_space (2, str + *offset);
+
+  interval* shape = calloc (*size, sizeof (interval));
+  int i = 0;
+  for (i = 0; i < *size; i++) {
+    double x1, y1, x2, y2;
+    sscanf (str + *offset, " (%lf, %lf) -- (%lf, %lf)", &x1, &y1, &x2, &y2);
+    *offset += move_by_space (5, str + *offset);
+    shape[i].start.x = x1;
+    shape[i].start.y = y1;
+    shape[i].end.x = x2;
+    shape[i].end.y = y2;
+  }  
+  sscanf (str + *offset, " END");
+  *offset += move_by_space (1, str + *offset);
+
+  return (shape);
+}
+
+/* Print shape. */
+static void print_shape (const interval* shape, const int size)
+{
+  printf ("START %i\n", size);
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    printf ("(%lf, %lf) -- (%lf, %lf)\n", shape[i].start.x, shape[i].start.y,
+	    shape[i].end.x, shape[i].end.y);
+  }
+  printf ("END\n");
+}
+
+static void sprint_shape (char* s, const interval* shape, const int size)
+{
+  int o;
+  o = sprintf (s, "START %i\n", size);
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    o += sprintf (s+o, "(%lf, %lf) -- (%lf, %lf)\n",
+            shape[i].start.x, shape[i].start.y,
+	    shape[i].end.x, shape[i].end.y);
+  }
+  sprintf (s+o, "END\n");
+}
+
+
+/* Print points. */
+static void print_points (const point* points, const int size)
+{
+  printf ("START %i\n", size);
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    printf ("(%lf, %lf)\n", points[i].x, points[i].y);
+  }
+  printf ("END\n");
+}
+
+
+
+/* Structure to hold shape and pattern, parameters for minimization. */
+typedef struct shape_and_pattern_s {
+  interval* shape;
+  int shape_size;
+  point* shape_points;
+  int shape_points_size;
+  interval* pattern;
+  int pattern_size;
+  point* pattern_points;
+  int pattern_points_size;
+} shape_and_pattern;
+
+
+/* We compute a penalty for very disproportional scaling. */
+static double disproportional_scale_penalty (double x, double y)
+{
+  double max_penalty_factor = 8;
+  double max_prop_diff = 16;
+  double free_d = 1.5;
+
+  if ((x < 0.0001) && (y < 0.0001)) {
+    return (-1);
+  } else if (x < 0.0001) {
+    return (-1);
+  } else if (y < 0.0001) {
+    return (-1);
+  } else {
+    double prop_diff = max (0, min (max (x / y, y / x)-free_d, max_prop_diff));
+    return (1 + max_penalty_factor * (prop_diff / max_prop_diff));
+  }
+}
+
+/* Minimal and maximal allowed rotation for the current shape. */
+static double min_rotation = 0;
+static double max_rotation = 0;
+
+/* Compute the distance between moved, scaled, rotated pattern and shape. */
+static double move_scale_rotate_distance (const point t, const point s, 
+				   const double a, const shape_and_pattern* s_p)
+{
+  double scale_penalty = disproportional_scale_penalty (s.x, s.y);
+  if (scale_penalty < 0) { // Infinite penalty = forbidden scaling.
+    return (100 * 100 * 100);
+  }
+
+  if ((a < min_rotation) || (a > max_rotation)) { //Disallowed rotation.
+    return (100 * 100 * 100);
+  }
+
+  interval new_pattern[s_p->pattern_size];
+  point new_pattern_points[s_p->pattern_points_size];
+
+  int i;
+  for (i = 0; i < s_p->pattern_size; i++) {
+    new_pattern[i] = s_p->pattern[i];
+  }
+  for (i = 0; i < s_p->pattern_points_size; i++) {
+    new_pattern_points[i] = s_p->pattern_points[i];
+  }
+
+  move_scale_rotate_shape_points (t, s, a, new_pattern, s_p->pattern_size, 
+			   new_pattern_points, s_p->pattern_points_size);
+  double res = 
+    shape_distance_fast (new_pattern, s_p->pattern_size,
+			 new_pattern_points, s_p->pattern_points_size,
+			 s_p->shape, s_p->shape_size,
+			 s_p->shape_points, s_p->shape_points_size);
+
+
+  return (res * scale_penalty);
+}
+
+
+/* Places for results during iteration of minimizing functions. */
+static point current_best_move;
+static point current_best_scale;
+static double current_best_rot;
+/* Step values for minimization. */
+static point current_move_step;
+static point current_scale_step;
+static double current_rot_step;
+/* Current minimization value. */
+static double current_min_dist;
+
+static const double min_improvement_factor = 1.0000001;
+
+
+/* Try adjusting current_best_move by trying to move by the
+   current_move_step in both directions. Report if adjusted. */
+static int adjust_translation (const shape_and_pattern* s_p)
+{
+  int done_something = 0;
+  int best_x = 0;
+  int best_y = 0;
+  int i = 0;
+  
+  double scale_penalty = 
+    disproportional_scale_penalty (current_best_scale.x, current_best_scale.y);
+  if (scale_penalty < 0) {
+    return (0);
+  }
+
+  interval new_pattern[s_p->pattern_size];
+  point new_pattern_points[s_p->pattern_points_size];
+  for (i = 0; i < s_p->pattern_size; i++) {
+    new_pattern[i] = s_p->pattern[i];
+  }
+  for (i = 0; i < s_p->pattern_points_size; i++) {
+    new_pattern_points[i] = s_p->pattern_points[i];
+  }
+
+  point prev_move;
+  int prev_move_x = 0;
+  int prev_move_y = 0;
+  for (i = -3; i <= 3; i++) {
+    int j = 0;
+    for (j = -3; j <= 3; j++) {
+      point t = current_best_move;
+      t.x += current_move_step.x * (i - prev_move_x);
+      t.y += current_move_step.y * (j - prev_move_y);
+      double dist = current_min_dist;
+      if (((i != 0) || (j != 0)) && ((i == 0) || (j == 0))) {
+	move_shape_points (t, new_pattern, s_p->pattern_size, 
+			   new_pattern_points, s_p->pattern_points_size);
+	dist = 
+	  shape_distance_fast (new_pattern, s_p->pattern_size,
+			       new_pattern_points, s_p->pattern_points_size,
+			       s_p->shape, s_p->shape_size,
+			       s_p->shape_points, s_p->shape_points_size);
+	dist *= scale_penalty;
+
+	prev_move_x = i;
+	prev_move_y = j;
+      }
+      if (dist * min_improvement_factor < current_min_dist) {
+	best_x = i;
+	best_y = j;
+	current_min_dist = dist;
+	done_something = 1;
+      }
+    }
+  }
+
+  if (done_something) {
+    current_best_move.x += current_move_step.x * best_x;
+    current_best_move.y += current_move_step.y * best_y;
+    return (1);
+  } else {
+    return (0);
+  }
+}
+
+/* Try adjusting current_best_scale by trying to move by the
+   current_scale_step in both directions. Report if adjusted. */
+static int adjust_scale (const shape_and_pattern* params)
+{
+  int done_something = 0;
+  int best_x = 0;
+  int best_y = 0;
+  int i = 0;
+  for (i = -1; i <= 1; i++) {
+    int j = 0;
+    for (j = -1; j <= 1; j++) {
+      point s = current_best_scale;
+      s.x += current_scale_step.x * i;
+      s.y += current_scale_step.y * j;
+      double dist = current_min_dist + 1;
+      if (((i != 0) || (j != 0)) && ((i == 0) || (j == 0))) {
+	dist = move_scale_rotate_distance (current_best_move, s, 
+					   current_best_rot, params);
+      }
+      if (dist * min_improvement_factor < current_min_dist) {
+	best_x = i;
+	best_y = j;
+	current_min_dist = dist;
+	done_something = 1;
+      }
+    }
+  }
+
+  if (done_something) {
+    current_best_scale.x += current_scale_step.x * best_x;
+    current_best_scale.y += current_scale_step.y * best_y;
+    return (1);
+  } else {
+    return (0);
+  }
+}
+
+/* Try adjusting current_best_rot by trying to move by the
+   current_rot_step, plus or minus. */
+static int adjust_rotation (const shape_and_pattern* params)
+{
+  double dist1 = 
+    move_scale_rotate_distance (current_best_move, current_best_scale,
+				current_best_rot + current_rot_step, params);
+  double dist2 = 
+    move_scale_rotate_distance (current_best_move, current_best_scale,
+				current_best_rot - current_rot_step, params);
+
+  if ((dist1 * min_improvement_factor < current_min_dist) && (dist1 < dist2)) {
+    current_min_dist = dist1;
+    current_best_rot += current_rot_step;
+    return (1);
+  }
+  if (dist2 * min_improvement_factor < current_min_dist) {
+    current_min_dist = dist2;
+    current_best_rot -= current_rot_step;
+    return (1);
+  }
+  return (0);
+}
+
+
+/* Makes one step correction of current move, step and rot vectors. */
+static void correct_move_scale_rot_step (const shape_and_pattern* params)
+{
+  int should_adjust = 1;
+  int adjusted = 0;
+
+  should_adjust = adjust_scale (params);
+  while (should_adjust > 0) should_adjust = adjust_scale (params);
+
+  should_adjust = adjust_translation (params);
+  while (should_adjust > 0) should_adjust = adjust_translation (params);
+
+  should_adjust = adjust_rotation (params);
+  while (should_adjust > 0) {
+    adjusted = 1;
+    should_adjust = adjust_rotation (params);
+  }
+
+  if (adjusted) {
+    if (adjust_scale (params) > 0) adjust_rotation (params);
+  }
+}
+
+/* Minimize distance between moved and scaled and rotated pattern and shape.
+   Starts with and changes the current_best_{move,scale,rot} variables. */
+static double find_minimal_dist_rot (const shape_and_pattern* params, 
+			      const int no_iter)
+{
+  current_min_dist = 
+    move_scale_rotate_distance (current_best_move, current_best_scale, 
+				current_best_rot, params);
+
+  int iters = 0;
+  while (iters < no_iter) {
+    int should_stop = 0;
+    pthread_mutex_lock (&shapes_stop_mutex);
+    should_stop = stop_signal;
+    pthread_mutex_unlock (&shapes_stop_mutex);
+
+    if (should_stop) { return (current_min_dist); }
+
+    correct_move_scale_rot_step (params);
+    current_move_step.x /= 4;
+    current_move_step.y /= 4;
+    current_scale_step.x /= 4;
+    current_scale_step.y /= 4;
+    current_rot_step /= 4;
+    iters++;
+  }
+
+  return (current_min_dist);
+}
+
+
+/* Find scale factor given pattern and shape dimensions. */
+static point find_scale (const point pattern_dim, const point shape_dim) {
+  point res;
+  if ((pattern_dim.x < 0.01) && (pattern_dim.y < 0.01)) {
+    res.x = 1;
+    res.y = 1;
+  } else if (pattern_dim.x < 0.01) {
+    res.x = shape_dim.y / pattern_dim.y;
+    res.y = shape_dim.y / pattern_dim.y;
+  } else if (pattern_dim.y < 0.01) {
+    res.x = shape_dim.x / pattern_dim.x;
+    res.y = shape_dim.x / pattern_dim.x;
+  } else {
+    res.x = shape_dim.x / pattern_dim.x;
+    res.y = shape_dim.y / pattern_dim.y;
+  }
+  return (res);
+}
+
+/* Find best fit (scale and translation) between shape and pattern. */
+static interval best_fit (interval* shape, const int s_size, interval* pattern, 
+		   const int p_size, const int no_iter, double* metric,
+		   double* rotation)
+{
+  shape_and_pattern params;
+  int points_size = 0;
+  params.shape = shape;
+  params.shape_size = s_size;
+  params.shape_points = shape_points (shape, s_size, &points_size);
+  params.shape_points_size = points_size;
+
+  params.pattern = pattern;
+  params.pattern_size = p_size;
+  params.pattern_points = shape_points (pattern, p_size, &points_size);
+  params.pattern_points_size = points_size;
+
+  interval shape_mids = mid_dimen (shape, s_size);
+  interval pattern_mids = mid_dimen (pattern, p_size);
+
+  point d_move;
+  d_move.x = shape_mids.start.x - pattern_mids.start.x;
+  d_move.y = shape_mids.start.y - pattern_mids.start.y;
+  point d_scale = find_scale (pattern_mids.end, shape_mids.end);
+  double d_rot = 0;
+
+
+  // Determine initial best rotation.
+  if (max_rotation - min_rotation > M_PI / 8) {
+    int rotate_try_size = 
+      ((int) 16 * ((max_rotation - min_rotation + 0.001) / (2 * M_PI)));
+    if (rotate_try_size == 0) rotate_try_size = 1;
+    interval check_pattern[p_size];
+    point tmp_scale;
+    double cur_best = 0;
+    double cur_dist =  move_scale_rotate_distance (d_move, d_scale, 0, &params);
+    double angle = 0;
+    for (angle = min_rotation; angle < max_rotation + 0.0001;
+	 angle += (max_rotation - min_rotation) / rotate_try_size) {
+      int j = 0;
+      for (j = 0; j < p_size; j++) {
+	check_pattern[j] = pattern[j];
+      }
+      rotate_shape (angle, check_pattern, p_size);
+      
+      interval check_mids = mid_dimen (check_pattern, p_size);
+      tmp_scale = find_scale (check_mids.end, shape_mids.end);
+      
+      double dist = 
+	move_scale_rotate_distance (d_move, tmp_scale, angle, &params);
+      if (dist < cur_dist) {
+	cur_best = angle;
+	d_scale = tmp_scale;
+	cur_dist = dist;
+      }
+    }
+    d_rot = cur_best;
+  }
+
+  // Set start and step values.
+  current_best_move = d_move;
+  current_best_scale = d_scale;
+  current_best_rot = d_rot;
+  current_move_step.x = (d_move.x > 1 ? d_move.x / 8 : 0.1);
+  current_move_step.y = (d_move.y > 1 ? d_move.y / 8 : 0.1);
+  current_scale_step.x = (d_scale.x > 0.1 ? d_scale.x / 8 : 0.01);
+  current_scale_step.y = (d_scale.y > 0.1 ? d_scale.y / 8 : 0.01);
+  current_rot_step = M_PI / 16;
+
+  *metric = find_minimal_dist_rot (&params, no_iter);
+
+  double shape_density = s_size /
+    ((shape_mids.end.x + 0.001) * (shape_mids.end.y + 0.001));
+  *metric = (*metric) * sqrt (shape_density) * 6;
+
+  interval res;
+  res.start = current_best_move;
+  res.end = current_best_scale;
+  *rotation = current_best_rot;
+
+  free (params.shape_points);
+  free (params.pattern_points);
+
+  return (res);
+}
+
+
+/* Shape management and fitting. */
+
+/* Storing shape patterns here. */
+static shape* patterns;
+static int no_patts = 0;
+shape* get_patterns () { return (patterns); }
+static int no_patterns () { return (no_patts); }
+
+/* Global scaling factor for distance. */
+static double scale_factor = 1;
+static double get_scale_factor () { return (scale_factor); }
+static void set_scale_factor (double s) { scale_factor = s; }
+
+/* Results will be put here. */
+static interval res_vec;
+static double res_min;
+static double res_rot;
+static point get_res_move () { return (res_vec.start); }
+static point get_res_scale () { return (res_vec.end); }
+static double get_res_rot () { return (res_rot); }
+static double get_res_min () { return (res_min); }
+
+/* How long to look for best fit. */
+static int number_of_iterations = 4;
+static int get_no_iterations () { return (number_of_iterations); }
+static void set_no_iterations (int n) { number_of_iterations = n; }
+
+/* Below what size should we make patterns denser. */
+static const int densing_size = 12;
+
+/* Initialize shape patterns from file. */
+static void init_patterns_from_file (const char* fname)
+{
+  const char mode = 'r';
+  FILE* file = fopen (fname, &mode);
+
+  pthread_mutex_init (&shapes_stop_mutex, PTHREAD_MUTEX_TIMED_NP);
+  pthread_mutex_init (&shapes_working_mutex, PTHREAD_MUTEX_TIMED_NP);
+  pthread_mutex_init (&shapes_painting_mutex, PTHREAD_MUTEX_TIMED_NP);
+
+  fscanf (file, " SHAPES %i PRECISION %i RECO FACTOR %lf", 
+	  &no_patts, &number_of_iterations, &scale_factor);
+  patterns = calloc (no_patts, sizeof(shape));
+  
+  int i = 0;
+  int j = 0;
+  for (i = 0; i < no_patts; i++) {
+    int shape_size = 0;
+    double max_dist = 0;
+
+    fscanf (file, " SHAPE %s MAXDIST %lf CORRECTION %lf SCALE DEVIATION %lf",
+	    patterns[i].name, &patterns[i].max_dist, &patterns[i].correction,
+	    &patterns[i].scale_correction);
+    // printf ("Reading %s.\n", patterns[i].name);
+    fscanf (file, " ROTATION MIN %lf MAX %lf DENSITY %lf",
+	    &patterns[i].min_rotation, &patterns[i].max_rotation,
+	    &patterns[i].rotation_density);
+    patterns[i].min_rotation = M_PI * patterns[i].min_rotation / 180;
+    patterns[i].max_rotation = M_PI * patterns[i].max_rotation / 180;
+    patterns[i].rotation_density = M_PI * patterns[i].rotation_density / 180;
+    if (patterns[i].correction < 0) patterns[i].correction = 0;
+
+    interval* shape = fread_shape (file, &shape_size);
+
+    while (shape_size <= densing_size) {
+      interval* new_shape = dense_shape (shape, shape_size);
+      free (shape);
+      shape = new_shape;
+      shape_size *= 2;
+    }
+
+    patterns[i].shape = shape;
+    patterns[i].size = shape_size;
+  }
+  
+  fclose (file);
+}
+
+/* Initialize shape patterns from string. */
+static void init_patterns_from_string (const char* str)
+{
+  int offset = 0;
+
+  pthread_mutex_init (&shapes_stop_mutex, PTHREAD_MUTEX_TIMED_NP);
+  pthread_mutex_init (&shapes_working_mutex, PTHREAD_MUTEX_TIMED_NP);
+
+  sscanf (str + offset, " SHAPES %i PRECISION %i RECO FACTOR %lf", 
+	  &no_patts, &number_of_iterations, &scale_factor);
+  offset += move_by_space (7, str + offset);
+  patterns = calloc (no_patts, sizeof(shape));
+
+  int i = 0;
+  int j = 0;
+  for (i = 0; i < no_patts; i++) {
+    int shape_size = 0;
+    double max_dist = 0;
+
+    sscanf (str + offset, 
+	    " SHAPE %s MAXDIST %lf CORRECTION %lf SCALE DEVIATION %lf",
+	    patterns[i].name, &patterns[i].max_dist, &patterns[i].correction,
+	    &patterns[i].scale_correction);
+    offset += move_by_space (9, str + offset);
+    // printf ("Reading %s.\n", patterns[i].name);
+    sscanf (str + offset, " ROTATION MIN %lf MAX %lf DENSITY %lf",
+	    &patterns[i].min_rotation, &patterns[i].max_rotation,
+	    &patterns[i].rotation_density);
+    offset += move_by_space (7, str + offset);
+    patterns[i].min_rotation = M_PI * patterns[i].min_rotation / 180;
+    patterns[i].max_rotation = M_PI * patterns[i].max_rotation / 180;
+    patterns[i].rotation_density = M_PI * patterns[i].rotation_density / 180;
+    if (patterns[i].correction < 0) patterns[i].correction = 0;
+
+    interval* shape = sread_shape (str, &shape_size, &offset);
+
+    while (shape_size <= densing_size) {
+      interval* new_shape = dense_shape (shape, shape_size);
+      free (shape);
+      shape = new_shape;
+      shape_size *= 2;
+    }
+
+    patterns[i].shape = shape;
+    patterns[i].size = shape_size;
+  }
+}
+
+/* Free shape patterns storage. */
+static void free_patterns ()
+{
+  no_patts = 0;
+  free (patterns);
+}
+
+static double prev_scale = 1;
+
+/* Find best matching pattern for the given shape.
+   Return pattern number if there is one or -1 else.
+   The required translation and scale are put in res_vec. */
+static int match_pattern (interval* shape, const int size)
+{
+  double min = 0;
+  res_min = -2;
+  int res = -1;
+  int i = 0;
+
+  for (i = 0; i < no_patts; i++) {
+    int should_stop = 0;
+    pthread_mutex_lock (&shapes_stop_mutex);
+    should_stop = stop_signal;
+    pthread_mutex_unlock (&shapes_stop_mutex);
+
+    if (should_stop) { return (-1); }
+
+    min_rotation = patterns[i].min_rotation;
+    max_rotation = patterns[i].max_rotation;
+    double rot = 0;
+    interval fit = best_fit (shape, size, patterns[i].shape, patterns[i].size,
+			     number_of_iterations, &min, &rot);
+    if (rot < 0) rot += 2 * M_PI;
+    if (min > 2*patterns[i].correction) min -= patterns[i].correction;
+    min /= scale_factor;
+    //printf ("Distance to pattern %s: %lf.\n", patterns[i].name, min);
+    if ((min <= patterns[i].max_dist) && 
+	((min < res_min) || (res_min < -1))) {
+      res_min = min;
+      res_rot = rot;
+      res_vec = fit;
+      res = i;
+    }
+  }
+  // printf ("\n");
+
+  if (res > -1) {
+    // Scale correction.
+    if ((res_vec.end.x > 0.0001) && (res_vec.end.y > 0.0001)) {
+      double quot = res_vec.end.x / res_vec.end.y;
+      double scale_correction = patterns[res].scale_correction;
+      if ((1 - scale_correction < quot) && (quot < 1 + scale_correction)) {
+	double q_pre = 2 * prev_scale / (res_vec.end.x + res_vec.end.y);
+	if ((1 - scale_correction < q_pre) && (q_pre < 1 + scale_correction)) {
+	  res_vec.end.x = prev_scale;
+	  res_vec.end.y = prev_scale;
+	} else {
+	  res_vec.end.x = (res_vec.end.x + res_vec.end.y) / 2;
+	  res_vec.end.y = res_vec.end.x;
+	  prev_scale = res_vec.end.x;
+	}
+      }
+    }
+
+    // Rotation correction.
+    double rot_density = patterns[res].rotation_density;
+    if (rot_density > 0) {
+      res_rot = rint (res_rot / rot_density) * rot_density;
+    }
+  }
+
+  return (res);
+}
+
+/* Determine if two intervals can be merged looking at the angle they form. */
+static double merge_possibility (interval i1, interval i2)
+{
+  if ((i1.end.x != i2.start.x) || (i1.end.y != i2.start.y)) {
+    return (4);
+  } else {
+    double angle1 = atan2 (i1.start.y - i1.end.y, i1.start.x - i1.end.x);
+    double angle2 = atan2 (i2.end.y - i1.end.y, i2.end.x - i1.end.x);
+    return (fabs (fabs (angle1 - angle2) - M_PI));
+  }
+}
+
+/* The angle in degrees from which on we decide to merge. */
+static const double merge_degrees = 3;
+
+/* Decrease the size of the shape when possible, one step. */
+static interval* downsize_shape_step (const interval* shape, const int size,
+			       int* new_size)
+{
+  double merge_diff = (M_PI * merge_degrees) / 180;
+  interval new_shape[size];
+
+  int i = 0;
+  int j = 0;
+  for (i = 0; i < size-1; i++) {
+    if (merge_possibility (shape[i], shape[i+1]) < merge_diff) {
+      new_shape[j].start = shape[i].start;
+      new_shape[j].end = shape[i+1].end;
+      j++;
+      i++;
+    } else {
+      new_shape[j] = shape[i];
+      j++;
+    }
+  }
+  if (i < size) { new_shape[j] = shape[i]; j++; }
+  *new_size = j;
+  
+  interval* res_shape = calloc (*new_size, sizeof (interval));
+  for (i = 0; i < *new_size; i++) {
+    res_shape[i] = new_shape[i];
+  }
+  
+  return (res_shape);
+}
+
+/* Decrease the size of the shape when possible, one step. */
+static interval* downsize_shape (const interval* shape, const int size,
+			  int* final_size)
+{
+  int prev_size = size;
+  int cur_size = 0;
+  interval* cur_shape = downsize_shape_step (shape, size, &cur_size);
+
+  while (cur_size != prev_size) {
+    int new_size = 0;
+    interval* new_shape = downsize_shape_step (cur_shape, cur_size, &new_size);
+    prev_size = cur_size;
+    free (cur_shape);
+    cur_shape = new_shape;
+    cur_size = new_size;
+  }
+
+  *final_size = cur_size;
+  return (cur_shape);
+}
+
+/* Find best matching pattern for the given line segments.
+   Return pattern number if there is one or -1 else.
+   Combine with the previous pattern if [next] is set.
+   The required translation, scale, rotation are put in res_{move,scale,rot}. */
+static interval* current_lin_shape = NULL;
+static int current_lin_shape_size = 0;
+static interval* get_recent_shape () { return (current_lin_shape); }
+static int get_recent_shape_size () { return (current_lin_shape_size); }
+
+static int match_pattern_line (const double* segments, const int size, const int next)
+{
+  interval* shape;
+  int start;
+
+  if ((current_lin_shape_size > 0) && (next)) {
+    shape = calloc (current_lin_shape_size + size-1, sizeof (interval));
+    start = current_lin_shape_size;
+  } else {
+    shape = calloc (size-1, sizeof (interval));
+    start = 0;
+  }
+ 
+
+  int i = 0;
+  for (i = 0; i < start; i++) {
+    shape[i] = current_lin_shape[i];
+  }
+  for (i = 0; i < size-1; i++) {
+    shape[i+start].start.x = segments[2*i];
+    shape[i+start].start.y = segments[2*i+1];
+    shape[i+start].end.x = segments[2*i+2];
+    shape[i+start].end.y = segments[2*i+3];
+  }
+
+  free (current_lin_shape);
+
+  current_lin_shape = 
+    downsize_shape (shape, start+size-1, &current_lin_shape_size);
+
+  free (shape);
+
+  return (match_pattern (current_lin_shape, current_lin_shape_size));
+}
+
+static void stop_recognition_forced ()
+{
+  pthread_mutex_lock (&shapes_stop_mutex);
+  stop_signal = 1;
+  pthread_mutex_unlock (&shapes_stop_mutex);
+  
+  pthread_mutex_lock (&shapes_working_mutex);
+  pthread_mutex_unlock (&shapes_working_mutex);
+}
+
+static void stop_recognition (int milisec)
+{
+  stop_recognition_forced ();
+  int failed_lock = pthread_mutex_trylock (&shapes_working_mutex);
+
+  int i = 0;
+  while ((failed_lock > 0) && (i < milisec)) {
+    usleep (10000);
+    i++;
+    failed_lock = pthread_mutex_trylock (&shapes_working_mutex);
+  }
+
+  if (failed_lock > 0) {
+    stop_recognition_forced ();
+  } else {
+    pthread_mutex_unlock (&shapes_working_mutex);
+  }
+}
+
+static void stop_recognition_now ()
+{
+  if (pthread_mutex_trylock (&shapes_working_mutex) == 0) {
+    pthread_mutex_unlock (&shapes_working_mutex);
+  } else { 
+    stop_recognition_forced ();
+  } 
+}
+
+int status_recognize = 0;
+void set_recognize (int onoff) { status_recognize = onoff; }
+int should_recognize () { return (status_recognize); }
+
+/* Default patterns. */
+
+/* There are 35 shapes with letters, but we skip letters and use only 10. */
+/*(-3, -3) -- (-3, 3) \
+(-3, 3) -- (3, 3) \
+(3, 3) -- (3, -3) \
+(3, -3) -- (-3, -3) \ */
+static const char* default_shape_patterns = "\
+SHAPES 1 \
+PRECISION 4 \
+RECO FACTOR 1.6 \
+ \
+SHAPE grid3 MAXDIST 900 CORRECTION 2 \
+SCALE DEVIATION 0 \
+ROTATION MIN -1 MAX 1 DENSITY 0 \
+START 8 \
+(-3, -3) -- (-3, 3) \
+(-3, 3) -- (3, 3) \
+(3, 3) -- (3, -3) \
+(3, -3) -- (-3, -3) \
+(-1, -3) -- (-1, 3) \
+(1, -3) -- (1, 3) \
+(-3, -1) -- (3, -1) \
+(-3, 1) -- (3, 1) \
+END \
+ \
+SHAPE grid3mid MAXDIST 900 CORRECTION 1 \
+SCALE DEVIATION 0.2 \
+ROTATION MIN -10 MAX 10 DENSITY 0 \
+START 6 \
+(-1, -3) -- (-1, 3) \
+(1, -3) -- (1, 3) \
+(-3, -1) -- (3, -1) \
+(-3, 1) -- (3, 1) \
+(0.8, 0.8) -- (-0.8, -0.8) \
+(0.8, -0.8) -- (-0.8, 0.8) \
+END \
+ \
+SHAPE arrow2 MAXDIST 9 CORRECTION 2.2 \
+SCALE DEVIATION 0 \
+ROTATION MIN -180 MAX 180 DENSITY 0 \
+START 7 \
+(0, -2) -- (0, -1) \
+(0, -1) -- (0, 0) \
+(0, 0) -- (0, 1) \
+(0, 1) -- (0, 2) \
+(0, 2) -- (-0.5, 1.5) \
+(-0.5, 1.5) -- (0, 2) \
+(0, 2) -- (0.5, 1.5) \
+END \
+ \
+ \
+SHAPE backarrow1 MAXDIST 9 CORRECTION 1.6 \
+SCALE DEVIATION 0 \
+ROTATION MIN -180 MAX 180 DENSITY 0 \
+START 18 \
+(0.75, 0.25) -- (1, 0) \
+(1, 0) -- (1.25, 0.25) \
+(1.25, 0.25) -- (1, 0) \
+(1.000000, 0.000000) -- (0.951057, 0.309017) \
+(0.951057, 0.309017) -- (0.809017, 0.587785) \
+(0.809017, 0.587785) -- (0.587785, 0.809017) \
+(0.587785, 0.809017) -- (0.309017, 0.951057) \
+(0.309017, 0.951057) -- (0.000000, 1.000000) \
+(0.000000, 1.000000) -- (-0.309017, 0.951057) \
+(-0.309017, 0.951057) -- (-0.587785, 0.809017) \
+(-0.587785, 0.809017) -- (-0.809017, 0.587785) \
+(-0.809017, 0.587785) -- (-0.951057, 0.309017) \
+(-0.951057, 0.309017) -- (-1.000000, 0.000000) \
+(-1.000000, 0.000000) -- (-0.951057, -0.309017) \
+(-0.951057, -0.309017) -- (-0.809017, -0.587785) \
+(-0.809017, -0.587785) -- (-0.587785, -0.809017) \
+(-0.587785, -0.809017) -- (-0.309017, -0.951057) \
+(-0.309017, -0.951057) -- (-0.000000, -1.000000) \
+END \
+ \
+ \
+SHAPE backarrow2 MAXDIST 9 CORRECTION 1.6 \
+SCALE DEVIATION 0 \
+ROTATION MIN -180 MAX 180 DENSITY 0 \
+START 18 \
+(1.000000, 0.000000) -- (0.951057, 0.309017) \
+(0.951057, 0.309017) -- (0.809017, 0.587785) \
+(0.809017, 0.587785) -- (0.587785, 0.809017) \
+(0.587785, 0.809017) -- (0.309017, 0.951057) \
+(0.309017, 0.951057) -- (0.000000, 1.000000) \
+(0.000000, 1.000000) -- (-0.309017, 0.951057) \
+(-0.309017, 0.951057) -- (-0.587785, 0.809017) \
+(-0.587785, 0.809017) -- (-0.809017, 0.587785) \
+(-0.809017, 0.587785) -- (-0.951057, 0.309017) \
+(-0.951057, 0.309017) -- (-1.000000, 0.000000) \
+(-1.000000, 0.000000) -- (-0.951057, -0.309017) \
+(-0.951057, -0.309017) -- (-0.809017, -0.587785) \
+(-0.809017, -0.587785) -- (-0.587785, -0.809017) \
+(-0.587785, -0.809017) -- (-0.309017, -0.951057) \
+(-0.309017, -0.951057) -- (-0.000000, -1.000000) \
+(0, -1) -- (-0.25, -0.75) \
+(-0.25, -0.75) -- (0, -1) \
+(0, -1) -- (-0.25, -1.25) \
+END \
+ \
+ \
+SHAPE bentarrow1 MAXDIST 9 CORRECTION 2 \
+SCALE DEVIATION 0 \
+ROTATION MIN -180 MAX 180 DENSITY 0 \
+START 11 \
+(0.751057, 0.309017) -- (0.951057, 0.309017) \
+(0.951057, 0.309017) -- (0.951057, 0.509017) \
+(0.951057, 0.509017) -- (0.951057, 0.309017) \
+(0.951057, 0.309017) -- (0.809017, 0.587785) \
+(0.809017, 0.587785) -- (0.587785, 0.809017) \
+(0.587785, 0.809017) -- (0.309017, 0.951057) \
+(0.309017, 0.951057) -- (0.000000, 1.000000) \
+(0.000000, 1.000000) -- (-0.309017, 0.951057) \
+(-0.309017, 0.951057) -- (-0.587785, 0.809017) \
+(-0.587785, 0.809017) -- (-0.809017, 0.587785) \
+(-0.809017, 0.587785) -- (-0.951057, 0.309017) \
+END \
+ \
+ \
+SHAPE bentarrow2 MAXDIST 9 CORRECTION 2 \
+SCALE DEVIATION 0 \
+ROTATION MIN -180 MAX 180 DENSITY 0 \
+START 11 \
+(0.951057, 0.309017) -- (0.809017, 0.587785) \
+(0.809017, 0.587785) -- (0.587785, 0.809017) \
+(0.587785, 0.809017) -- (0.309017, 0.951057) \
+(0.309017, 0.951057) -- (0.000000, 1.000000) \
+(0.000000, 1.000000) -- (-0.309017, 0.951057) \
+(-0.309017, 0.951057) -- (-0.587785, 0.809017) \
+(-0.587785, 0.809017) -- (-0.809017, 0.587785) \
+(-0.809017, 0.587785) -- (-0.951057, 0.309017) \
+(-0.951057, 0.309017) -- (-0.951057, 0.509017) \
+(-0.951057, 0.509017) -- (-0.951057, 0.309017) \
+(-0.951057, 0.309017) -- (-0.751057, 0.309017) \
+END \
+ \
+ \
+SHAPE triangle MAXDIST 8 CORRECTION 1.7 \
+SCALE DEVIATION 0.2 \
+ROTATION MIN -180 MAX 180 DENSITY 30 \
+START 6 \
+(0, 0) -- (1, 0) \
+(1, 0) -- (2, 0) \
+(2, 0) -- (1.5, 0.866025) \
+(1.5, 0.866025) -- (1, 1.732051) \
+(1, 1.732051) -- (0.5, 0.866025) \
+(0.5, 0.866025) -- (0, 0) \
+END \
+ \
+ \
+SHAPE rectangle MAXDIST 7 CORRECTION 0.8 \
+SCALE DEVIATION 0.35 \
+ROTATION MIN -45 MAX 45 DENSITY 45 \
+START 8 \
+(0, 0) -- (0, 1) \
+(0, 1) -- (0, 2) \
+(0, 2) -- (1, 2) \
+(1, 2) -- (2, 2) \
+(2, 2) -- (2, 1) \
+(2, 1) -- (2, 0) \
+(2, 0) -- (1, 0) \
+(1, 0) -- (0, 0) \
+END \
+ \
+SHAPE circle MAXDIST 7 CORRECTION 0 \
+SCALE DEVIATION 0.35 \
+ROTATION MIN -45 MAX 45 DENSITY 90 \
+START 41 \
+(1.000000, 0.000000) -- (0.988280, 0.152649) \
+(0.988280, 0.152649) -- (0.953396, 0.301721) \
+(0.953396, 0.301721) -- (0.896166, 0.443720) \
+(0.896166, 0.443720) -- (0.817929, 0.575319) \
+(0.817929, 0.575319) -- (0.720522, 0.693433) \
+(0.720522, 0.693433) -- (0.606225, 0.795293) \
+(0.606225, 0.795293) -- (0.477720, 0.878512) \
+(0.477720, 0.878512) -- (0.338017, 0.941140) \
+(0.338017, 0.941140) -- (0.190391, 0.981708) \
+(0.190391, 0.981708) -- (0.038303, 0.999266) \
+(0.038303, 0.999266) -- (-0.114683, 0.993402) \
+(-0.114683, 0.993402) -- (-0.264982, 0.964253) \
+(-0.264982, 0.964253) -- (-0.409069, 0.912504) \
+(-0.409069, 0.912504) -- (-0.543568, 0.839365) \
+(-0.543568, 0.839365) -- (-0.665326, 0.746553) \
+(-0.665326, 0.746553) -- (-0.771489, 0.636242) \
+(-0.771489, 0.636242) -- (-0.859570, 0.511019) \
+(-0.859570, 0.511019) -- (-0.927502, 0.373817) \
+(-0.927502, 0.373817) -- (-0.973695, 0.227854) \
+(-0.973695, 0.227854) -- (-0.997066, 0.076549) \
+(-0.997066, 0.076549) -- (-0.997066, -0.076549) \
+(-0.997066, -0.076549) -- (-0.973695, -0.227854) \
+(-0.973695, -0.227854) -- (-0.927502, -0.373817) \
+(-0.927502, -0.373817) -- (-0.859570, -0.511019) \
+(-0.859570, -0.511019) -- (-0.771489, -0.636242) \
+(-0.771489, -0.636242) -- (-0.665326, -0.746553) \
+(-0.665326, -0.746553) -- (-0.543568, -0.839365) \
+(-0.543568, -0.839365) -- (-0.409069, -0.912504) \
+(-0.409069, -0.912504) -- (-0.264982, -0.964253) \
+(-0.264982, -0.964253) -- (-0.114683, -0.993402) \
+(-0.114683, -0.993402) -- (0.038303, -0.999266) \
+(0.038303, -0.999266) -- (0.190391, -0.981708) \
+(0.190391, -0.981708) -- (0.338017, -0.941140) \
+(0.338017, -0.941140) -- (0.477720, -0.878512) \
+(0.477720, -0.878512) -- (0.606225, -0.795293) \
+(0.606225, -0.795293) -- (0.720522, -0.693433) \
+(0.720522, -0.693433) -- (0.817929, -0.575319) \
+(0.817929, -0.575319) -- (0.896166, -0.443720) \
+(0.896166, -0.443720) -- (0.953396, -0.301721) \
+(0.953396, -0.301721) -- (0.988280, -0.152649) \
+(0.988280, -0.152649) -- (1.000000, -0.000000) \
+END \
+ \
+SHAPE A MAXDIST 8 CORRECTION 2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(0.5, 4) -- (0.2, 4) \
+(0.2, 4) -- (-1.5, 0) \
+(0.5, 4) -- (1.5, 0) \
+(-0.8, 2) -- (1.2, 2) \
+END \
+ \
+SHAPE B MAXDIST 8 CORRECTION 3.6 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 11 \
+(0, 4) -- (0, 0) \
+(0, 0) -- (1.5, 0) \
+(1.5, 0) -- (2.2, 0.5) \
+(2.2, 0.5) -- (2.4, 1.1) \
+(2.4, 1.1) -- (2.2, 1.7) \
+(2.2, 1.7) -- (1.5, 2.2) \
+(1.5, 2.2) -- (1.2, 2.2) \
+(1.2, 2.2) -- (1.8, 3.1) \
+(1.8, 3.1) -- (1.2, 4) \
+(1.2, 4) -- (0, 4) \
+(0, 2.2) -- (1.2, 2.2) \
+END \
+ \
+SHAPE C MAXDIST 8 CORRECTION 2.2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 8 \
+(3, 0.8) -- (2, 0) \
+(2, 0) -- (1, 0) \
+(1, 0) -- (0, 1) \
+(0, 1) -- (0, 2) \
+(0, 2) -- (0, 3) \
+(0, 3) -- (1, 4) \
+(1, 4) -- (2, 4) \
+(2, 4) -- (2.5, 3.5) \
+END \
+ \
+SHAPE D MAXDIST 8 CORRECTION 2.4 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 7 \
+(0, 4) -- (0, 2) \
+(0, 2) -- (0, 0) \
+(0, 0) -- (1, 0) \
+(1, 0) -- (2, 0.8) \
+(2, 0.8) -- (2, 2.8) \
+(2, 2.8) -- (1, 4) \
+(1, 4) -- (0, 4) \
+END \
+ \
+SHAPE E MAXDIST 8 CORRECTION 2.6 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 5 \
+(0, 4) -- (0, 0) \
+(2, 0) -- (0, 0) \
+(0, 0) -- (0, 2) \
+(1.5, 2) -- (0, 2) \
+(0, 4) -- (2, 4) \
+END \
+ \
+SHAPE F MAXDIST 8 CORRECTION 3.8 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(0, 0) -- (0, 4) \
+(0, 4) -- (2.5, 4) \
+(2.5, 4) -- (2.5, 3.8) \
+(0, 1.9) -- (1.8, 1.9) \
+END \
+ \
+SHAPE G MAXDIST 8 CORRECTION 3.4 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 9 \
+(2, 4) -- (1, 4) \
+(1, 4) -- (0, 3) \
+(0, 3) -- (0, 2) \
+(0, 2) -- (0, 1) \
+(0, 1) -- (1, 0) \
+(1, 0) -- (2, 0) \
+(2, 0) -- (2.5, 2) \
+(2.5, 2) -- (1.5, 2) \
+(1.5, 2) -- (3.5, 2) \
+END \
+ \
+SHAPE H MAXDIST 8 CORRECTION 2.4 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(0, 4) -- (0, 0) \
+(2.5, 4) -- (2.5, 0) \
+(0, 1.8) -- (1.5, 1.8) \
+(1.5, 1.8) -- (2.5, 2) \
+END \
+ \
+SHAPE I MAXDIST 8 CORRECTION 3.2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 3 \
+(-1, 0) -- (1, 0) \
+(0, 0) -- (0, 4) \
+(-1, 4) -- (1, 4) \
+END \
+ \
+SHAPE J MAXDIST 8 CORRECTION 3.8 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(-2, 4) -- (0, 4) \
+(0, 4) -- (0, 1) \
+(0, 1) -- (-1, 0) \
+(-1, 0) -- (-2, 1) \
+END \
+ \
+SHAPE K MAXDIST 8 CORRECTION 1.5 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 3 \
+(0, 4) -- (0, 0) \
+(0, 1) -- (3, 4) \
+(0.5, 1.5) -- (3, 0) \
+END \
+ \
+SHAPE L MAXDIST 8 CORRECTION 2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 2 \
+(0, 4) -- (0, 0) \
+(0, 0) -- (2, 0) \
+END \
+ \
+SHAPE M MAXDIST 8 CORRECTION 2.5 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 6 \
+(0, 0) -- (0, 4) \
+(0, 4) -- (1.2, 2.2) \
+(1.2, 2.2) -- (1.5, 2) \
+(1.5, 2) -- (1.8, 2.2) \
+(1.8, 2.2) -- (3, 4) \
+(3, 4) -- (3, 0) \
+END \
+ \
+SHAPE N MAXDIST 8 CORRECTION 2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(0, 0) -- (0, 4) \
+(0, 4) -- (2, 0.5) \
+(2, 0.5) -- (2.5, 1) \
+(2.5, 1) -- (2.8, 4) \
+END \
+ \
+SHAPE P MAXDIST 8 CORRECTION 1.5 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 6 \
+(0, 0) -- (0, 4) \
+(0, 4) -- (1, 4) \
+(1, 4) -- (2, 3.5) \
+(2, 3.5) -- (2, 2.5) \
+(2, 2.5) -- (1, 2) \
+(1, 2) -- (0, 2) \
+END \
+ \
+SHAPE Q MAXDIST 8 CORRECTION 3.4 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 9 \
+(2, 0) -- (1, 0) \
+(1, 0) -- (0, 1) \
+(0, 1) -- (0, 3) \
+(0, 3) -- (1, 4) \
+(1, 4) -- (2, 4) \
+(2, 4) -- (3, 3) \
+(3, 3) -- (3, 1) \
+(3, 1) -- (2, 0) \
+(2, 1) -- (4, 0) \
+END \
+ \
+SHAPE R MAXDIST 8 CORRECTION 2.2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 7 \
+(0, 0) -- (0, 4) \
+(0, 4) -- (1, 4) \
+(1, 4) -- (2, 3.5) \
+(2, 3.5) -- (2, 2.5) \
+(2, 2.5) -- (1, 2) \
+(1, 2) -- (0, 2) \
+(0, 2) -- (2, 0) \
+END \
+ \
+SHAPE S MAXDIST 8 CORRECTION 2.6 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 8 \
+(1.5, 3.5) -- (1, 4) \
+(1, 4) -- (0, 4) \
+(0, 4) -- (-1, 3) \
+(-1, 3) -- (0, 2) \
+(0, 2) -- (1, 1) \
+(1, 1) -- (0, 0) \
+(0, 0) -- (-1, 0) \
+(-1, 0) -- (-1.5, 0.5) \
+END \
+ \
+SHAPE T MAXDIST 8 CORRECTION 5.8 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(1.4, 3.8) -- (1.4, 4) \
+(1.4, 4) -- (-1.4, 4) \
+(-1.4, 4) -- (-1.4, 3.8) \
+(0, 4) -- (0, 0) \
+END \
+ \
+SHAPE U MAXDIST 8 CORRECTION 1.7 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 6 \
+(1, 4) -- (1, 1.5) \
+(1, 1.5) -- (1.4, 0) \
+(1, 1.5) -- (0, 0) \
+(0, 0) -- (-0.5, 0) \
+(-0.5, 0) -- (-1, 1) \
+(-1, 1) -- (-1, 4) \
+END \
+ \
+SHAPE V MAXDIST 8 CORRECTION 1.6 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 2 \
+(1.5, 4.5) -- (0, 0) \
+(-1, 4) -- (0, 0) \
+END \
+ \
+SHAPE W MAXDIST 8 CORRECTION 2 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(-1.5, 4) -- (-1, 0) \
+(-1, 0) -- (0, 2.5) \
+(0, 2.5) -- (1, 0) \
+(1, 0) -- (2, 4) \
+END \
+ \
+SHAPE X MAXDIST 8 CORRECTION 2.8 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 4 \
+(-2, 4) -- (0, 0) \
+(0, 0) -- (2, 4) \
+(-2, -4) -- (0, 0) \
+(0, 0) -- (2, -4) \
+END \
+ \
+SHAPE Y MAXDIST 8 CORRECTION 4.4 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 2 \
+(2, 4) -- (0, 0) \
+(-0.8, 4) -- (0.8, 1.6) \
+END \
+ \
+SHAPE Z MAXDIST 8 CORRECTION 2.8 \
+SCALE DEVIATION 0.5 \
+ROTATION MIN -9 MAX 9 DENSITY 20 \
+START 3 \
+(0, 4) -- (3, 4) \
+(3, 4) -- (0, 0) \
+(0, 0) -- (3, 0) \
+END \
+";
+
+
+/* Cut shape to the given rectangle. */
+static interval* cut_shape (const interval* shape, const int size,
+			    point bottom_left, point top_right, int* res_size)
+{
+  int new_size = 0;
+  int i = 0;
+  for (i = 0; i < size; i++) {
+    if (shape[i].start.x > bottom_left.x && shape[i].start.y > bottom_left.y &&
+	shape[i].start.x < top_right.x && shape[i].start.y < top_right.y &&
+	shape[i].end.x > bottom_left.x && shape[i].end.y > bottom_left.y &&
+	shape[i].end.x < top_right.x && shape[i].end.y < top_right.y) {
+      new_size++;
+    }
+  }
+  
+  interval* new_shape = calloc (new_size, sizeof (interval));
+  int j = 0;
+  for (i = 0; i < size; i++) {
+    if (shape[i].start.x > bottom_left.x && shape[i].start.y > bottom_left.y &&
+	shape[i].start.x < top_right.x && shape[i].start.y < top_right.y &&
+	shape[i].end.x > bottom_left.x && shape[i].end.y > bottom_left.y &&
+	shape[i].end.x < top_right.x && shape[i].end.y < top_right.y) {
+      new_shape[j].start.x = shape[i].start.x;
+      new_shape[j].start.y = shape[i].start.y;
+      new_shape[j].end.x = shape[i].end.x;
+      new_shape[j].end.y = shape[i].end.y;
+      j++;
+    }
+  }
+
+  *res_size = new_size;
+  return (new_shape);
+}
+
+#define gridSIZE 3
+#define gridJUMP 1
+#define gridMARGIN 0.28
+int gridSIZES[gridSIZE][gridSIZE];
+interval * gridSHAPES[gridSIZE][gridSIZE];
+
+
+/* Run complete recognition from string, return resul...
 
[truncated message content]