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