1 /* 2 * Copyright (C) 2012 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 17 package com.android.inputmethod.keyboard.internal; 18 19 import android.util.Log; 20 21 import com.android.inputmethod.latin.common.Constants; 22 import com.android.inputmethod.latin.common.InputPointers; 23 import com.android.inputmethod.latin.common.ResizableIntArray; 24 25 /** 26 * This class holds event points to recognize a gesture stroke. 27 * TODO: Should be package private class. 28 */ 29 public final class GestureStrokeRecognitionPoints { 30 private static final String TAG = GestureStrokeRecognitionPoints.class.getSimpleName(); 31 private static final boolean DEBUG = false; 32 private static final boolean DEBUG_SPEED = false; 33 34 // The height of extra area above the keyboard to draw gesture trails. 35 // Proportional to the keyboard height. 36 public static final float EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO = 0.25f; 37 38 private final int mPointerId; 39 private final ResizableIntArray mEventTimes = new ResizableIntArray( 40 Constants.DEFAULT_GESTURE_POINTS_CAPACITY); 41 private final ResizableIntArray mXCoordinates = new ResizableIntArray( 42 Constants.DEFAULT_GESTURE_POINTS_CAPACITY); 43 private final ResizableIntArray mYCoordinates = new ResizableIntArray( 44 Constants.DEFAULT_GESTURE_POINTS_CAPACITY); 45 46 private final GestureStrokeRecognitionParams mRecognitionParams; 47 48 private int mKeyWidth; // pixel 49 private int mMinYCoordinate; // pixel 50 private int mMaxYCoordinate; // pixel 51 // Static threshold for starting gesture detection 52 private int mDetectFastMoveSpeedThreshold; // pixel /sec 53 private int mDetectFastMoveTime; 54 private int mDetectFastMoveX; 55 private int mDetectFastMoveY; 56 // Dynamic threshold for gesture after fast typing 57 private boolean mAfterFastTyping; 58 private int mGestureDynamicDistanceThresholdFrom; // pixel 59 private int mGestureDynamicDistanceThresholdTo; // pixel 60 // Variables for gesture sampling 61 private int mGestureSamplingMinimumDistance; // pixel 62 private long mLastMajorEventTime; 63 private int mLastMajorEventX; 64 private int mLastMajorEventY; 65 // Variables for gesture recognition 66 private int mGestureRecognitionSpeedThreshold; // pixel / sec 67 private int mIncrementalRecognitionSize; 68 private int mLastIncrementalBatchSize; 69 70 private static final int MSEC_PER_SEC = 1000; 71 72 // TODO: Make this package private GestureStrokeRecognitionPoints(final int pointerId, final GestureStrokeRecognitionParams recognitionParams)73 public GestureStrokeRecognitionPoints(final int pointerId, 74 final GestureStrokeRecognitionParams recognitionParams) { 75 mPointerId = pointerId; 76 mRecognitionParams = recognitionParams; 77 } 78 79 // TODO: Make this package private setKeyboardGeometry(final int keyWidth, final int keyboardHeight)80 public void setKeyboardGeometry(final int keyWidth, final int keyboardHeight) { 81 mKeyWidth = keyWidth; 82 mMinYCoordinate = -(int)(keyboardHeight * EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO); 83 mMaxYCoordinate = keyboardHeight; 84 // TODO: Find an appropriate base metric for these length. Maybe diagonal length of the key? 85 mDetectFastMoveSpeedThreshold = (int)( 86 keyWidth * mRecognitionParams.mDetectFastMoveSpeedThreshold); 87 mGestureDynamicDistanceThresholdFrom = (int)( 88 keyWidth * mRecognitionParams.mDynamicDistanceThresholdFrom); 89 mGestureDynamicDistanceThresholdTo = (int)( 90 keyWidth * mRecognitionParams.mDynamicDistanceThresholdTo); 91 mGestureSamplingMinimumDistance = (int)( 92 keyWidth * mRecognitionParams.mSamplingMinimumDistance); 93 mGestureRecognitionSpeedThreshold = (int)( 94 keyWidth * mRecognitionParams.mRecognitionSpeedThreshold); 95 if (DEBUG) { 96 Log.d(TAG, String.format( 97 "[%d] setKeyboardGeometry: keyWidth=%3d tT=%3d >> %3d tD=%3d >> %3d", 98 mPointerId, keyWidth, 99 mRecognitionParams.mDynamicTimeThresholdFrom, 100 mRecognitionParams.mDynamicTimeThresholdTo, 101 mGestureDynamicDistanceThresholdFrom, 102 mGestureDynamicDistanceThresholdTo)); 103 } 104 } 105 106 // TODO: Make this package private getLength()107 public int getLength() { 108 return mEventTimes.getLength(); 109 } 110 111 // TODO: Make this package private addDownEventPoint(final int x, final int y, final int elapsedTimeSinceFirstDown, final int elapsedTimeSinceLastTyping)112 public void addDownEventPoint(final int x, final int y, final int elapsedTimeSinceFirstDown, 113 final int elapsedTimeSinceLastTyping) { 114 reset(); 115 if (elapsedTimeSinceLastTyping < mRecognitionParams.mStaticTimeThresholdAfterFastTyping) { 116 mAfterFastTyping = true; 117 } 118 if (DEBUG) { 119 Log.d(TAG, String.format("[%d] onDownEvent: dT=%3d%s", mPointerId, 120 elapsedTimeSinceLastTyping, mAfterFastTyping ? " afterFastTyping" : "")); 121 } 122 // Call {@link #addEventPoint(int,int,int,boolean)} to record this down event point as a 123 // major event point. 124 addEventPoint(x, y, elapsedTimeSinceFirstDown, true /* isMajorEvent */); 125 } 126 getGestureDynamicDistanceThreshold(final int deltaTime)127 private int getGestureDynamicDistanceThreshold(final int deltaTime) { 128 if (!mAfterFastTyping || deltaTime >= mRecognitionParams.mDynamicThresholdDecayDuration) { 129 return mGestureDynamicDistanceThresholdTo; 130 } 131 final int decayedThreshold = 132 (mGestureDynamicDistanceThresholdFrom - mGestureDynamicDistanceThresholdTo) 133 * deltaTime / mRecognitionParams.mDynamicThresholdDecayDuration; 134 return mGestureDynamicDistanceThresholdFrom - decayedThreshold; 135 } 136 getGestureDynamicTimeThreshold(final int deltaTime)137 private int getGestureDynamicTimeThreshold(final int deltaTime) { 138 if (!mAfterFastTyping || deltaTime >= mRecognitionParams.mDynamicThresholdDecayDuration) { 139 return mRecognitionParams.mDynamicTimeThresholdTo; 140 } 141 final int decayedThreshold = 142 (mRecognitionParams.mDynamicTimeThresholdFrom 143 - mRecognitionParams.mDynamicTimeThresholdTo) 144 * deltaTime / mRecognitionParams.mDynamicThresholdDecayDuration; 145 return mRecognitionParams.mDynamicTimeThresholdFrom - decayedThreshold; 146 } 147 148 // TODO: Make this package private isStartOfAGesture()149 public final boolean isStartOfAGesture() { 150 if (!hasDetectedFastMove()) { 151 return false; 152 } 153 final int size = getLength(); 154 if (size <= 0) { 155 return false; 156 } 157 final int lastIndex = size - 1; 158 final int deltaTime = mEventTimes.get(lastIndex) - mDetectFastMoveTime; 159 if (deltaTime < 0) { 160 return false; 161 } 162 final int deltaDistance = getDistance( 163 mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex), 164 mDetectFastMoveX, mDetectFastMoveY); 165 final int distanceThreshold = getGestureDynamicDistanceThreshold(deltaTime); 166 final int timeThreshold = getGestureDynamicTimeThreshold(deltaTime); 167 final boolean isStartOfAGesture = deltaTime >= timeThreshold 168 && deltaDistance >= distanceThreshold; 169 if (DEBUG) { 170 Log.d(TAG, String.format("[%d] isStartOfAGesture: dT=%3d tT=%3d dD=%3d tD=%3d%s%s", 171 mPointerId, deltaTime, timeThreshold, 172 deltaDistance, distanceThreshold, 173 mAfterFastTyping ? " afterFastTyping" : "", 174 isStartOfAGesture ? " startOfAGesture" : "")); 175 } 176 return isStartOfAGesture; 177 } 178 179 // TODO: Make this package private duplicateLastPointWith(final int time)180 public void duplicateLastPointWith(final int time) { 181 final int lastIndex = getLength() - 1; 182 if (lastIndex >= 0) { 183 final int x = mXCoordinates.get(lastIndex); 184 final int y = mYCoordinates.get(lastIndex); 185 if (DEBUG) { 186 Log.d(TAG, String.format("[%d] duplicateLastPointWith: %d,%d|%d", mPointerId, 187 x, y, time)); 188 } 189 // TODO: Have appendMajorPoint() 190 appendPoint(x, y, time); 191 updateIncrementalRecognitionSize(x, y, time); 192 } 193 } 194 reset()195 private void reset() { 196 mIncrementalRecognitionSize = 0; 197 mLastIncrementalBatchSize = 0; 198 mEventTimes.setLength(0); 199 mXCoordinates.setLength(0); 200 mYCoordinates.setLength(0); 201 mLastMajorEventTime = 0; 202 mDetectFastMoveTime = 0; 203 mAfterFastTyping = false; 204 } 205 appendPoint(final int x, final int y, final int time)206 private void appendPoint(final int x, final int y, final int time) { 207 final int lastIndex = getLength() - 1; 208 // The point that is created by {@link duplicateLastPointWith(int)} may have later event 209 // time than the next {@link MotionEvent}. To maintain the monotonicity of the event time, 210 // drop the successive point here. 211 if (lastIndex >= 0 && mEventTimes.get(lastIndex) > time) { 212 Log.w(TAG, String.format("[%d] drop stale event: %d,%d|%d last: %d,%d|%d", mPointerId, 213 x, y, time, mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex), 214 mEventTimes.get(lastIndex))); 215 return; 216 } 217 mEventTimes.add(time); 218 mXCoordinates.add(x); 219 mYCoordinates.add(y); 220 } 221 updateMajorEvent(final int x, final int y, final int time)222 private void updateMajorEvent(final int x, final int y, final int time) { 223 mLastMajorEventTime = time; 224 mLastMajorEventX = x; 225 mLastMajorEventY = y; 226 } 227 hasDetectedFastMove()228 private final boolean hasDetectedFastMove() { 229 return mDetectFastMoveTime > 0; 230 } 231 detectFastMove(final int x, final int y, final int time)232 private int detectFastMove(final int x, final int y, final int time) { 233 final int size = getLength(); 234 final int lastIndex = size - 1; 235 final int lastX = mXCoordinates.get(lastIndex); 236 final int lastY = mYCoordinates.get(lastIndex); 237 final int dist = getDistance(lastX, lastY, x, y); 238 final int msecs = time - mEventTimes.get(lastIndex); 239 if (msecs > 0) { 240 final int pixels = getDistance(lastX, lastY, x, y); 241 final int pixelsPerSec = pixels * MSEC_PER_SEC; 242 if (DEBUG_SPEED) { 243 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 244 Log.d(TAG, String.format("[%d] detectFastMove: speed=%5.2f", mPointerId, speed)); 245 } 246 // Equivalent to (pixels / msecs < mStartSpeedThreshold / MSEC_PER_SEC) 247 if (!hasDetectedFastMove() && pixelsPerSec > mDetectFastMoveSpeedThreshold * msecs) { 248 if (DEBUG) { 249 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 250 Log.d(TAG, String.format( 251 "[%d] detectFastMove: speed=%5.2f T=%3d points=%3d fastMove", 252 mPointerId, speed, time, size)); 253 } 254 mDetectFastMoveTime = time; 255 mDetectFastMoveX = x; 256 mDetectFastMoveY = y; 257 } 258 } 259 return dist; 260 } 261 262 /** 263 * Add an event point to this gesture stroke recognition points. Returns true if the event 264 * point is on the valid gesture area. 265 * @param x the x-coordinate of the event point 266 * @param y the y-coordinate of the event point 267 * @param time the elapsed time in millisecond from the first gesture down 268 * @param isMajorEvent false if this is a historical move event 269 * @return true if the event point is on the valid gesture area 270 */ 271 // TODO: Make this package private addEventPoint(final int x, final int y, final int time, final boolean isMajorEvent)272 public boolean addEventPoint(final int x, final int y, final int time, 273 final boolean isMajorEvent) { 274 final int size = getLength(); 275 if (size <= 0) { 276 // The first event of this stroke (a.k.a. down event). 277 appendPoint(x, y, time); 278 updateMajorEvent(x, y, time); 279 } else { 280 final int distance = detectFastMove(x, y, time); 281 if (distance > mGestureSamplingMinimumDistance) { 282 appendPoint(x, y, time); 283 } 284 } 285 if (isMajorEvent) { 286 updateIncrementalRecognitionSize(x, y, time); 287 updateMajorEvent(x, y, time); 288 } 289 return y >= mMinYCoordinate && y < mMaxYCoordinate; 290 } 291 updateIncrementalRecognitionSize(final int x, final int y, final int time)292 private void updateIncrementalRecognitionSize(final int x, final int y, final int time) { 293 final int msecs = (int)(time - mLastMajorEventTime); 294 if (msecs <= 0) { 295 return; 296 } 297 final int pixels = getDistance(mLastMajorEventX, mLastMajorEventY, x, y); 298 final int pixelsPerSec = pixels * MSEC_PER_SEC; 299 // Equivalent to (pixels / msecs < mGestureRecognitionThreshold / MSEC_PER_SEC) 300 if (pixelsPerSec < mGestureRecognitionSpeedThreshold * msecs) { 301 mIncrementalRecognitionSize = getLength(); 302 } 303 } 304 305 // TODO: Make this package private hasRecognitionTimePast( final long currentTime, final long lastRecognitionTime)306 public final boolean hasRecognitionTimePast( 307 final long currentTime, final long lastRecognitionTime) { 308 return currentTime > lastRecognitionTime + mRecognitionParams.mRecognitionMinimumTime; 309 } 310 311 // TODO: Make this package private appendAllBatchPoints(final InputPointers out)312 public final void appendAllBatchPoints(final InputPointers out) { 313 appendBatchPoints(out, getLength()); 314 } 315 316 // TODO: Make this package private appendIncrementalBatchPoints(final InputPointers out)317 public final void appendIncrementalBatchPoints(final InputPointers out) { 318 appendBatchPoints(out, mIncrementalRecognitionSize); 319 } 320 appendBatchPoints(final InputPointers out, final int size)321 private void appendBatchPoints(final InputPointers out, final int size) { 322 final int length = size - mLastIncrementalBatchSize; 323 if (length <= 0) { 324 return; 325 } 326 out.append(mPointerId, mEventTimes, mXCoordinates, mYCoordinates, 327 mLastIncrementalBatchSize, length); 328 mLastIncrementalBatchSize = size; 329 } 330 getDistance(final int x1, final int y1, final int x2, final int y2)331 private static int getDistance(final int x1, final int y1, final int x2, final int y2) { 332 return (int)Math.hypot(x1 - x2, y1 - y2); 333 } 334 } 335