1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.android.inputmethod.keyboard.internal; 16 17 import android.content.res.TypedArray; 18 import android.util.Log; 19 20 import com.android.inputmethod.latin.InputPointers; 21 import com.android.inputmethod.latin.R; 22 import com.android.inputmethod.latin.ResizableIntArray; 23 import com.android.inputmethod.latin.ResourceUtils; 24 25 public class GestureStroke { 26 private static final String TAG = GestureStroke.class.getSimpleName(); 27 private static final boolean DEBUG = false; 28 private static final boolean DEBUG_SPEED = false; 29 30 public static final int DEFAULT_CAPACITY = 128; 31 32 private final int mPointerId; 33 private final ResizableIntArray mEventTimes = new ResizableIntArray(DEFAULT_CAPACITY); 34 private final ResizableIntArray mXCoordinates = new ResizableIntArray(DEFAULT_CAPACITY); 35 private final ResizableIntArray mYCoordinates = new ResizableIntArray(DEFAULT_CAPACITY); 36 37 private final GestureStrokeParams mParams; 38 39 private int mKeyWidth; // pixel 40 // Static threshold for starting gesture detection 41 private int mDetectFastMoveSpeedThreshold; // pixel /sec 42 private int mDetectFastMoveTime; 43 private int mDetectFastMoveX; 44 private int mDetectFastMoveY; 45 // Dynamic threshold for gesture after fast typing 46 private boolean mAfterFastTyping; 47 private int mGestureDynamicDistanceThresholdFrom; // pixel 48 private int mGestureDynamicDistanceThresholdTo; // pixel 49 // Variables for gesture sampling 50 private int mGestureSamplingMinimumDistance; // pixel 51 private long mLastMajorEventTime; 52 private int mLastMajorEventX; 53 private int mLastMajorEventY; 54 // Variables for gesture recognition 55 private int mGestureRecognitionSpeedThreshold; // pixel / sec 56 private int mIncrementalRecognitionSize; 57 private int mLastIncrementalBatchSize; 58 59 public static final class GestureStrokeParams { 60 // Static threshold for gesture after fast typing 61 public final int mStaticTimeThresholdAfterFastTyping; // msec 62 // Static threshold for starting gesture detection 63 public final float mDetectFastMoveSpeedThreshold; // keyWidth/sec 64 // Dynamic threshold for gesture after fast typing 65 public final int mDynamicThresholdDecayDuration; // msec 66 // Time based threshold values 67 public final int mDynamicTimeThresholdFrom; // msec 68 public final int mDynamicTimeThresholdTo; // msec 69 // Distance based threshold values 70 public final float mDynamicDistanceThresholdFrom; // keyWidth 71 public final float mDynamicDistanceThresholdTo; // keyWidth 72 // Parameters for gesture sampling 73 public final float mSamplingMinimumDistance; // keyWidth 74 // Parameters for gesture recognition 75 public final int mRecognitionMinimumTime; // msec 76 public final float mRecognitionSpeedThreshold; // keyWidth/sec 77 78 // Default GestureStroke parameters for test. 79 public static final GestureStrokeParams FOR_TEST = new GestureStrokeParams(); 80 public static final GestureStrokeParams DEFAULT = FOR_TEST; 81 GestureStrokeParams()82 private GestureStrokeParams() { 83 // These parameter values are default and intended for testing. 84 mStaticTimeThresholdAfterFastTyping = 350; // msec 85 mDetectFastMoveSpeedThreshold = 1.5f; // keyWidth / sec 86 mDynamicThresholdDecayDuration = 450; // msec 87 mDynamicTimeThresholdFrom = 300; // msec 88 mDynamicTimeThresholdTo = 20; // msec 89 mDynamicDistanceThresholdFrom = 6.0f; // keyWidth 90 mDynamicDistanceThresholdTo = 0.35f; // keyWidth 91 // The following parameters' change will affect the result of regression test. 92 mSamplingMinimumDistance = 1.0f / 6.0f; // keyWidth 93 mRecognitionMinimumTime = 100; // msec 94 mRecognitionSpeedThreshold = 5.5f; // keyWidth / sec 95 } 96 GestureStrokeParams(final TypedArray mainKeyboardViewAttr)97 public GestureStrokeParams(final TypedArray mainKeyboardViewAttr) { 98 mStaticTimeThresholdAfterFastTyping = mainKeyboardViewAttr.getInt( 99 R.styleable.MainKeyboardView_gestureStaticTimeThresholdAfterFastTyping, 100 DEFAULT.mStaticTimeThresholdAfterFastTyping); 101 mDetectFastMoveSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr, 102 R.styleable.MainKeyboardView_gestureDetectFastMoveSpeedThreshold, 103 DEFAULT.mDetectFastMoveSpeedThreshold); 104 mDynamicThresholdDecayDuration = mainKeyboardViewAttr.getInt( 105 R.styleable.MainKeyboardView_gestureDynamicThresholdDecayDuration, 106 DEFAULT.mDynamicThresholdDecayDuration); 107 mDynamicTimeThresholdFrom = mainKeyboardViewAttr.getInt( 108 R.styleable.MainKeyboardView_gestureDynamicTimeThresholdFrom, 109 DEFAULT.mDynamicTimeThresholdFrom); 110 mDynamicTimeThresholdTo = mainKeyboardViewAttr.getInt( 111 R.styleable.MainKeyboardView_gestureDynamicTimeThresholdTo, 112 DEFAULT.mDynamicTimeThresholdTo); 113 mDynamicDistanceThresholdFrom = ResourceUtils.getFraction(mainKeyboardViewAttr, 114 R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdFrom, 115 DEFAULT.mDynamicDistanceThresholdFrom); 116 mDynamicDistanceThresholdTo = ResourceUtils.getFraction(mainKeyboardViewAttr, 117 R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdTo, 118 DEFAULT.mDynamicDistanceThresholdTo); 119 mSamplingMinimumDistance = ResourceUtils.getFraction(mainKeyboardViewAttr, 120 R.styleable.MainKeyboardView_gestureSamplingMinimumDistance, 121 DEFAULT.mSamplingMinimumDistance); 122 mRecognitionMinimumTime = mainKeyboardViewAttr.getInt( 123 R.styleable.MainKeyboardView_gestureRecognitionMinimumTime, 124 DEFAULT.mRecognitionMinimumTime); 125 mRecognitionSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr, 126 R.styleable.MainKeyboardView_gestureRecognitionSpeedThreshold, 127 DEFAULT.mRecognitionSpeedThreshold); 128 } 129 } 130 131 private static final int MSEC_PER_SEC = 1000; 132 GestureStroke(final int pointerId, final GestureStrokeParams params)133 public GestureStroke(final int pointerId, final GestureStrokeParams params) { 134 mPointerId = pointerId; 135 mParams = params; 136 } 137 setKeyboardGeometry(final int keyWidth)138 public void setKeyboardGeometry(final int keyWidth) { 139 mKeyWidth = keyWidth; 140 // TODO: Find an appropriate base metric for these length. Maybe diagonal length of the key? 141 mDetectFastMoveSpeedThreshold = (int)(keyWidth * mParams.mDetectFastMoveSpeedThreshold); 142 mGestureDynamicDistanceThresholdFrom = 143 (int)(keyWidth * mParams.mDynamicDistanceThresholdFrom); 144 mGestureDynamicDistanceThresholdTo = (int)(keyWidth * mParams.mDynamicDistanceThresholdTo); 145 mGestureSamplingMinimumDistance = (int)(keyWidth * mParams.mSamplingMinimumDistance); 146 mGestureRecognitionSpeedThreshold = (int)(keyWidth * mParams.mRecognitionSpeedThreshold); 147 if (DEBUG) { 148 Log.d(TAG, String.format( 149 "[%d] setKeyboardGeometry: keyWidth=%3d tT=%3d >> %3d tD=%3d >> %3d", 150 mPointerId, keyWidth, 151 mParams.mDynamicTimeThresholdFrom, 152 mParams.mDynamicTimeThresholdTo, 153 mGestureDynamicDistanceThresholdFrom, 154 mGestureDynamicDistanceThresholdTo)); 155 } 156 } 157 onDownEvent(final int x, final int y, final long downTime, final long gestureFirstDownTime, final long lastTypingTime)158 public void onDownEvent(final int x, final int y, final long downTime, 159 final long gestureFirstDownTime, final long lastTypingTime) { 160 reset(); 161 final long elapsedTimeAfterTyping = downTime - lastTypingTime; 162 if (elapsedTimeAfterTyping < mParams.mStaticTimeThresholdAfterFastTyping) { 163 mAfterFastTyping = true; 164 } 165 if (DEBUG) { 166 Log.d(TAG, String.format("[%d] onDownEvent: dT=%3d%s", mPointerId, 167 elapsedTimeAfterTyping, mAfterFastTyping ? " afterFastTyping" : "")); 168 } 169 final int elapsedTimeFromFirstDown = (int)(downTime - gestureFirstDownTime); 170 addPoint(x, y, elapsedTimeFromFirstDown, true /* isMajorEvent */); 171 } 172 getGestureDynamicDistanceThreshold(final int deltaTime)173 private int getGestureDynamicDistanceThreshold(final int deltaTime) { 174 if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) { 175 return mGestureDynamicDistanceThresholdTo; 176 } 177 final int decayedThreshold = 178 (mGestureDynamicDistanceThresholdFrom - mGestureDynamicDistanceThresholdTo) 179 * deltaTime / mParams.mDynamicThresholdDecayDuration; 180 return mGestureDynamicDistanceThresholdFrom - decayedThreshold; 181 } 182 getGestureDynamicTimeThreshold(final int deltaTime)183 private int getGestureDynamicTimeThreshold(final int deltaTime) { 184 if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) { 185 return mParams.mDynamicTimeThresholdTo; 186 } 187 final int decayedThreshold = 188 (mParams.mDynamicTimeThresholdFrom - mParams.mDynamicTimeThresholdTo) 189 * deltaTime / mParams.mDynamicThresholdDecayDuration; 190 return mParams.mDynamicTimeThresholdFrom - decayedThreshold; 191 } 192 isStartOfAGesture()193 public final boolean isStartOfAGesture() { 194 if (!hasDetectedFastMove()) { 195 return false; 196 } 197 final int size = mEventTimes.getLength(); 198 if (size <= 0) { 199 return false; 200 } 201 final int lastIndex = size - 1; 202 final int deltaTime = mEventTimes.get(lastIndex) - mDetectFastMoveTime; 203 if (deltaTime < 0) { 204 return false; 205 } 206 final int deltaDistance = getDistance( 207 mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex), 208 mDetectFastMoveX, mDetectFastMoveY); 209 final int distanceThreshold = getGestureDynamicDistanceThreshold(deltaTime); 210 final int timeThreshold = getGestureDynamicTimeThreshold(deltaTime); 211 final boolean isStartOfAGesture = deltaTime >= timeThreshold 212 && deltaDistance >= distanceThreshold; 213 if (DEBUG) { 214 Log.d(TAG, String.format("[%d] isStartOfAGesture: dT=%3d tT=%3d dD=%3d tD=%3d%s%s", 215 mPointerId, deltaTime, timeThreshold, 216 deltaDistance, distanceThreshold, 217 mAfterFastTyping ? " afterFastTyping" : "", 218 isStartOfAGesture ? " startOfAGesture" : "")); 219 } 220 return isStartOfAGesture; 221 } 222 reset()223 protected void reset() { 224 mIncrementalRecognitionSize = 0; 225 mLastIncrementalBatchSize = 0; 226 mEventTimes.setLength(0); 227 mXCoordinates.setLength(0); 228 mYCoordinates.setLength(0); 229 mLastMajorEventTime = 0; 230 mDetectFastMoveTime = 0; 231 mAfterFastTyping = false; 232 } 233 appendPoint(final int x, final int y, final int time)234 private void appendPoint(final int x, final int y, final int time) { 235 mEventTimes.add(time); 236 mXCoordinates.add(x); 237 mYCoordinates.add(y); 238 } 239 updateMajorEvent(final int x, final int y, final int time)240 private void updateMajorEvent(final int x, final int y, final int time) { 241 mLastMajorEventTime = time; 242 mLastMajorEventX = x; 243 mLastMajorEventY = y; 244 } 245 hasDetectedFastMove()246 private final boolean hasDetectedFastMove() { 247 return mDetectFastMoveTime > 0; 248 } 249 detectFastMove(final int x, final int y, final int time)250 private int detectFastMove(final int x, final int y, final int time) { 251 final int size = mEventTimes.getLength(); 252 final int lastIndex = size - 1; 253 final int lastX = mXCoordinates.get(lastIndex); 254 final int lastY = mYCoordinates.get(lastIndex); 255 final int dist = getDistance(lastX, lastY, x, y); 256 final int msecs = time - mEventTimes.get(lastIndex); 257 if (msecs > 0) { 258 final int pixels = getDistance(lastX, lastY, x, y); 259 final int pixelsPerSec = pixels * MSEC_PER_SEC; 260 if (DEBUG_SPEED) { 261 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 262 Log.d(TAG, String.format("[%d] detectFastMove: speed=%5.2f", mPointerId, speed)); 263 } 264 // Equivalent to (pixels / msecs < mStartSpeedThreshold / MSEC_PER_SEC) 265 if (!hasDetectedFastMove() && pixelsPerSec > mDetectFastMoveSpeedThreshold * msecs) { 266 if (DEBUG) { 267 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 268 Log.d(TAG, String.format( 269 "[%d] detectFastMove: speed=%5.2f T=%3d points=%3d fastMove", 270 mPointerId, speed, time, size)); 271 } 272 mDetectFastMoveTime = time; 273 mDetectFastMoveX = x; 274 mDetectFastMoveY = y; 275 } 276 } 277 return dist; 278 } 279 addPoint(final int x, final int y, final int time, final boolean isMajorEvent)280 public void addPoint(final int x, final int y, final int time, final boolean isMajorEvent) { 281 final int size = mEventTimes.getLength(); 282 if (size <= 0) { 283 // Down event 284 appendPoint(x, y, time); 285 updateMajorEvent(x, y, time); 286 } else { 287 final int distance = detectFastMove(x, y, time); 288 if (distance > mGestureSamplingMinimumDistance) { 289 appendPoint(x, y, time); 290 } 291 } 292 if (isMajorEvent) { 293 updateIncrementalRecognitionSize(x, y, time); 294 updateMajorEvent(x, y, time); 295 } 296 } 297 updateIncrementalRecognitionSize(final int x, final int y, final int time)298 private void updateIncrementalRecognitionSize(final int x, final int y, final int time) { 299 final int msecs = (int)(time - mLastMajorEventTime); 300 if (msecs <= 0) { 301 return; 302 } 303 final int pixels = getDistance(mLastMajorEventX, mLastMajorEventY, x, y); 304 final int pixelsPerSec = pixels * MSEC_PER_SEC; 305 // Equivalent to (pixels / msecs < mGestureRecognitionThreshold / MSEC_PER_SEC) 306 if (pixelsPerSec < mGestureRecognitionSpeedThreshold * msecs) { 307 mIncrementalRecognitionSize = mEventTimes.getLength(); 308 } 309 } 310 hasRecognitionTimePast( final long currentTime, final long lastRecognitionTime)311 public final boolean hasRecognitionTimePast( 312 final long currentTime, final long lastRecognitionTime) { 313 return currentTime > lastRecognitionTime + mParams.mRecognitionMinimumTime; 314 } 315 appendAllBatchPoints(final InputPointers out)316 public final void appendAllBatchPoints(final InputPointers out) { 317 appendBatchPoints(out, mEventTimes.getLength()); 318 } 319 appendIncrementalBatchPoints(final InputPointers out)320 public final void appendIncrementalBatchPoints(final InputPointers out) { 321 appendBatchPoints(out, mIncrementalRecognitionSize); 322 } 323 appendBatchPoints(final InputPointers out, final int size)324 private void appendBatchPoints(final InputPointers out, final int size) { 325 final int length = size - mLastIncrementalBatchSize; 326 if (length <= 0) { 327 return; 328 } 329 out.append(mPointerId, mEventTimes, mXCoordinates, mYCoordinates, 330 mLastIncrementalBatchSize, length); 331 mLastIncrementalBatchSize = size; 332 } 333 getDistance(final int x1, final int y1, final int x2, final int y2)334 private static int getDistance(final int x1, final int y1, final int x2, final int y2) { 335 final int dx = x1 - x2; 336 final int dy = y1 - y2; 337 // Note that, in recent versions of Android, FloatMath is actually slower than 338 // java.lang.Math due to the way the JIT optimizes java.lang.Math. 339 return (int)Math.sqrt(dx * dx + dy * dy); 340 } 341 } 342