content: /*
   * Copyright (C) 2008-2009 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package android.gesture;
  
  import android.graphics.RectF;
  import android.util.Log;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.io.Closeable;
  import java.io.IOException;
  
  import static android.gesture.GestureConstants.*;
  
  /**
   * Utility functions for gesture processing & analysis, including methods for:
   * <ul> 
   * <li>feature extraction (e.g., samplers and those for calculating bounding
   * boxes and gesture path lengths);
   * <li>geometric transformation (e.g., translation, rotation and scaling);
   * <li>gesture similarity comparison (e.g., calculating Euclidean or Cosine
   * distances between two gestures).
   * </ul>
   */
  public final class GestureUtils {
    
      private static final float SCALING_THRESHOLD = 0.26f;
      private static final float NONUNIFORM_SCALE = (float) Math.sqrt(2);
      
      private GestureUtils() {
      }
  
      /**
       * Closes the specified stream.
       *
       * @param stream The stream to close.
       */
      static void closeStream(Closeable stream) {
          if (stream != null) {
              try {
                  stream.close();
              } catch (IOException e) {
                  Log.e(LOG_TAG, "Could not close stream", e);
              }
          }
      }
      
      /**
       * Samples the gesture spatially by rendering the gesture into a 2D 
       * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 
       * The scaling does not necessarily keep the aspect ratio of the gesture. 
       * 
       * @param gesture the gesture to be sampled
       * @param bitmapSize the size of the bitmap
       * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 
       *         as a 1D array. The float at index i represents the grayscale 
       *         value at pixel [i%bitmapSize, i/bitmapSize] 
       */
      public static float[] spatialSampling(Gesture gesture, int bitmapSize) {
          return spatialSampling(gesture, bitmapSize, false);
      }
  
      /**
       * Samples the gesture spatially by rendering the gesture into a 2D 
       * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 
       * 
       * @param gesture the gesture to be sampled
       * @param bitmapSize the size of the bitmap
       * @param keepAspectRatio if the scaling should keep the gesture's 
       *        aspect ratio
       * 
       * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 
       *         as a 1D array. The float at index i represents the grayscale 
       *         value at pixel [i%bitmapSize, i/bitmapSize] 
       */
      public static float[] spatialSampling(Gesture gesture, int bitmapSize, 
              boolean keepAspectRatio) {
          final float targetPatchSize = bitmapSize - 1; 
          float[] sample = new float[bitmapSize * bitmapSize];
          Arrays.fill(sample, 0);
    
          RectF rect = gesture.getBoundingBox();
          final float gestureWidth = rect.width();
          final float gestureHeight = rect.height();
          float sx = targetPatchSize / gestureWidth;
          float sy = targetPatchSize / gestureHeight;
          
          if (keepAspectRatio) {
              float scale = sx < sy ? sx : sy;
              sx = scale;
              sy = scale;
          } else {
  
              float aspectRatio = gestureWidth / gestureHeight;
              if (aspectRatio > 1) {
                  aspectRatio = 1 / aspectRatio;
              }
              if (aspectRatio < SCALING_THRESHOLD) {
                  float scale = sx < sy ? sx : sy;
                  sx = scale;
                  sy = scale;
              } else {
                  if (sx > sy) {
                      float scale = sy * NONUNIFORM_SCALE;
                      if (scale < sx) {
                          sx = scale;
                      }
                  } else {
                      float scale = sx * NONUNIFORM_SCALE; 
                      if (scale < sy) {
                          sy = scale;
                      }
                  }
              }
          }
          float preDx = -rect.centerX();
          float preDy = -rect.centerY();
          float postDx = targetPatchSize / 2;
          float postDy = targetPatchSize / 2;
          final ArrayList<GestureStroke> strokes = gesture.getStrokes();
          final int count = strokes.size();
          int size;
          float xpos;
          float ypos;
          for (int index = 0; index < count; index++) {
              final GestureStroke stroke = strokes.get(index);
              float[] strokepoints = stroke.points;
              size = strokepoints.length;
              final float[] pts = new float[size];
              for (int i = 0; i < size; i += 2) {
                  pts[i] = (strokepoints[i] + preDx) * sx + postDx;
                  pts[i + 1] = (strokepoints[i + 1] + preDy) * sy + postDy;
              }
              float segmentEndX = -1;
              float segmentEndY = -1;
              for (int i = 0; i < size; i += 2) {
                  float segmentStartX = pts[i] < 0 ? 0 : pts[i];
                  float segmentStartY = pts[i + 1] < 0 ? 0 : pts[i + 1];
                  if (segmentStartX > targetPatchSize) {
                      segmentStartX = targetPatchSize;
                  } 
                  if (segmentStartY > targetPatchSize) {
                      segmentStartY = targetPatchSize;
                  }
                  plot(segmentStartX, segmentStartY, sample, bitmapSize);
                  if (segmentEndX != -1) {
                      // Evaluate horizontally
                      if (segmentEndX > segmentStartX) {
                          xpos = (float) Math.ceil(segmentStartX);
                          float slope = (segmentEndY - segmentStartY) / 
                                        (segmentEndX - segmentStartX);
                          while (xpos < segmentEndX) {
                              ypos = slope * (xpos - segmentStartX) + segmentStartY;
                              plot(xpos, ypos, sample, bitmapSize); 
                              xpos++;
                          }
                      } else if (segmentEndX < segmentStartX){
                          xpos = (float) Math.ceil(segmentEndX);
                          float slope = (segmentEndY - segmentStartY) / 
                                        (segmentEndX - segmentStartX);
                          while (xpos < segmentStartX) {
                              ypos = slope * (xpos - segmentStartX) + segmentStartY;
                              plot(xpos, ypos, sample, bitmapSize); 
                              xpos++;
                          }
                      }
                      // Evaluate vertically
                      if (segmentEndY > segmentStartY) {
                          ypos = (float) Math.ceil(segmentStartY);
                          float invertSlope = (segmentEndX - segmentStartX) / 
                                              (segmentEndY - segmentStartY);
                          while (ypos < segmentEndY) {
                              xpos = invertSlope * (ypos - segmentStartY) + segmentStartX;
                              plot(xpos, ypos, sample, bitmapSize); 
                              ypos++;
                          }
                      } else if (segmentEndY < segmentStartY) {
                          ypos = (float) Math.ceil(segmentEndY);
                          float invertSlope = (segmentEndX - segmentStartX) / 
                                              (segmentEndY - segmentStartY);
                          while (ypos < segmentStartY) {
                              xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 
                              plot(xpos, ypos, sample, bitmapSize); 
                              ypos++;
                          }
                      }
                  } 
                  segmentEndX = segmentStartX;
                  segmentEndY = segmentStartY;
              }
          }
          return sample;
      }
    
      private static void plot(float x, float y, float[] sample, int sampleSize) {
          x = x < 0 ? 0 : x;
          y = y < 0 ? 0 : y;
          int xFloor = (int) Math.floor(x);
          int xCeiling = (int) Math.ceil(x);
          int yFloor = (int) Math.floor(y);
          int yCeiling = (int) Math.ceil(y);
          
          // if it's an integer
          if (x == xFloor && y == yFloor) {
              int index = yCeiling * sampleSize + xCeiling;
              if (sample[index] < 1){
                  sample[index] = 1;
              }
          } else {
              final double xFloorSq = Math.pow(xFloor - x, 2);
              final double yFloorSq = Math.pow(yFloor - y, 2);
              final double xCeilingSq = Math.pow(xCeiling - x, 2);
              final double yCeilingSq = Math.pow(yCeiling - y, 2);
              float topLeft = (float) Math.sqrt(xFloorSq + yFloorSq);
              float topRight = (float) Math.sqrt(xCeilingSq + yFloorSq);
              float btmLeft = (float) Math.sqrt(xFloorSq + yCeilingSq);
              float btmRight = (float) Math.sqrt(xCeilingSq + yCeilingSq);
              float sum = topLeft + topRight + btmLeft + btmRight;
              
              float value = topLeft / sum;
              int index = yFloor * sampleSize + xFloor;
              if (value > sample[index]){
                  sample[index] = value;
              }
              
              value = topRight / sum;
              index = yFloor * sampleSize + xCeiling;
              if (value > sample[index]){
                  sample[index] = value;
              }
              
              value = btmLeft / sum;
              index = yCeiling * sampleSize + xFloor;
              if (value > sample[index]){
                  sample[index] = value;
              }
              
              value = btmRight / sum;
              index = yCeiling * sampleSize + xCeiling;
              if (value > sample[index]){
                  sample[index] = value;
              }
          }
      }
  
      /**
       * Samples a stroke temporally into a given number of evenly-distributed 
       * points.
       * 
       * @param stroke the gesture stroke to be sampled
       * @param numPoints the number of points
       * @return the sampled points in the form of [x1, y1, x2, y2, ..., xn, yn]
       */
      public static float[] temporalSampling(GestureStroke stroke, int numPoints) {
          final float increment = stroke.length / (numPoints - 1);
          int vectorLength = numPoints * 2;
          float[] vector = new float[vectorLength];
          float distanceSoFar = 0;
          float[] pts = stroke.points;
          float lstPointX = pts[0];
          float lstPointY = pts[1];
          int index = 0;
          float currentPointX = Float.MIN_VALUE;
          float currentPointY = Float.MIN_VALUE;
          vector[index] = lstPointX;
          index++;
          vector[index] = lstPointY;
          index++;
          int i = 0;
          int count = pts.length / 2;
          while (i < count) {
              if (currentPointX == Float.MIN_VALUE) {
                  i++;
                  if (i >= count) {
                      break;
                  }
                  currentPointX = pts[i * 2];
                  currentPointY = pts[i * 2 + 1];
              }
              float deltaX = currentPointX - lstPointX;
              float deltaY = currentPointY - lstPointY;
              float distance = (float) Math.hypot(deltaX, deltaY);
              if (distanceSoFar + distance >= increment) {
                  float ratio = (increment - distanceSoFar) / distance;
                  float nx = lstPointX + ratio * deltaX;
                  float ny = lstPointY + ratio * deltaY;
                  vector[index] = nx;
                  index++;
                  vector[index] = ny;
                  index++;
                  lstPointX = nx;
                  lstPointY = ny;
                  distanceSoFar = 0;
              } else {
                  lstPointX = currentPointX;
                  lstPointY = currentPointY;
                  currentPointX = Float.MIN_VALUE;
                  currentPointY = Float.MIN_VALUE;
                  distanceSoFar += distance;
              }
          }
  
          for (i = index; i < vectorLength; i += 2) {
              vector[i] = lstPointX;
              vector[i + 1] = lstPointY;
          }
          return vector;
      }
  
      /**
       * Calculates the centroid of a set of points.
       * 
       * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn]
       * @return the centroid
       */
      static float[] computeCentroid(float[] points) {
          float centerX = 0;
          float centerY = 0;
          int count = points.length;
          for (int i = 0; i < count; i++) {
              centerX += points[i];
              i++;
              centerY += points[i];
          }
          float[] center = new float[2];
          center[0] = 2 * centerX / count;
          center[1] = 2 * centerY / count;
  
          return center;
      }
  
      /**
       * Calculates the variance-covariance matrix of a set of points.
       * 
       * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn]
       * @return the variance-covariance matrix
       */
      private static float[][] computeCoVariance(float[] points) {
          float[][] array = new float[2][2];
          array[0][0] = 0;
          array[0][1] = 0;
          array[1][0] = 0;
          array[1][1] = 0;
          int count = points.length;
          for (int i = 0; i < count; i++) {
              float x = points[i];
              i++;
              float y = points[i];
              array[0][0] += x * x;
              array[0][1] += x * y;
              array[1][0] = array[0][1];
              array[1][1] += y * y;
          }
          array[0][0] /= (count / 2);
          array[0][1] /= (count / 2);
          array[1][0] /= (count / 2);
          array[1][1] /= (count / 2);
  
          return array;
      }
  
      static float computeTotalLength(float[] points) {
          float sum = 0;
          int count = points.length - 4;
          for (int i = 0; i < count; i += 2) {
              float dx = points[i + 2] - points[i];
              float dy = points[i + 3] - points[i + 1];
              sum += Math.hypot(dx, dy);
          }
          return sum;
      }
  
      static float computeStraightness(float[] points) {
          float totalLen = computeTotalLength(points);
          float dx = points[2] - points[0];
          float dy = points[3] - points[1];
          return (float) Math.hypot(dx, dy) / totalLen;
      }
  
      static float computeStraightness(float[] points, float totalLen) {
          float dx = points[2] - points[0];
          float dy = points[3] - points[1];
          return (float) Math.hypot(dx, dy) / totalLen;
      }
  
      /**
       * Calculates the squared Euclidean distance between two vectors.
       * 
       * @param vector1
       * @param vector2
       * @return the distance
       */
      static float squaredEuclideanDistance(float[] vector1, float[] vector2) {
          float squaredDistance = 0;
          int size = vector1.length;
          for (int i = 0; i < size; i++) {
              float difference = vector1[i] - vector2[i];
              squaredDistance += difference * difference;
          }
          return squaredDistance / size;
      }
  
      /**
       * Calculates the cosine distance between two instances.
       * 
       * @param vector1
       * @param vector2
       * @return the distance between 0 and Math.PI
       */
      static float cosineDistance(float[] vector1, float[] vector2) {
          float sum = 0;
          int len = vector1.length;
          for (int i = 0; i < len; i++) {
              sum += vector1[i] * vector2[i];
          }
          return (float) Math.acos(sum);
      }
      
      /**
       * Calculates the "minimum" cosine distance between two instances.
       * 
       * @param vector1
       * @param vector2
       * @param numOrientations the maximum number of orientation allowed
       * @return the distance between the two instances (between 0 and Math.PI)
       */
      static float minimumCosineDistance(float[] vector1, float[] vector2, int numOrientations) {
          final int len = vector1.length;
          float a = 0;
          float b = 0;
          for (int i = 0; i < len; i += 2) {
              a += vector1[i] * vector2[i] + vector1[i + 1] * vector2[i + 1];
              b += vector1[i] * vector2[i + 1] - vector1[i + 1] * vector2[i];
          }
          if (a != 0) {
              final float tan = b/a;
              final double angle = Math.atan(tan);
              if (numOrientations > 2 && Math.abs(angle) >= Math.PI / numOrientations) {
                  return (float) Math.acos(a);
              } else {
                  final double cosine = Math.cos(angle);
                  final double sine = cosine * tan; 
                  return (float) Math.acos(a * cosine + b * sine);
              }
          } else {
              return (float) Math.PI / 2;
          }
      }
  
      /**
       * Computes an oriented, minimum bounding box of a set of points.
       * 
       * @param originalPoints
       * @return an oriented bounding box
       */
      public static OrientedBoundingBox computeOrientedBoundingBox(ArrayList<GesturePoint> originalPoints) {
          final int count = originalPoints.size();
          float[] points = new float[count * 2];
          for (int i = 0; i < count; i++) {
              GesturePoint point = originalPoints.get(i);
              int index = i * 2;
              points[index] = point.x;
              points[index + 1] = point.y;
          }
          float[] meanVector = computeCentroid(points);
          return computeOrientedBoundingBox(points, meanVector);
      }
  
      /**
       * Computes an oriented, minimum bounding box of a set of points.
       * 
       * @param originalPoints
       * @return an oriented bounding box
       */
      public static OrientedBoundingBox computeOrientedBoundingBox(float[] originalPoints) {
          int size = originalPoints.length;
          float[] points = new float[size];
          for (int i = 0; i < size; i++) {
              points[i] = originalPoints[i];
          }
          float[] meanVector = computeCentroid(points);
          return computeOrientedBoundingBox(points, meanVector);
      }
  
      private static OrientedBoundingBox computeOrientedBoundingBox(float[] points, float[] centroid) {
          translate(points, -centroid[0], -centroid[1]);
  
          float[][] array = computeCoVariance(points);
          float[] targetVector = computeOrientation(array);
  
          float angle;
          if (targetVector[0] == 0 && targetVector[1] == 0) {
              angle = (float) -Math.PI/2;
          } else { // -PI<alpha<PI
              angle = (float) Math.atan2(targetVector[1], targetVector[0]);
              rotate(points, -angle);
          }
  
          float minx = Float.MAX_VALUE;
          float miny = Float.MAX_VALUE;
          float maxx = Float.MIN_VALUE;
          float maxy = Float.MIN_VALUE;
          int count = points.length;
          for (int i = 0; i < count; i++) {
              if (points[i] < minx) {
                  minx = points[i];
              }
              if (points[i] > maxx) {
                  maxx = points[i];
              }
              i++;
              if (points[i] < miny) {
                  miny = points[i];
              }
              if (points[i] > maxy) {
                  maxy = points[i];
              }
          }
  
          return new OrientedBoundingBox((float) (angle * 180 / Math.PI), centroid[0], centroid[1], maxx - minx, maxy - miny);
      }
  
      private static float[] computeOrientation(float[][] covarianceMatrix) {
          float[] targetVector = new float[2];
          if (covarianceMatrix[0][1] == 0 || covarianceMatrix[1][0] == 0) {
              targetVector[0] = 1;
              targetVector[1] = 0;
          }
  
          float a = -covarianceMatrix[0][0] - covarianceMatrix[1][1];
          float b = covarianceMatrix[0][0] * covarianceMatrix[1][1] - covarianceMatrix[0][1]
                  * covarianceMatrix[1][0];
          float value = a / 2;
          float rightside = (float) Math.sqrt(Math.pow(value, 2) - b);
          float lambda1 = -value + rightside;
          float lambda2 = -value - rightside;
          if (lambda1 == lambda2) {
              targetVector[0] = 0;
              targetVector[1] = 0;
          } else {
              float lambda = lambda1 > lambda2 ? lambda1 : lambda2;
              targetVector[0] = 1;
              targetVector[1] = (lambda - covarianceMatrix[0][0]) / covarianceMatrix[0][1];
          }
          return targetVector;
      }
      
      
      static float[] rotate(float[] points, float angle) {
          float cos = (float) Math.cos(angle);
          float sin = (float) Math.sin(angle);
          int size = points.length;
          for (int i = 0; i < size; i += 2) {
              float x = points[i] * cos - points[i + 1] * sin;
              float y = points[i] * sin + points[i + 1] * cos;
              points[i] = x;
              points[i + 1] = y;
          }
          return points;
      }
      
      static float[] translate(float[] points, float dx, float dy) {
          int size = points.length;
          for (int i = 0; i < size; i += 2) {
              points[i] += dx;
              points[i + 1] += dy;
          }
          return points;
      }
      
      static float[] scale(float[] points, float sx, float sy) {
          int size = points.length;
          for (int i = 0; i < size; i += 2) {
              points[i] *= sx;
              points[i + 1] *= sy;
          }
          return points;
      }
  }
  