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