135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li/* 235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Copyright (C) 2008-2009 The Android Open Source Project 335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Licensed under the Apache License, Version 2.0 (the "License"); 535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * you may not use this file except in compliance with the License. 635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * You may obtain a copy of the License at 735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * http://www.apache.org/licenses/LICENSE-2.0 935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 1035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Unless required by applicable law or agreed to in writing, software 1135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * distributed under the License is distributed on an "AS IS" BASIS, 1235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * See the License for the specific language governing permissions and 1435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * limitations under the License. 1535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 1635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 17db567c390bd56c05614eaa83c02dbb99f97ad9ccRomain Guypackage android.gesture; 1835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 1935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport android.graphics.RectF; 20b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guyimport android.util.Log; 2135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 2235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.ArrayList; 2335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.Arrays; 24c534727972c3835ed997e84a349f259915ef2cddRomain Guyimport java.io.Closeable; 25c534727972c3835ed997e84a349f259915ef2cddRomain Guyimport java.io.IOException; 2635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 27db567c390bd56c05614eaa83c02dbb99f97ad9ccRomain Guyimport static android.gesture.GestureConstants.*; 2835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 29a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li/** 30a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * Utility functions for gesture processing & analysis, including methods for: 31a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * <ul> 32a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * <li>feature extraction (e.g., samplers and those for calculating bounding 33a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * boxes and gesture path lengths); 34a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * <li>geometric transformation (e.g., translation, rotation and scaling); 35a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * <li>gesture similarity comparison (e.g., calculating Euclidean or Cosine 36a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * distances between two gestures). 37a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li * </ul> 38a54bec599a4d49c8586a65a2f570e434cbbf08a2Yang Li */ 3946c53129c6f27c9193ab195a69cb50591b8c1fa2Romain Guypublic final class GestureUtils { 4055732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li 4155732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li private static final float SCALING_THRESHOLD = 0.26f; 4255732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li private static final float NONUNIFORM_SCALE = (float) Math.sqrt(2); 4355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li 4446c53129c6f27c9193ab195a69cb50591b8c1fa2Romain Guy private GestureUtils() { 45c534727972c3835ed997e84a349f259915ef2cddRomain Guy } 46c534727972c3835ed997e84a349f259915ef2cddRomain Guy 47c534727972c3835ed997e84a349f259915ef2cddRomain Guy /** 48c534727972c3835ed997e84a349f259915ef2cddRomain Guy * Closes the specified stream. 49c534727972c3835ed997e84a349f259915ef2cddRomain Guy * 50c534727972c3835ed997e84a349f259915ef2cddRomain Guy * @param stream The stream to close. 51c534727972c3835ed997e84a349f259915ef2cddRomain Guy */ 52c534727972c3835ed997e84a349f259915ef2cddRomain Guy static void closeStream(Closeable stream) { 53c534727972c3835ed997e84a349f259915ef2cddRomain Guy if (stream != null) { 54c534727972c3835ed997e84a349f259915ef2cddRomain Guy try { 55c534727972c3835ed997e84a349f259915ef2cddRomain Guy stream.close(); 56c534727972c3835ed997e84a349f259915ef2cddRomain Guy } catch (IOException e) { 57b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guy Log.e(LOG_TAG, "Could not close stream", e); 58c534727972c3835ed997e84a349f259915ef2cddRomain Guy } 59c534727972c3835ed997e84a349f259915ef2cddRomain Guy } 60c534727972c3835ed997e84a349f259915ef2cddRomain Guy } 61ec837187dfdc69a94d8b1bdffc54a0d1eed80ec2Yang Li 62c7f930f5a9a62470775e913945c771ca57e0b10fYang Li /** 63c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Samples the gesture spatially by rendering the gesture into a 2D 64c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 65c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * The scaling does not necessarily keep the aspect ratio of the gesture. 66c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * 67c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param gesture the gesture to be sampled 68c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param bitmapSize the size of the bitmap 69c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 70c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * as a 1D array. The float at index i represents the grayscale 71c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * value at pixel [i%bitmapSize, i/bitmapSize] 72c7f930f5a9a62470775e913945c771ca57e0b10fYang Li */ 73c7f930f5a9a62470775e913945c771ca57e0b10fYang Li public static float[] spatialSampling(Gesture gesture, int bitmapSize) { 74c7f930f5a9a62470775e913945c771ca57e0b10fYang Li return spatialSampling(gesture, bitmapSize, false); 75ec837187dfdc69a94d8b1bdffc54a0d1eed80ec2Yang Li } 76c534727972c3835ed997e84a349f259915ef2cddRomain Guy 77c7f930f5a9a62470775e913945c771ca57e0b10fYang Li /** 78c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Samples the gesture spatially by rendering the gesture into a 2D 79c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 80c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * 81c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param gesture the gesture to be sampled 82c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param bitmapSize the size of the bitmap 83c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param keepAspectRatio if the scaling should keep the gesture's 84c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * aspect ratio 85c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * 86c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 87c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * as a 1D array. The float at index i represents the grayscale 88c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * value at pixel [i%bitmapSize, i/bitmapSize] 89c7f930f5a9a62470775e913945c771ca57e0b10fYang Li */ 90c7f930f5a9a62470775e913945c771ca57e0b10fYang Li public static float[] spatialSampling(Gesture gesture, int bitmapSize, 91c7f930f5a9a62470775e913945c771ca57e0b10fYang Li boolean keepAspectRatio) { 92c7f930f5a9a62470775e913945c771ca57e0b10fYang Li final float targetPatchSize = bitmapSize - 1; 93c7f930f5a9a62470775e913945c771ca57e0b10fYang Li float[] sample = new float[bitmapSize * bitmapSize]; 9435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li Arrays.fill(sample, 0); 955c79dee64f29bb7c2bde5bd44116baca7307751cYang Li 9635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li RectF rect = gesture.getBoundingBox(); 9755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final float gestureWidth = rect.width(); 9855732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final float gestureHeight = rect.height(); 9955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float sx = targetPatchSize / gestureWidth; 10055732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float sy = targetPatchSize / gestureHeight; 10155732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li 102c7f930f5a9a62470775e913945c771ca57e0b10fYang Li if (keepAspectRatio) { 10355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float scale = sx < sy ? sx : sy; 10455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sx = scale; 10555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sy = scale; 10655732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } else { 10755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li 10855732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float aspectRatio = gestureWidth / gestureHeight; 10955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li if (aspectRatio > 1) { 11055732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li aspectRatio = 1 / aspectRatio; 11155732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 11255732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li if (aspectRatio < SCALING_THRESHOLD) { 11355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float scale = sx < sy ? sx : sy; 11455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sx = scale; 11555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sy = scale; 11655732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } else { 11755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li if (sx > sy) { 11855732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float scale = sy * NONUNIFORM_SCALE; 11955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li if (scale < sx) { 12055732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sx = scale; 12155732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 12255732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } else { 12355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float scale = sx * NONUNIFORM_SCALE; 12455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li if (scale < sy) { 12555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sy = scale; 12655732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 12755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 12855732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 12955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li } 130b082ceefdc877bda2159a8d66d854576e0511d15Yang Li float preDx = -rect.centerX(); 131b082ceefdc877bda2159a8d66d854576e0511d15Yang Li float preDy = -rect.centerY(); 132b082ceefdc877bda2159a8d66d854576e0511d15Yang Li float postDx = targetPatchSize / 2; 133b082ceefdc877bda2159a8d66d854576e0511d15Yang Li float postDy = targetPatchSize / 2; 134b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guy final ArrayList<GestureStroke> strokes = gesture.getStrokes(); 135b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guy final int count = strokes.size(); 13635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int size; 13735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float xpos; 13835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float ypos; 13935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int index = 0; index < count; index++) { 140b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guy final GestureStroke stroke = strokes.get(index); 141b082ceefdc877bda2159a8d66d854576e0511d15Yang Li float[] strokepoints = stroke.points; 142b082ceefdc877bda2159a8d66d854576e0511d15Yang Li size = strokepoints.length; 143b6d99b7d17fd1bb1326a70744bd01be5d1586487Romain Guy final float[] pts = new float[size]; 144b082ceefdc877bda2159a8d66d854576e0511d15Yang Li for (int i = 0; i < size; i += 2) { 14555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li pts[i] = (strokepoints[i] + preDx) * sx + postDx; 14655732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li pts[i + 1] = (strokepoints[i + 1] + preDy) * sy + postDy; 147b082ceefdc877bda2159a8d66d854576e0511d15Yang Li } 14835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float segmentEndX = -1; 14935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float segmentEndY = -1; 15035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < size; i += 2) { 15135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float segmentStartX = pts[i] < 0 ? 0 : pts[i]; 15235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float segmentStartY = pts[i + 1] < 0 ? 0 : pts[i + 1]; 15335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (segmentStartX > targetPatchSize) { 15435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li segmentStartX = targetPatchSize; 15535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 15635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (segmentStartY > targetPatchSize) { 15735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li segmentStartY = targetPatchSize; 15835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 159c7f930f5a9a62470775e913945c771ca57e0b10fYang Li plot(segmentStartX, segmentStartY, sample, bitmapSize); 16035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (segmentEndX != -1) { 161c7f930f5a9a62470775e913945c771ca57e0b10fYang Li // Evaluate horizontally 16235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (segmentEndX > segmentStartX) { 16335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos = (float) Math.ceil(segmentStartX); 16455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float slope = (segmentEndY - segmentStartY) / 16555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li (segmentEndX - segmentStartX); 16635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li while (xpos < segmentEndX) { 16735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos = slope * (xpos - segmentStartX) + segmentStartY; 168c7f930f5a9a62470775e913945c771ca57e0b10fYang Li plot(xpos, ypos, sample, bitmapSize); 16935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos++; 17035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 17135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else if (segmentEndX < segmentStartX){ 17235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos = (float) Math.ceil(segmentEndX); 17355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float slope = (segmentEndY - segmentStartY) / 17455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li (segmentEndX - segmentStartX); 17535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li while (xpos < segmentStartX) { 17635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos = slope * (xpos - segmentStartX) + segmentStartY; 177c7f930f5a9a62470775e913945c771ca57e0b10fYang Li plot(xpos, ypos, sample, bitmapSize); 17835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos++; 17935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 18035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 181c7f930f5a9a62470775e913945c771ca57e0b10fYang Li // Evaluate vertically 18235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (segmentEndY > segmentStartY) { 18335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos = (float) Math.ceil(segmentStartY); 18455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float invertSlope = (segmentEndX - segmentStartX) / 18555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li (segmentEndY - segmentStartY); 18635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li while (ypos < segmentEndY) { 18735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 188c7f930f5a9a62470775e913945c771ca57e0b10fYang Li plot(xpos, ypos, sample, bitmapSize); 18935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos++; 19035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 19135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else if (segmentEndY < segmentStartY) { 19235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos = (float) Math.ceil(segmentEndY); 19355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float invertSlope = (segmentEndX - segmentStartX) / 19455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li (segmentEndY - segmentStartY); 19535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li while (ypos < segmentStartY) { 19635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 197c7f930f5a9a62470775e913945c771ca57e0b10fYang Li plot(xpos, ypos, sample, bitmapSize); 19835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ypos++; 19935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 20035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 20135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 20235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li segmentEndX = segmentStartX; 20335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li segmentEndY = segmentStartY; 20435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 20535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 20635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return sample; 20735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 2085c79dee64f29bb7c2bde5bd44116baca7307751cYang Li 20935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li private static void plot(float x, float y, float[] sample, int sampleSize) { 21035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li x = x < 0 ? 0 : x; 21135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li y = y < 0 ? 0 : y; 21235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int xFloor = (int) Math.floor(x); 21335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int xCeiling = (int) Math.ceil(x); 21435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int yFloor = (int) Math.floor(y); 21535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int yCeiling = (int) Math.ceil(y); 21635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 21735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li // if it's an integer 21835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (x == xFloor && y == yFloor) { 21935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int index = yCeiling * sampleSize + xCeiling; 22035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (sample[index] < 1){ 22135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li sample[index] = 1; 22235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 22335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { 22455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final double xFloorSq = Math.pow(xFloor - x, 2); 22555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final double yFloorSq = Math.pow(yFloor - y, 2); 22655732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final double xCeilingSq = Math.pow(xCeiling - x, 2); 22755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li final double yCeilingSq = Math.pow(yCeiling - y, 2); 22855732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float topLeft = (float) Math.sqrt(xFloorSq + yFloorSq); 22955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float topRight = (float) Math.sqrt(xCeilingSq + yFloorSq); 23055732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float btmLeft = (float) Math.sqrt(xFloorSq + yCeilingSq); 23155732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float btmRight = (float) Math.sqrt(xCeilingSq + yCeilingSq); 23255732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float sum = topLeft + topRight + btmLeft + btmRight; 23335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 23455732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li float value = topLeft / sum; 23535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int index = yFloor * sampleSize + xFloor; 23635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (value > sample[index]){ 23755732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sample[index] = value; 23835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 23935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 24035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li value = topRight / sum; 24135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index = yFloor * sampleSize + xCeiling; 24235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (value > sample[index]){ 24355732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sample[index] = value; 24435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 24535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 24635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li value = btmLeft / sum; 24735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index = yCeiling * sampleSize + xFloor; 24835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (value > sample[index]){ 24955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sample[index] = value; 25035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 25135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 25235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li value = btmRight / sum; 25335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index = yCeiling * sampleSize + xCeiling; 25435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (value > sample[index]){ 25555732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li sample[index] = value; 25635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 25735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 25835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 25955732c52ee2bcfe5a59a1395688aeb7576713ac4Yang Li 26035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li /** 261c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Samples a stroke temporally into a given number of evenly-distributed 262c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * points. 26335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 264c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param stroke the gesture stroke to be sampled 265c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param numPoints the number of points 266c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return the sampled points in the form of [x1, y1, x2, y2, ..., xn, yn] 26735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 268c7f930f5a9a62470775e913945c771ca57e0b10fYang Li public static float[] temporalSampling(GestureStroke stroke, int numPoints) { 269c7f930f5a9a62470775e913945c771ca57e0b10fYang Li final float increment = stroke.length / (numPoints - 1); 270c7f930f5a9a62470775e913945c771ca57e0b10fYang Li int vectorLength = numPoints * 2; 27135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float[] vector = new float[vectorLength]; 27235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float distanceSoFar = 0; 27335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float[] pts = stroke.points; 27435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float lstPointX = pts[0]; 27535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float lstPointY = pts[1]; 27635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int index = 0; 27735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float currentPointX = Float.MIN_VALUE; 27835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float currentPointY = Float.MIN_VALUE; 27935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[index] = lstPointX; 28035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index++; 28135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[index] = lstPointY; 28235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index++; 28335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int i = 0; 28435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = pts.length / 2; 28535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li while (i < count) { 28635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (currentPointX == Float.MIN_VALUE) { 28735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li i++; 28835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (i >= count) { 28935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li break; 29035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 29135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li currentPointX = pts[i * 2]; 29235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li currentPointY = pts[i * 2 + 1]; 29335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 29435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float deltaX = currentPointX - lstPointX; 29535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float deltaY = currentPointY - lstPointY; 29633253a4baa6279f81a73425b49dfb6abe5f5416eNeil Fuller float distance = (float) Math.hypot(deltaX, deltaY); 29735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (distanceSoFar + distance >= increment) { 29835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float ratio = (increment - distanceSoFar) / distance; 29935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float nx = lstPointX + ratio * deltaX; 30035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float ny = lstPointY + ratio * deltaY; 30135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[index] = nx; 30235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index++; 30335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[index] = ny; 30435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li index++; 30535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li lstPointX = nx; 30635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li lstPointY = ny; 30735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li distanceSoFar = 0; 30835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { 30935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li lstPointX = currentPointX; 31035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li lstPointY = currentPointY; 31135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li currentPointX = Float.MIN_VALUE; 31235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li currentPointY = Float.MIN_VALUE; 31335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li distanceSoFar += distance; 31435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 31535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 31635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 31735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (i = index; i < vectorLength; i += 2) { 31835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[i] = lstPointX; 31935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li vector[i + 1] = lstPointY; 32035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 32135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return vector; 32235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 32335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 32435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li /** 325c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Calculates the centroid of a set of points. 32635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 327c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn] 32835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * @return the centroid 32935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 330c534727972c3835ed997e84a349f259915ef2cddRomain Guy static float[] computeCentroid(float[] points) { 33135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float centerX = 0; 33235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float centerY = 0; 33335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = points.length; 33435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < count; i++) { 33535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li centerX += points[i]; 33635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li i++; 33735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li centerY += points[i]; 33835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 33935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float[] center = new float[2]; 34035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li center[0] = 2 * centerX / count; 34135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li center[1] = 2 * centerY / count; 34235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 34335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return center; 34435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 34535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 34635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li /** 347c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Calculates the variance-covariance matrix of a set of points. 34835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 349c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn] 350c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return the variance-covariance matrix 35135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 3525c79dee64f29bb7c2bde5bd44116baca7307751cYang Li private static float[][] computeCoVariance(float[] points) { 3535c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[][] array = new float[2][2]; 35435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][0] = 0; 35535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][1] = 0; 35635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][0] = 0; 35735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][1] = 0; 35835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = points.length; 35935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < count; i++) { 36035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float x = points[i]; 36135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li i++; 36235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float y = points[i]; 36335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][0] += x * x; 36435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][1] += x * y; 36535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][0] = array[0][1]; 36635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][1] += y * y; 36735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 36835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][0] /= (count / 2); 36935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[0][1] /= (count / 2); 37035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][0] /= (count / 2); 37135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li array[1][1] /= (count / 2); 37235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 37335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return array; 37435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 37535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 376c534727972c3835ed997e84a349f259915ef2cddRomain Guy static float computeTotalLength(float[] points) { 37735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float sum = 0; 37835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = points.length - 4; 37935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < count; i += 2) { 38035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dx = points[i + 2] - points[i]; 38135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dy = points[i + 3] - points[i + 1]; 38233253a4baa6279f81a73425b49dfb6abe5f5416eNeil Fuller sum += Math.hypot(dx, dy); 38335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 38435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return sum; 38535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 38635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 3875c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float computeStraightness(float[] points) { 38835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float totalLen = computeTotalLength(points); 38935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dx = points[2] - points[0]; 39035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dy = points[3] - points[1]; 39133253a4baa6279f81a73425b49dfb6abe5f5416eNeil Fuller return (float) Math.hypot(dx, dy) / totalLen; 39235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 39335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 3945c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float computeStraightness(float[] points, float totalLen) { 39535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dx = points[2] - points[0]; 39635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float dy = points[3] - points[1]; 39733253a4baa6279f81a73425b49dfb6abe5f5416eNeil Fuller return (float) Math.hypot(dx, dy) / totalLen; 39835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 39935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 40035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li /** 401c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Calculates the squared Euclidean distance between two vectors. 40235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 40335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * @param vector1 40435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * @param vector2 40535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * @return the distance 40635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 4075c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float squaredEuclideanDistance(float[] vector1, float[] vector2) { 4085c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float squaredDistance = 0; 40935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int size = vector1.length; 41035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < size; i++) { 41135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float difference = vector1[i] - vector2[i]; 41235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li squaredDistance += difference * difference; 41335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 41435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return squaredDistance / size; 41535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 41635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 41735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li /** 418c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Calculates the cosine distance between two instances. 41935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 420e6ea003ab66ea8bd91bed8aaf5c3b4cd75555886Yang Li * @param vector1 421e6ea003ab66ea8bd91bed8aaf5c3b4cd75555886Yang Li * @param vector2 42235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * @return the distance between 0 and Math.PI 42335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 4245c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float cosineDistance(float[] vector1, float[] vector2) { 42535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float sum = 0; 42635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int len = vector1.length; 42735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < len; i++) { 42835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li sum += vector1[i] * vector2[i]; 42935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 4305c79dee64f29bb7c2bde5bd44116baca7307751cYang Li return (float) Math.acos(sum); 43135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 4324758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li 4334758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li /** 434c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Calculates the "minimum" cosine distance between two instances. 4354758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li * 4364758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li * @param vector1 4374758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li * @param vector2 4384758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li * @param numOrientations the maximum number of orientation allowed 4394758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li * @return the distance between the two instances (between 0 and Math.PI) 4404758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li */ 4415c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float minimumCosineDistance(float[] vector1, float[] vector2, int numOrientations) { 4424758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li final int len = vector1.length; 4435c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float a = 0; 4445c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float b = 0; 4454758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li for (int i = 0; i < len; i += 2) { 4464758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li a += vector1[i] * vector2[i] + vector1[i + 1] * vector2[i + 1]; 4474758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li b += vector1[i] * vector2[i + 1] - vector1[i + 1] * vector2[i]; 4484758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } 4494758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li if (a != 0) { 4505c79dee64f29bb7c2bde5bd44116baca7307751cYang Li final float tan = b/a; 4514758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li final double angle = Math.atan(tan); 4524758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li if (numOrientations > 2 && Math.abs(angle) >= Math.PI / numOrientations) { 4535c79dee64f29bb7c2bde5bd44116baca7307751cYang Li return (float) Math.acos(a); 4544758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } else { 4554758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li final double cosine = Math.cos(angle); 4564758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li final double sine = cosine * tan; 4575c79dee64f29bb7c2bde5bd44116baca7307751cYang Li return (float) Math.acos(a * cosine + b * sine); 4584758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } 4594758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } else { 4605c79dee64f29bb7c2bde5bd44116baca7307751cYang Li return (float) Math.PI / 2; 4614758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } 4624758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li } 4634758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li 464c7f930f5a9a62470775e913945c771ca57e0b10fYang Li /** 465c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Computes an oriented, minimum bounding box of a set of points. 466c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * 467c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param originalPoints 468c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return an oriented bounding box 469c7f930f5a9a62470775e913945c771ca57e0b10fYang Li */ 470c7f930f5a9a62470775e913945c771ca57e0b10fYang Li public static OrientedBoundingBox computeOrientedBoundingBox(ArrayList<GesturePoint> originalPoints) { 4715c79dee64f29bb7c2bde5bd44116baca7307751cYang Li final int count = originalPoints.size(); 4725c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[] points = new float[count * 2]; 4735c79dee64f29bb7c2bde5bd44116baca7307751cYang Li for (int i = 0; i < count; i++) { 4745c79dee64f29bb7c2bde5bd44116baca7307751cYang Li GesturePoint point = originalPoints.get(i); 4755c79dee64f29bb7c2bde5bd44116baca7307751cYang Li int index = i * 2; 4765c79dee64f29bb7c2bde5bd44116baca7307751cYang Li points[index] = point.x; 4775c79dee64f29bb7c2bde5bd44116baca7307751cYang Li points[index + 1] = point.y; 4785c79dee64f29bb7c2bde5bd44116baca7307751cYang Li } 4795c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[] meanVector = computeCentroid(points); 4805c79dee64f29bb7c2bde5bd44116baca7307751cYang Li return computeOrientedBoundingBox(points, meanVector); 48135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 48235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 483c7f930f5a9a62470775e913945c771ca57e0b10fYang Li /** 484c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * Computes an oriented, minimum bounding box of a set of points. 485c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * 486c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @param originalPoints 487c7f930f5a9a62470775e913945c771ca57e0b10fYang Li * @return an oriented bounding box 488c7f930f5a9a62470775e913945c771ca57e0b10fYang Li */ 489c7f930f5a9a62470775e913945c771ca57e0b10fYang Li public static OrientedBoundingBox computeOrientedBoundingBox(float[] originalPoints) { 4905c79dee64f29bb7c2bde5bd44116baca7307751cYang Li int size = originalPoints.length; 4915c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[] points = new float[size]; 4925c79dee64f29bb7c2bde5bd44116baca7307751cYang Li for (int i = 0; i < size; i++) { 4935c79dee64f29bb7c2bde5bd44116baca7307751cYang Li points[i] = originalPoints[i]; 4945c79dee64f29bb7c2bde5bd44116baca7307751cYang Li } 49535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float[] meanVector = computeCentroid(points); 496c534727972c3835ed997e84a349f259915ef2cddRomain Guy return computeOrientedBoundingBox(points, meanVector); 49735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 49835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 4995c79dee64f29bb7c2bde5bd44116baca7307751cYang Li private static OrientedBoundingBox computeOrientedBoundingBox(float[] points, float[] centroid) { 50058b359041a29418876f12d37a7082ece9f8a38a4Yang Li translate(points, -centroid[0], -centroid[1]); 50135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 5025c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[][] array = computeCoVariance(points); 5035c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[] targetVector = computeOrientation(array); 50435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 50535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float angle; 50635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (targetVector[0] == 0 && targetVector[1] == 0) { 50758b359041a29418876f12d37a7082ece9f8a38a4Yang Li angle = (float) -Math.PI/2; 50835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { // -PI<alpha<PI 50935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li angle = (float) Math.atan2(targetVector[1], targetVector[0]); 51058b359041a29418876f12d37a7082ece9f8a38a4Yang Li rotate(points, -angle); 51135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 51235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 51335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float minx = Float.MAX_VALUE; 51435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float miny = Float.MAX_VALUE; 51535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float maxx = Float.MIN_VALUE; 51635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li float maxy = Float.MIN_VALUE; 51735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = points.length; 51835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < count; i++) { 51935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (points[i] < minx) { 52035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li minx = points[i]; 52135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 52235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (points[i] > maxx) { 52335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li maxx = points[i]; 52435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 52535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li i++; 52635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (points[i] < miny) { 52735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li miny = points[i]; 52835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 52935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (points[i] > maxy) { 53035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li maxy = points[i]; 53135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 53235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 53335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 534f3ede869b8abef8d85e204bc259ee0cf8dc8d2aeYang Li return new OrientedBoundingBox((float) (angle * 180 / Math.PI), centroid[0], centroid[1], maxx - minx, maxy - miny); 53535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 53635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 5375c79dee64f29bb7c2bde5bd44116baca7307751cYang Li private static float[] computeOrientation(float[][] covarianceMatrix) { 5385c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float[] targetVector = new float[2]; 53935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (covarianceMatrix[0][1] == 0 || covarianceMatrix[1][0] == 0) { 54035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[0] = 1; 54135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[1] = 0; 54235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 54335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 5445c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float a = -covarianceMatrix[0][0] - covarianceMatrix[1][1]; 5455c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float b = covarianceMatrix[0][0] * covarianceMatrix[1][1] - covarianceMatrix[0][1] 54635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * covarianceMatrix[1][0]; 5475c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float value = a / 2; 5485c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float rightside = (float) Math.sqrt(Math.pow(value, 2) - b); 5495c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float lambda1 = -value + rightside; 5505c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float lambda2 = -value - rightside; 55135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (lambda1 == lambda2) { 55235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[0] = 0; 55335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[1] = 0; 55435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { 5555c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float lambda = lambda1 > lambda2 ? lambda1 : lambda2; 55635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[0] = 1; 55735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li targetVector[1] = (lambda - covarianceMatrix[0][0]) / covarianceMatrix[0][1]; 55835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 55935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return targetVector; 56035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 56158b359041a29418876f12d37a7082ece9f8a38a4Yang Li 56258b359041a29418876f12d37a7082ece9f8a38a4Yang Li 5635c79dee64f29bb7c2bde5bd44116baca7307751cYang Li static float[] rotate(float[] points, float angle) { 5645c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float cos = (float) Math.cos(angle); 5655c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float sin = (float) Math.sin(angle); 56658b359041a29418876f12d37a7082ece9f8a38a4Yang Li int size = points.length; 56758b359041a29418876f12d37a7082ece9f8a38a4Yang Li for (int i = 0; i < size; i += 2) { 5685c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float x = points[i] * cos - points[i + 1] * sin; 5695c79dee64f29bb7c2bde5bd44116baca7307751cYang Li float y = points[i] * sin + points[i + 1] * cos; 57058b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i] = x; 57158b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i + 1] = y; 57258b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 57358b359041a29418876f12d37a7082ece9f8a38a4Yang Li return points; 57458b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 57558b359041a29418876f12d37a7082ece9f8a38a4Yang Li 57658b359041a29418876f12d37a7082ece9f8a38a4Yang Li static float[] translate(float[] points, float dx, float dy) { 57758b359041a29418876f12d37a7082ece9f8a38a4Yang Li int size = points.length; 57858b359041a29418876f12d37a7082ece9f8a38a4Yang Li for (int i = 0; i < size; i += 2) { 57958b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i] += dx; 58058b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i + 1] += dy; 58158b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 58258b359041a29418876f12d37a7082ece9f8a38a4Yang Li return points; 58358b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 58458b359041a29418876f12d37a7082ece9f8a38a4Yang Li 58558b359041a29418876f12d37a7082ece9f8a38a4Yang Li static float[] scale(float[] points, float sx, float sy) { 58658b359041a29418876f12d37a7082ece9f8a38a4Yang Li int size = points.length; 58758b359041a29418876f12d37a7082ece9f8a38a4Yang Li for (int i = 0; i < size; i += 2) { 58858b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i] *= sx; 58958b359041a29418876f12d37a7082ece9f8a38a4Yang Li points[i + 1] *= sy; 59058b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 59158b359041a29418876f12d37a7082ece9f8a38a4Yang Li return points; 59258b359041a29418876f12d37a7082ece9f8a38a4Yang Li } 59335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li} 594