q_recognizer/gesture.rs
1/**
2 * The $P Point-Cloud Recognizer (rust version)
3 *
4 * Translated to rust from the original authors' C# code with an AI tool.
5 * The translated code has been reviewed by Ferran Pujol Camins.
6 *
7 * Original authors:
8 *
9 * Radu-Daniel Vatavu, Ph.D.
10 * University Stefan cel Mare of Suceava
11 * Suceava 720229, Romania
12 * vatavu@eed.usv.ro
13 *
14 * Lisa Anthony, Ph.D.
15 * UMBC
16 * Information Systems Department
17 * 1000 Hilltop Circle
18 * Baltimore, MD 21250
19 * lanthony@umbc.edu
20 *
21 * Jacob O. Wobbrock, Ph.D.
22 * The Information School
23 * University of Washington
24 * Seattle, WA 98195-2840
25 * wobbrock@uw.edu
26 *
27 * The academic publication for the $P recognizer, and what should be
28 * used to cite it, is:
29 *
30 * Vatavu, R.-D., Anthony, L. and Wobbrock, J.O. (2012).
31 * Gestures as point clouds: A $P recognizer for user interface
32 * prototypes. Proceedings of the ACM Int'l Conference on
33 * Multimodal Interfaces (ICMI '12). Santa Monica, California
34 * (October 22-26, 2012). New York: ACM Press, pp. 273-280.
35 *
36 * This software is distributed under the "New BSD License" agreement:
37 *
38 * Copyright (c) 2012, Radu-Daniel Vatavu, Lisa Anthony, and
39 * Jacob O. Wobbrock. All rights reserved.
40 *
41 * Redistribution and use in source and binary forms, with or without
42 * modification, are permitted provided that the following conditions are met:
43 * * Redistributions of source code must retain the above copyright
44 * notice, this list of conditions and the following disclaimer.
45 * * Redistributions in binary form must reproduce the above copyright
46 * notice, this list of conditions and the following disclaimer in the
47 * documentation and/or other materials provided with the distribution.
48 * * Neither the names of the University Stefan cel Mare of Suceava,
49 * University of Washington, nor UMBC, nor the names of its contributors
50 * may be used to endorse or promote products derived from this software
51 * without specific prior written permission.
52 *
53 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
54 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
55 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
56 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Radu-Daniel Vatavu OR Lisa Anthony
57 * OR Jacob O. Wobbrock OR Ferran Pujol Camins BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
58 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
59 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
60 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
61 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
62 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
63 * SUCH DAMAGE.
64**/
65
66use crate::{geometry, point::Point};
67
68/// Default number of points on the gesture path
69const SAMPLING_RESOLUTION: usize = 64;
70/// Each point has two additional x and y integer coordinates in the interval [0..MAX_INT_COORDINATES-1] used to operate the LUT table efficiently (O(1))
71const MAX_INT_COORDINATES: usize = 1024;
72/// The default size of the lookup table is 64 x 64
73pub const LUT_SIZE: usize = 64;
74/// Scale factor to convert between integer x and y coordinates and the size of the LUT
75pub const LUT_SCALE_FACTOR: usize = MAX_INT_COORDINATES / LUT_SIZE;
76
77/// Implements a gesture as a cloud of points (i.e., an unordered set of points).
78/// For $P, gestures are normalized with respect to scale, translated to origin, and resampled into a fixed number of 32 points.
79/// For $Q, a LUT is also computed.
80#[derive(Clone)]
81pub struct Gesture {
82 /// Gesture points (normalized)
83 pub points: Vec<Point>,
84 /// Gesture points (not normalized, as captured from the input device)
85 pub points_raw: Vec<Point>,
86 /// Gesture class
87 pub name: String,
88 /// Look-up table
89 pub lut: Option<Vec<Vec<usize>>>,
90}
91
92impl Gesture {
93 /// Constructs a new gesture from a list of points and a name
94 pub fn new(pts: Vec<Point>, name: &str) -> Self {
95 let points_raw = pts.iter().cloned().collect();
96 let mut g = Self {
97 points: Vec::new(),
98 points_raw,
99 name: name.into(),
100 lut: None,
101 };
102 g.normalize(true);
103 g
104 }
105
106 /// Normalizes the gesture path.
107 /// The $Q recognizer requires an extra normalization step, the computation of the LUT,
108 /// which can be enabled with the computeLUT parameter.
109 pub fn normalize(&mut self, compute_lut: bool) {
110 // standard $-family processing: resample, scale, and translate to origin
111 self.points = Self::resample(&self.points_raw, SAMPLING_RESOLUTION);
112 self.points = Self::scale(&self.points);
113 let c = Self::centroid(&self.points);
114 self.points = Self::translate_to(&self.points, &c);
115
116 // constructs a lookup table for fast lower bounding (used by $Q)
117 if compute_lut {
118 self.transform_coordinates_to_integers();
119 self.construct_lut();
120 }
121 }
122
123 /// Performs scale normalization with shape preservation into [0..1]x[0..1]
124 fn scale(points: &[Point]) -> Vec<Point> {
125 let (mut minx, mut miny) = (f32::MAX, f32::MAX);
126 let (mut maxx, mut maxy) = (f32::MIN, f32::MIN);
127 for p in points {
128 if p.x < minx { minx = p.x; }
129 if p.y < miny { miny = p.y; }
130 if p.x > maxx { maxx = p.x; }
131 if p.y > maxy { maxy = p.y; }
132 }
133 let scale = (maxx - minx).max(maxy - miny);
134 points.iter().map(|p| {
135 Point::new((p.x - minx) / scale, (p.y - miny) / scale, p.stroke_id)
136 }).collect()
137 }
138
139 /// Translates the array of points by p
140 fn translate_to(points: &[Point], p: &Point) -> Vec<Point> {
141 points.iter().map(|point| {
142 Point::new(point.x - p.x, point.y - p.y, p.stroke_id)
143 }).collect()
144 }
145
146 /// Computes the centroid for an array of points
147 fn centroid(points: &[Point]) -> Point {
148 let mut cx = 0.0;
149 let mut cy = 0.0;
150 for p in points {
151 cx += p.x;
152 cy += p.y;
153 }
154 let n = points.len() as f32;
155 Point::new(cx / n, cy / n, 0)
156 }
157
158 /// Resamples the array of points into n equally-distanced points
159 fn resample(points: &[Point], n: usize) -> Vec<Point> {
160 let mut new_points = Vec::with_capacity(n);
161 new_points.push(Point::new(points[0].x, points[0].y, points[0].stroke_id));
162
163 let interval = Self::path_length(points) / (n as f32 - 1.0);
164 let mut d = 0.0;
165
166 for i in 1..points.len() {
167 if points[i].stroke_id == points[i - 1].stroke_id {
168 let mut dist = geometry::euclidean_distance(&points[i - 1], &points[i]);
169 if (d + dist) >= interval {
170 let mut first_point = &points[i - 1];
171 while (d + dist) >= interval {
172 let t = if dist != 0. {
173 ((interval - d) / dist).clamp(0.0, 1.0)
174 } else {
175 0.5
176 };
177 let nx = (1.0 - t) * first_point.x + t * points[i].x;
178 let ny = (1.0 - t) * first_point.y + t * points[i].y;
179 new_points.push(Point::new(nx, ny, points[i].stroke_id));
180
181 // update partial length
182 dist = d + dist - interval;
183 d = 0.0;
184 first_point = new_points.last().unwrap();
185 }
186 d = dist;
187 } else {
188 d += dist;
189 }
190 }
191 }
192 // sometimes we fall a rounding-error short of adding the last point, so add it if so
193 if new_points.len() == n - 1 {
194 let last = new_points.last().unwrap();
195 new_points.push(Point::new(last.x, last.y, last.stroke_id));
196 }
197 new_points
198 }
199
200 /// Computes the path length for an array of points
201 fn path_length(points: &[Point]) -> f32 {
202 let mut length = 0.0;
203 for i in 1..points.len() {
204 if points[i].stroke_id == points[i - 1].stroke_id {
205 length += geometry::euclidean_distance(&points[i - 1], &points[i]);
206 }
207 }
208 length
209 }
210
211 /// Scales point coordinates to the integer domain [0..MAXINT-1] x [0..MAXINT-1]
212 fn transform_coordinates_to_integers(&mut self) {
213 for p in &mut self.points {
214 p.int_x = ((p.x + 1.0) / 2.0 * (MAX_INT_COORDINATES as f32 - 1.0)) as i32;
215 p.int_y = ((p.y + 1.0) / 2.0 * (MAX_INT_COORDINATES as f32 - 1.0)) as i32;
216 }
217 }
218
219 /// Constructs a Lookup Table that maps grip points to the closest point from the gesture path
220 fn construct_lut(&mut self) {
221 let mut table: Vec<Vec<usize>> = vec![vec![0; LUT_SIZE]; LUT_SIZE];
222 for i in 0..LUT_SIZE {
223 for j in 0..LUT_SIZE {
224 let mut min_dist = i32::MAX;
225 let mut idx_min: usize = 0;
226 for (t, p) in self.points.iter().enumerate() {
227 let row = p.int_y / LUT_SCALE_FACTOR as i32;
228 let col = p.int_x / LUT_SCALE_FACTOR as i32;
229 let dr = row - i as i32;
230 let dc = col - j as i32;
231 let dist = dr * dr + dc * dc;
232 if dist < min_dist {
233 min_dist = dist;
234 idx_min = t;
235 }
236 }
237 table[i][j] = idx_min as usize;
238 }
239 }
240 self.lut = Some(table);
241 }
242}