Using distance to the edge of key as proximity detection

Because there may be very long key, such as space bar on tablet, we
should not use the distance between the touch point and the center of
key as proximity detection.  Instead of that, this change uses the
distance between the point and the nearest edge of key as proximity
detection.

Also this change fixes the bug that space key (code 32) was not
counted in proximity detection.

Bug: 3164020
Bug: 3168138
Change-Id: I687f1ce94a8e944c3f6eea0fe00e18ed6e68e278

5 files changed, 80 insertions, 84 deletions

diff --git a/java/src/com/android/inputmethod/latin/BaseKeyboard.java b/java/src/com/android/inputmethod/latin/BaseKeyboard.java
index 266300eb3..e5b2756d4 100644
--- a/java/src/com/android/inputmethod/latin/BaseKeyboard.java
+++ b/java/src/com/android/inputmethod/latin/BaseKeyboard.java
@@ -24,7 +24,6 @@ import android.content.res.TypedArray;
 import android.content.res.XmlResourceParser;
 import android.graphics.drawable.Drawable;
 import android.text.TextUtils;
-import android.util.DisplayMetrics;
 import android.util.Log;
 import android.util.TypedValue;
 import android.util.Xml;
@@ -109,15 +108,16 @@ public class BaseKeyboard {
 
     // Variables for pre-computing nearest keys.
 
-    private final int GRID_WIDTH;
-    private final int GRID_HEIGHT;
+    public final int GRID_WIDTH;
+    public final int GRID_HEIGHT;
     private final int GRID_SIZE;
     private int mCellWidth;
     private int mCellHeight;
     private int[][] mGridNeighbors;
     private int mProximityThreshold;
+    private static int[] EMPTY_INT_ARRAY = new int[0];
     /** Number of key widths from current touch point to search for nearest keys. */
-    private static float SEARCH_DISTANCE = 1.8f;
+    private static float SEARCH_DISTANCE = 1.2f;
 
     /**
      * Container for keys in the keyboard. All keys in a row are at the same Y-coordinate.
@@ -402,18 +402,21 @@ public class BaseKeyboard {
         }
 
         /**
-         * Returns the square of the distance between the center of the key and the given point.
+         * Returns the square of the distance to the nearest edge of the key and the given point.
          * @param x the x-coordinate of the point
          * @param y the y-coordinate of the point
-         * @return the square of the distance of the point from the center of the key
+         * @return the square of the distance of the point from the nearest edge of the key
          */
-        public int squaredDistanceFrom(int x, int y) {
-            // We should count vertical gap between rows to calculate the center of this Key.
-            // TODO: We should re-think how we define the center of the key.
-            final int verticalGap = keyboard.getVerticalGap();
-            int xDist = this.x + width / 2 - x;
-            int yDist = this.y + (height + verticalGap) / 2 - y;
-            return xDist * xDist + yDist * yDist;
+        public int squaredDistanceToEdge(int x, int y) {
+            final int left = this.x;
+            final int right = left + this.width;
+            final int top = this.y;
+            final int bottom = top + this.height;
+            final int edgeX = x < left ? left : (x > right ? right : x);
+            final int edgeY = y < top ? top : (y > bottom ? bottom : y);
+            final int dx = x - edgeX;
+            final int dy = y - edgeY;
+            return dx * dx + dy * dy;
         }
 
         /**
@@ -633,24 +636,21 @@ public class BaseKeyboard {
         mCellWidth = (getMinWidth() + GRID_WIDTH - 1) / GRID_WIDTH;
         mCellHeight = (getHeight() + GRID_HEIGHT - 1) / GRID_HEIGHT;
         mGridNeighbors = new int[GRID_SIZE][];
-        int[] indices = new int[mKeys.size()];
+        final int[] indices = new int[mKeys.size()];
         final int gridWidth = GRID_WIDTH * mCellWidth;
         final int gridHeight = GRID_HEIGHT * mCellHeight;
+        final int threshold = mProximityThreshold;
         for (int x = 0; x < gridWidth; x += mCellWidth) {
             for (int y = 0; y < gridHeight; y += mCellHeight) {
+                final int centerX = x + mCellWidth / 2;
+                final int centerY = y + mCellHeight / 2;
                 int count = 0;
                 for (int i = 0; i < mKeys.size(); i++) {
                     final Key key = mKeys.get(i);
-                    final int threshold = mProximityThreshold;
-                    if (key.squaredDistanceFrom(x, y) < threshold ||
-                            key.squaredDistanceFrom(x + mCellWidth - 1, y) < threshold ||
-                            key.squaredDistanceFrom(x + mCellWidth - 1, y + mCellHeight - 1)
-                                < threshold ||
-                            key.squaredDistanceFrom(x, y + mCellHeight - 1) < threshold) {
+                    if (key.squaredDistanceToEdge(centerX, centerY) < threshold)
                         indices[count++] = i;
-                    }
                 }
-                int [] cell = new int[count];
+                final int[] cell = new int[count];
                 System.arraycopy(indices, 0, cell, 0, count);
                 mGridNeighbors[(y / mCellHeight) * GRID_WIDTH + (x / mCellWidth)] = cell;
             }
@@ -672,7 +672,7 @@ public class BaseKeyboard {
                 return mGridNeighbors[index];
             }
         }
-        return new int[0];
+        return EMPTY_INT_ARRAY;
     }
 
     // TODO should be private
diff --git a/java/src/com/android/inputmethod/latin/BaseKeyboardView.java b/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
index 4ba6fbddc..070d031e7 100644
--- a/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
+++ b/java/src/com/android/inputmethod/latin/BaseKeyboardView.java
@@ -71,6 +71,7 @@ import java.util.WeakHashMap;
 public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
     private static final String TAG = "BaseKeyboardView";
     private static final boolean DEBUG = false;
+    private static final boolean DEBUG_KEYBOARD_GRID = false;
 
     public static final int NOT_A_TOUCH_COORDINATE = -1;
 
@@ -183,8 +184,6 @@ public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
     // Main keyboard
     private BaseKeyboard mKeyboard;
     private Key[] mKeys;
-    // TODO this attribute should be gotten from Keyboard.
-    private int mKeyboardVerticalGap;
 
     // Key preview popup
     private boolean mInForeground;
@@ -609,7 +608,6 @@ public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
         LatinImeLogger.onSetKeyboard(keyboard);
         mKeys = mKeyDetector.setKeyboard(keyboard, -getPaddingLeft(),
                 -getPaddingTop() + mVerticalCorrection);
-        mKeyboardVerticalGap = (int)getResources().getDimension(R.dimen.key_bottom_gap);
         for (PointerTracker tracker : mPointerTrackers) {
             tracker.setKeyboard(keyboard, mKeys, mKeyHysteresisDistance);
         }
@@ -617,7 +615,7 @@ public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
         // Hint to reallocate the buffer if the size changed
         mKeyboardChanged = true;
         invalidateAllKeys();
-        computeProximityThreshold(keyboard);
+        computeProximityThreshold(keyboard, mKeys);
         mMiniKeyboardCache.clear();
     }
 
@@ -713,23 +711,27 @@ public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
     }
 
     /**
-     * Compute the average distance between adjacent keys (horizontally and vertically)
-     * and square it to get the proximity threshold. We use a square here and in computing
-     * the touch distance from a key's center to avoid taking a square root.
+     * Compute the most common key width and use it as proximity key detection threshold.
      * @param keyboard
+     * @param keys
      */
-    private void computeProximityThreshold(BaseKeyboard keyboard) {
-        if (keyboard == null) return;
-        final Key[] keys = mKeys;
-        if (keys == null) return;
-        int length = keys.length;
-        int dimensionSum = 0;
-        for (int i = 0; i < length; i++) {
-            Key key = keys[i];
-            dimensionSum += Math.min(key.width, key.height + mKeyboardVerticalGap) + key.gap;
+    private void computeProximityThreshold(BaseKeyboard keyboard, Key[] keys) {
+        if (keyboard == null || keys == null || keys.length == 0) return;
+        final HashMap<Integer, Integer> histogram = new HashMap<Integer, Integer>();
+        int maxCount = 0;
+        int mostCommonWidth = 0;
+        for (Key key : keys) {
+            final Integer width = key.width + key.gap;
+            Integer count = histogram.get(width);
+            if (count == null)
+                count = 0;
+            histogram.put(width, ++count);
+            if (count > maxCount) {
+                maxCount = count;
+                mostCommonWidth = width;
+            }
         }
-        if (dimensionSum < 0 || length == 0) return;
-        mKeyDetector.setProximityThreshold((int) (dimensionSum * 1.4f / length));
+        mKeyDetector.setProximityThreshold(mostCommonWidth);
     }
 
     @Override
@@ -868,6 +870,20 @@ public class BaseKeyboardView extends View implements PointerTracker.UIProxy {
             }
             canvas.translate(-key.x - kbdPaddingLeft, -key.y - kbdPaddingTop);
         }
+
+        if (DEBUG_KEYBOARD_GRID) {
+            Paint p = new Paint();
+            p.setStyle(Paint.Style.STROKE);
+            p.setStrokeWidth(1.0f);
+            p.setColor(0x800000c0);
+            int cw = (mKeyboard.getMinWidth() + mKeyboard.GRID_WIDTH - 1) / mKeyboard.GRID_WIDTH;
+            int ch = (mKeyboard.getHeight() + mKeyboard.GRID_HEIGHT - 1) / mKeyboard.GRID_HEIGHT;
+            for (int i = 0; i <= mKeyboard.GRID_WIDTH; i++)
+                canvas.drawLine(i * cw, 0, i * cw, ch * mKeyboard.GRID_HEIGHT, p);
+            for (int i = 0; i <= mKeyboard.GRID_HEIGHT; i++)
+                canvas.drawLine(0, i * ch, cw * mKeyboard.GRID_WIDTH, i * ch, p);
+        }
+
         mInvalidatedKey = null;
         // Overlay a dark rectangle to dim the keyboard
         if (mMiniKeyboard != null) {
diff --git a/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java b/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
index 0e0c2e7fc..3cc43b99c 100644
--- a/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
+++ b/java/src/com/android/inputmethod/latin/MiniKeyboardKeyDetector.java
@@ -41,17 +41,18 @@ class MiniKeyboardKeyDetector extends KeyDetector {
         final Key[] keys = getKeys();
         final int touchX = getTouchX(x);
         final int touchY = getTouchY(y);
+
         int closestKeyIndex = BaseKeyboardView.NOT_A_KEY;
         int closestKeyDist = (y < 0) ? mSlideAllowanceSquareTop : mSlideAllowanceSquare;
         final int keyCount = keys.length;
-        for (int i = 0; i < keyCount; i++) {
-            final Key key = keys[i];
-            int dist = key.squaredDistanceFrom(touchX, touchY);
+        for (int index = 0; index < keyCount; index++) {
+            final int dist = keys[index].squaredDistanceToEdge(touchX, touchY);
             if (dist < closestKeyDist) {
-                closestKeyIndex = i;
+                closestKeyIndex = index;
                 closestKeyDist = dist;
             }
         }
+
         if (allKeys != null && closestKeyIndex != BaseKeyboardView.NOT_A_KEY)
             allKeys[0] = keys[closestKeyIndex].codes[0];
         return closestKeyIndex;
diff --git a/java/src/com/android/inputmethod/latin/PointerTracker.java b/java/src/com/android/inputmethod/latin/PointerTracker.java
index 78e00720a..2194ed91b 100644
--- a/java/src/com/android/inputmethod/latin/PointerTracker.java
+++ b/java/src/com/android/inputmethod/latin/PointerTracker.java
@@ -396,24 +396,12 @@ public class PointerTracker {
         if (newKey == curKey) {
             return true;
         } else if (isValidKeyIndex(curKey)) {
-            return getSquareDistanceToKeyEdge(x, y, mKeys[curKey]) < mKeyHysteresisDistanceSquared;
+            return mKeys[curKey].squaredDistanceToEdge(x, y) < mKeyHysteresisDistanceSquared;
         } else {
             return false;
         }
     }
 
-    private static int getSquareDistanceToKeyEdge(int x, int y, Key key) {
-        final int left = key.x;
-        final int right = key.x + key.width;
-        final int top = key.y;
-        final int bottom = key.y + key.height;
-        final int edgeX = x < left ? left : (x > right ? right : x);
-        final int edgeY = y < top ? top : (y > bottom ? bottom : y);
-        final int dx = x - edgeX;
-        final int dy = y - edgeY;
-        return dx * dx + dy * dy;
-    }
-
     private void showKeyPreviewAndUpdateKeyGraphics(int keyIndex) {
         updateKeyGraphics(keyIndex);
         // The modifier key, such as shift key, should not be shown as preview when multi-touch is
diff --git a/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java b/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
index 01122ebb7..35bdc6728 100644
--- a/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
+++ b/java/src/com/android/inputmethod/latin/ProximityKeyDetector.java
@@ -36,41 +36,34 @@ class ProximityKeyDetector extends KeyDetector {
         final Key[] keys = getKeys();
         final int touchX = getTouchX(x);
         final int touchY = getTouchY(y);
+
         int primaryIndex = BaseKeyboardView.NOT_A_KEY;
-        int closestKey = BaseKeyboardView.NOT_A_KEY;
+        int closestKeyIndex = BaseKeyboardView.NOT_A_KEY;
         int closestKeyDist = mProximityThresholdSquare + 1;
-        int[] distances = mDistances;
+        final int[] distances = mDistances;
         Arrays.fill(distances, Integer.MAX_VALUE);
-        int [] nearestKeyIndices = mKeyboard.getNearestKeys(touchX, touchY);
-        final int keyCount = nearestKeyIndices.length;
-        for (int i = 0; i < keyCount; i++) {
-            final Key key = keys[nearestKeyIndices[i]];
-            int dist = 0;
-            boolean isInside = key.isInside(touchX, touchY);
-            if (isInside) {
-                primaryIndex = nearestKeyIndices[i];
-            }
-
-            if (((mProximityCorrectOn
-                    && (dist = key.squaredDistanceFrom(touchX, touchY)) < mProximityThresholdSquare)
-                    || isInside)
-                    && key.codes[0] > 32) {
-                // Find insertion point
-                final int nCodes = key.codes.length;
+        for (final int index : mKeyboard.getNearestKeys(touchX, touchY)) {
+            final Key key = keys[index];
+            final boolean isInside = key.isInside(touchX, touchY);
+            if (isInside)
+                primaryIndex = index;
+            final int dist = key.squaredDistanceToEdge(touchX, touchY);
+            if (isInside || (mProximityCorrectOn && dist < mProximityThresholdSquare)) {
                 if (dist < closestKeyDist) {
                     closestKeyDist = dist;
-                    closestKey = nearestKeyIndices[i];
+                    closestKeyIndex = index;
                 }
 
                 if (allKeys == null) continue;
-
+                final int nCodes = key.codes.length;
+                // Find insertion point
                 for (int j = 0; j < distances.length; j++) {
                     if (distances[j] > dist) {
                         // Make space for nCodes codes
                         System.arraycopy(distances, j, distances, j + nCodes,
-                                distances.length - j - nCodes);
+                                distances.length - (j + nCodes));
                         System.arraycopy(allKeys, j, allKeys, j + nCodes,
-                                allKeys.length - j - nCodes);
+                                allKeys.length - (j + nCodes));
                         System.arraycopy(key.codes, 0, allKeys, j, nCodes);
                         Arrays.fill(distances, j, j + nCodes, dist);
                         break;
@@ -78,9 +71,7 @@ class ProximityKeyDetector extends KeyDetector {
                 }
             }
         }
-        if (primaryIndex == BaseKeyboardView.NOT_A_KEY) {
-            primaryIndex = closestKey;
-        }
-        return primaryIndex;
+
+        return primaryIndex == BaseKeyboardView.NOT_A_KEY ? closestKeyIndex : primaryIndex;
     }
 }