1/* 2 * Copyright (C) 2008-2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.gesture; 18 19import android.graphics.RectF; 20import android.util.Log; 21 22import java.util.ArrayList; 23import java.util.Arrays; 24import java.io.Closeable; 25import java.io.IOException; 26 27import static android.gesture.GestureConstants.*; 28 29final class GestureUtilities { 30 private static final int TEMPORAL_SAMPLING_RATE = 16; 31 32 private GestureUtilities() { 33 } 34 35 /** 36 * Closes the specified stream. 37 * 38 * @param stream The stream to close. 39 */ 40 static void closeStream(Closeable stream) { 41 if (stream != null) { 42 try { 43 stream.close(); 44 } catch (IOException e) { 45 Log.e(LOG_TAG, "Could not close stream", e); 46 } 47 } 48 } 49 50 static float[] spatialSampling(Gesture gesture, int sampleMatrixDimension) { 51 final float targetPatchSize = sampleMatrixDimension - 1; // edge inclusive 52 float[] sample = new float[sampleMatrixDimension * sampleMatrixDimension]; 53 Arrays.fill(sample, 0); 54 55 RectF rect = gesture.getBoundingBox(); 56 float sx = targetPatchSize / rect.width(); 57 float sy = targetPatchSize / rect.height(); 58 float scale = sx < sy ? sx : sy; 59 60 float preDx = -rect.centerX(); 61 float preDy = -rect.centerY(); 62 float postDx = targetPatchSize / 2; 63 float postDy = targetPatchSize / 2; 64 65 final ArrayList<GestureStroke> strokes = gesture.getStrokes(); 66 final int count = strokes.size(); 67 68 int size; 69 float xpos; 70 float ypos; 71 72 for (int index = 0; index < count; index++) { 73 final GestureStroke stroke = strokes.get(index); 74 float[] strokepoints = stroke.points; 75 size = strokepoints.length; 76 77 final float[] pts = new float[size]; 78 79 for (int i = 0; i < size; i += 2) { 80 pts[i] = (strokepoints[i] + preDx) * scale + postDx; 81 pts[i + 1] = (strokepoints[i + 1] + preDy) * scale + postDy; 82 } 83 84 float segmentEndX = -1; 85 float segmentEndY = -1; 86 87 for (int i = 0; i < size; i += 2) { 88 89 float segmentStartX = pts[i] < 0 ? 0 : pts[i]; 90 float segmentStartY = pts[i + 1] < 0 ? 0 : pts[i + 1]; 91 92 if (segmentStartX > targetPatchSize) { 93 segmentStartX = targetPatchSize; 94 } 95 96 if (segmentStartY > targetPatchSize) { 97 segmentStartY = targetPatchSize; 98 } 99 100 plot(segmentStartX, segmentStartY, sample, sampleMatrixDimension); 101 102 if (segmentEndX != -1) { 103 // evaluate horizontally 104 if (segmentEndX > segmentStartX) { 105 xpos = (float) Math.ceil(segmentStartX); 106 float slope = (segmentEndY - segmentStartY) / (segmentEndX - segmentStartX); 107 while (xpos < segmentEndX) { 108 ypos = slope * (xpos - segmentStartX) + segmentStartY; 109 plot(xpos, ypos, sample, sampleMatrixDimension); 110 xpos++; 111 } 112 } else if (segmentEndX < segmentStartX){ 113 xpos = (float) Math.ceil(segmentEndX); 114 float slope = (segmentEndY - segmentStartY) / (segmentEndX - segmentStartX); 115 while (xpos < segmentStartX) { 116 ypos = slope * (xpos - segmentStartX) + segmentStartY; 117 plot(xpos, ypos, sample, sampleMatrixDimension); 118 xpos++; 119 } 120 } 121 122 // evaluating vertically 123 if (segmentEndY > segmentStartY) { 124 ypos = (float) Math.ceil(segmentStartY); 125 float invertSlope = (segmentEndX - segmentStartX) / (segmentEndY - segmentStartY); 126 while (ypos < segmentEndY) { 127 xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 128 plot(xpos, ypos, sample, sampleMatrixDimension); 129 ypos++; 130 } 131 } else if (segmentEndY < segmentStartY) { 132 ypos = (float) Math.ceil(segmentEndY); 133 float invertSlope = (segmentEndX - segmentStartX) / (segmentEndY - segmentStartY); 134 while (ypos < segmentStartY) { 135 xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 136 plot(xpos, ypos, sample, sampleMatrixDimension); 137 ypos++; 138 } 139 } 140 } 141 142 segmentEndX = segmentStartX; 143 segmentEndY = segmentStartY; 144 } 145 } 146 147 148 return sample; 149 } 150 151 private static void plot(float x, float y, float[] sample, int sampleSize) { 152 x = x < 0 ? 0 : x; 153 y = y < 0 ? 0 : y; 154 int xFloor = (int) Math.floor(x); 155 int xCeiling = (int) Math.ceil(x); 156 int yFloor = (int) Math.floor(y); 157 int yCeiling = (int) Math.ceil(y); 158 159 // if it's an integer 160 if (x == xFloor && y == yFloor) { 161 int index = yCeiling * sampleSize + xCeiling; 162 if (sample[index] < 1){ 163 sample[index] = 1; 164 } 165 } else { 166 double topLeft = Math.sqrt(Math.pow(xFloor - x, 2) + Math.pow(yFloor - y, 2)); 167 double topRight = Math.sqrt(Math.pow(xCeiling - x, 2) + Math.pow(yFloor - y, 2)); 168 double btmLeft = Math.sqrt(Math.pow(xFloor - x, 2) + Math.pow(yCeiling - y, 2)); 169 double btmRight = Math.sqrt(Math.pow(xCeiling - x, 2) + Math.pow(yCeiling - y, 2)); 170 double sum = topLeft + topRight + btmLeft + btmRight; 171 172 double value = topLeft / sum; 173 int index = yFloor * sampleSize + xFloor; 174 if (value > sample[index]){ 175 sample[index] = (float) value; 176 } 177 178 value = topRight / sum; 179 index = yFloor * sampleSize + xCeiling; 180 if (value > sample[index]){ 181 sample[index] = (float) value; 182 } 183 184 value = btmLeft / sum; 185 index = yCeiling * sampleSize + xFloor; 186 if (value > sample[index]){ 187 sample[index] = (float) value; 188 } 189 190 value = btmRight / sum; 191 index = yCeiling * sampleSize + xCeiling; 192 if (value > sample[index]){ 193 sample[index] = (float) value; 194 } 195 } 196 } 197 198 /** 199 * Featurize a stroke into a vector of a given number of elements 200 * 201 * @param stroke 202 * @param sampleSize 203 * @return a float array 204 */ 205 static float[] temporalSampling(GestureStroke stroke, int sampleSize) { 206 final float increment = stroke.length / (sampleSize - 1); 207 int vectorLength = sampleSize * 2; 208 float[] vector = new float[vectorLength]; 209 float distanceSoFar = 0; 210 float[] pts = stroke.points; 211 float lstPointX = pts[0]; 212 float lstPointY = pts[1]; 213 int index = 0; 214 float currentPointX = Float.MIN_VALUE; 215 float currentPointY = Float.MIN_VALUE; 216 vector[index] = lstPointX; 217 index++; 218 vector[index] = lstPointY; 219 index++; 220 int i = 0; 221 int count = pts.length / 2; 222 while (i < count) { 223 if (currentPointX == Float.MIN_VALUE) { 224 i++; 225 if (i >= count) { 226 break; 227 } 228 currentPointX = pts[i * 2]; 229 currentPointY = pts[i * 2 + 1]; 230 } 231 float deltaX = currentPointX - lstPointX; 232 float deltaY = currentPointY - lstPointY; 233 float distance = (float) Math.sqrt(deltaX * deltaX + deltaY * deltaY); 234 if (distanceSoFar + distance >= increment) { 235 float ratio = (increment - distanceSoFar) / distance; 236 float nx = lstPointX + ratio * deltaX; 237 float ny = lstPointY + ratio * deltaY; 238 vector[index] = nx; 239 index++; 240 vector[index] = ny; 241 index++; 242 lstPointX = nx; 243 lstPointY = ny; 244 distanceSoFar = 0; 245 } else { 246 lstPointX = currentPointX; 247 lstPointY = currentPointY; 248 currentPointX = Float.MIN_VALUE; 249 currentPointY = Float.MIN_VALUE; 250 distanceSoFar += distance; 251 } 252 } 253 254 for (i = index; i < vectorLength; i += 2) { 255 vector[i] = lstPointX; 256 vector[i + 1] = lstPointY; 257 } 258 return vector; 259 } 260 261 /** 262 * Calculate the centroid 263 * 264 * @param points 265 * @return the centroid 266 */ 267 static float[] computeCentroid(float[] points) { 268 float centerX = 0; 269 float centerY = 0; 270 int count = points.length; 271 for (int i = 0; i < count; i++) { 272 centerX += points[i]; 273 i++; 274 centerY += points[i]; 275 } 276 float[] center = new float[2]; 277 center[0] = 2 * centerX / count; 278 center[1] = 2 * centerY / count; 279 280 return center; 281 } 282 283 /** 284 * calculate the variance-covariance matrix, treat each point as a sample 285 * 286 * @param points 287 * @return the covariance matrix 288 */ 289 private static double[][] computeCoVariance(float[] points) { 290 double[][] array = new double[2][2]; 291 array[0][0] = 0; 292 array[0][1] = 0; 293 array[1][0] = 0; 294 array[1][1] = 0; 295 int count = points.length; 296 for (int i = 0; i < count; i++) { 297 float x = points[i]; 298 i++; 299 float y = points[i]; 300 array[0][0] += x * x; 301 array[0][1] += x * y; 302 array[1][0] = array[0][1]; 303 array[1][1] += y * y; 304 } 305 array[0][0] /= (count / 2); 306 array[0][1] /= (count / 2); 307 array[1][0] /= (count / 2); 308 array[1][1] /= (count / 2); 309 310 return array; 311 } 312 313 static float computeTotalLength(float[] points) { 314 float sum = 0; 315 int count = points.length - 4; 316 for (int i = 0; i < count; i += 2) { 317 float dx = points[i + 2] - points[i]; 318 float dy = points[i + 3] - points[i + 1]; 319 sum += Math.sqrt(dx * dx + dy * dy); 320 } 321 return sum; 322 } 323 324 static double computeStraightness(float[] points) { 325 float totalLen = computeTotalLength(points); 326 float dx = points[2] - points[0]; 327 float dy = points[3] - points[1]; 328 return Math.sqrt(dx * dx + dy * dy) / totalLen; 329 } 330 331 static double computeStraightness(float[] points, float totalLen) { 332 float dx = points[2] - points[0]; 333 float dy = points[3] - points[1]; 334 return Math.sqrt(dx * dx + dy * dy) / totalLen; 335 } 336 337 /** 338 * Calculate the squared Euclidean distance between two vectors 339 * 340 * @param vector1 341 * @param vector2 342 * @return the distance 343 */ 344 static double squaredEuclideanDistance(float[] vector1, float[] vector2) { 345 double squaredDistance = 0; 346 int size = vector1.length; 347 for (int i = 0; i < size; i++) { 348 float difference = vector1[i] - vector2[i]; 349 squaredDistance += difference * difference; 350 } 351 return squaredDistance / size; 352 } 353 354 /** 355 * Calculate the cosine distance between two instances 356 * 357 * @param vector1 358 * @param vector2 359 * @return the distance between 0 and Math.PI 360 */ 361 static double cosineDistance(float[] vector1, float[] vector2) { 362 float sum = 0; 363 int len = vector1.length; 364 for (int i = 0; i < len; i++) { 365 sum += vector1[i] * vector2[i]; 366 } 367 return Math.acos(sum); 368 } 369 370 static OrientedBoundingBox computeOrientedBoundingBox(ArrayList<GesturePoint> pts) { 371 GestureStroke stroke = new GestureStroke(pts); 372 float[] points = temporalSampling(stroke, TEMPORAL_SAMPLING_RATE); 373 return computeOrientedBoundingBox(points); 374 } 375 376 static OrientedBoundingBox computeOrientedBoundingBox(float[] points) { 377 float[] meanVector = computeCentroid(points); 378 return computeOrientedBoundingBox(points, meanVector); 379 } 380 381 static OrientedBoundingBox computeOrientedBoundingBox(float[] points, float[] centroid) { 382 translate(points, -centroid[0], -centroid[1]); 383 384 double[][] array = computeCoVariance(points); 385 double[] targetVector = computeOrientation(array); 386 387 float angle; 388 if (targetVector[0] == 0 && targetVector[1] == 0) { 389 angle = (float) -Math.PI/2; 390 } else { // -PI<alpha<PI 391 angle = (float) Math.atan2(targetVector[1], targetVector[0]); 392 rotate(points, -angle); 393 } 394 395 float minx = Float.MAX_VALUE; 396 float miny = Float.MAX_VALUE; 397 float maxx = Float.MIN_VALUE; 398 float maxy = Float.MIN_VALUE; 399 int count = points.length; 400 for (int i = 0; i < count; i++) { 401 if (points[i] < minx) { 402 minx = points[i]; 403 } 404 if (points[i] > maxx) { 405 maxx = points[i]; 406 } 407 i++; 408 if (points[i] < miny) { 409 miny = points[i]; 410 } 411 if (points[i] > maxy) { 412 maxy = points[i]; 413 } 414 } 415 416 return new OrientedBoundingBox((float) (angle * 180 / Math.PI), centroid[0], centroid[1], maxx - minx, maxy - miny); 417 } 418 419 private static double[] computeOrientation(double[][] covarianceMatrix) { 420 double[] targetVector = new double[2]; 421 if (covarianceMatrix[0][1] == 0 || covarianceMatrix[1][0] == 0) { 422 targetVector[0] = 1; 423 targetVector[1] = 0; 424 } 425 426 double a = -covarianceMatrix[0][0] - covarianceMatrix[1][1]; 427 double b = covarianceMatrix[0][0] * covarianceMatrix[1][1] - covarianceMatrix[0][1] 428 * covarianceMatrix[1][0]; 429 double value = a / 2; 430 double rightside = Math.sqrt(Math.pow(value, 2) - b); 431 double lambda1 = -value + rightside; 432 double lambda2 = -value - rightside; 433 if (lambda1 == lambda2) { 434 targetVector[0] = 0; 435 targetVector[1] = 0; 436 } else { 437 double lambda = lambda1 > lambda2 ? lambda1 : lambda2; 438 targetVector[0] = 1; 439 targetVector[1] = (lambda - covarianceMatrix[0][0]) / covarianceMatrix[0][1]; 440 } 441 return targetVector; 442 } 443 444 445 static float[] rotate(float[] points, double angle) { 446 double cos = Math.cos(angle); 447 double sin = Math.sin(angle); 448 int size = points.length; 449 for (int i = 0; i < size; i += 2) { 450 float x = (float) (points[i] * cos - points[i + 1] * sin); 451 float y = (float) (points[i] * sin + points[i + 1] * cos); 452 points[i] = x; 453 points[i + 1] = y; 454 } 455 return points; 456 } 457 458 static float[] translate(float[] points, float dx, float dy) { 459 int size = points.length; 460 for (int i = 0; i < size; i += 2) { 461 points[i] += dx; 462 points[i + 1] += dy; 463 } 464 return points; 465 } 466 467 static float[] scale(float[] points, float sx, float sy) { 468 int size = points.length; 469 for (int i = 0; i < size; i += 2) { 470 points[i] *= sx; 471 points[i + 1] *= sy; 472 } 473 return points; 474 } 475} 476