/*
Class to recognize a single-stroke glyph from a library of glyphs. - Ken Perlin

Algorithm:

	Uniformly transform to fill middle of unit square.
	Reparameterize X coordinates by stroke length.
	Reparameterize Y coordinates by stroke length.
	Resample both X and Y into N samples (eg: N = 20).
	Do least squares comparison against library which is in same form.
	Choose candidate with lowest sum of X error and Y error.

	Speedup:
		Initially subsample with small N (eg: N = 8) to rapidly
		eliminate all but smallest K library candidates (eg: K = 8).

		Then final K candidates compete using larger N (eg: N = 32).
*/

import java.util.*;

public class Recognizer extends Vector
{
   int N = 10;
   double d[];

   public Recognizer() { this(10); }

   public Recognizer(int N) {
      this.N = N;
      d = new double[2*N];
   }

   public double[] add(int xy[], int n, Object obj) {
      double objData[] = new double[2*N];
      normalize(xy, n/2, objData);
      addElement(objData);
      addElement(obj);
      return objData;
   }

   public Object recognize(int xy[], int n) {
      normalize(xy, n/2, d);
      double errMin = 10000, err, t;
      int iMin = -1;
      for (int i = 0 ; i < size() ; i += 2) {
         err = 0;
	 double data[] = (double[])elementAt(i);
         for (int j = 0 ; j < d.length ; j++) {
	    t = d[j] - data[j];
            err += t * t;
         }
         if (err < errMin) {
            errMin = err;
	    iMin = i;
         }
      }
      return iMin == -1 ? null : elementAt(iMin+1);
   }

   public double[] getPattern(Object obj) {
      for (int i = 0 ; i < size() ; i += 2)
	 if ( ((String)obj).equals( (String)elementAt(i+1) ) )
	    return (double[])elementAt(i);
      return null;
   }

   public static void normalize(int xy[], int n, double data[]) {

      int N = data.length / 2;

      // COPY INPUT DATA AND COMPUTE LENGTH-BASED PARAMETER T

      double X[] = new double[n];
      double Y[] = new double[n];
      double T[] = new double[n];

      for (int i = 0 ; i < n ; i++) {
         X[i] = xy[2*i];
         Y[i] = xy[2*i+1];
	 if (i > 0) {
	    double dx = X[i] - X[i-1];
	    double dy = Y[i] - Y[i-1];
	    T[i] = T[i-1] + Math.sqrt(dx * dx + dy * dy);
         }
      }
      for (int i = 0 ; i < n ; i++)
         T[i] = T[i] / T[n-1];

      // NORMALIZE TO FIT INTO A UNIT SQUARE

      double xlo = 10000, xhi = -10000;
      double ylo = 10000, yhi = -10000;
      for (int i = 0 ; i < X.length ; i++) {
         xlo = Math.min(xlo, X[i]);
         xhi = Math.max(xhi, X[i]);
         ylo = Math.min(ylo, Y[i]);
         yhi = Math.max(yhi, Y[i]);
      }
      if (xhi - xlo > yhi - ylo)
         fitIntoSquare(X,Y, xlo, xhi, ylo, yhi); // WIDE STROKE: UNIT WIDTH
      else
         fitIntoSquare(Y,X, ylo, yhi, xlo, xhi); // TALL STROKE: UNIT HEIGHT
     
      // RESAMPLE X AND Y TO N SAMPLES

      for (int i = 0 ; i < N ; i++) {
         double t = (i-.001) / (N-1);
	 data[i  ] = sample(X, T, t);
	 data[i+N] = sample(Y, T, t);
      }
   }
   static void fitIntoSquare(double U[], double V[],
                             double ulo, double uhi, double vlo, double vhi) {
      double du = uhi - ulo;
      double dv = vhi - vlo;
      double v0 = .5 * (1 - dv / du);
      for (int i = 0 ; i < U.length ; i++) {
         U[i] = (U[i] - ulo) / du;
         V[i] = (V[i] - vlo) / du + v0;
      }
   }
   static double sample(double U[], double T[], double t) {
      for (int i = 1 ; i < U.length ; i++)
         if (T[i-1] <= t && T[i] > t)
	    return U[i-1] + (t - T[i-1]) / (T[i] - T[i-1]) * (U[i] - U[i-1]);
      return U[0];
   }
}