q_recognizer/point_cloud_recognizer_plus.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, gesture::Gesture, point::Point};
67use std::f32;
68
69/// Main function of the $P+ recognizer.
70/// Classifies a candidate gesture against a set of training samples.
71/// Returns the class of the closest neighbor in the template set.
72pub fn classify(candidate: &Gesture, training_set: &[Gesture]) -> String {
73 let mut min_distance = f32::MAX;
74 let mut gesture_class = String::new();
75 for template in training_set {
76 let dist = greedy_cloud_match(&candidate.points, &template.points);
77 if dist < min_distance {
78 min_distance = dist;
79 gesture_class = template.name.clone();
80 }
81 }
82 gesture_class
83}
84
85/// Implements greedy search for a minimum-distance matching between two point clouds
86/// using local shape descriptors (theta turning angles).
87fn greedy_cloud_match(points1: &[Point], points2: &[Point]) -> f32 {
88 // should be pre-processed in the Gesture class
89 let theta1 = compute_local_shape_descriptors(points1);
90 // should be pre-processed in the Gesture class
91 let theta2 = compute_local_shape_descriptors(points2);
92 let d1 = cloud_distance(points1, &theta1, points2, &theta2);
93 let d2 = cloud_distance(points2, &theta2, points1, &theta1);
94 d1.min(d2)
95}
96
97/// Computes the distance between two point clouds
98/// using local shape descriptors (theta turning angles).
99fn cloud_distance(
100 points1: &[Point],
101 theta1: &[f32],
102 points2: &[Point],
103 theta2: &[f32]
104) -> f32 {
105 let mut matched = vec![false; points2.len()];
106 let mut sum = 0.0;
107 let mut index = 0;
108
109 for i in 0..points1.len() {
110 sum += get_closest_point_from_cloud(&points1[i], theta1[i], points2, theta2, &mut index);
111 matched[index] = true;
112 }
113 for i in 0..points2.len() {
114 if !matched[i] {
115 sum += get_closest_point_from_cloud(&points2[i], theta2[i], points1, theta1, &mut index);
116 }
117 }
118 sum
119}
120
121/// Searches for the point from point-cloud cloud that is closest to point p.
122fn get_closest_point_from_cloud(
123 p: &Point,
124 theta: f32,
125 cloud: &[Point],
126 theta_cloud: &[f32],
127 index_min: &mut usize
128) -> f32 {
129 let mut min = f32::MAX;
130 *index_min = 0;
131 for i in 0..cloud.len() {
132 let dx = geometry::sqr_euclidean_distance(p, &cloud[i]);
133 let dtheta = theta - theta_cloud[i];
134 let dist = (dx + dtheta * dtheta).sqrt();
135 if dist < min {
136 min = dist;
137 *index_min = i;
138 }
139 }
140 min
141}
142
143/// Computes local shape descriptors (theta turning angles) at each point on the gesture path.
144pub fn compute_local_shape_descriptors(points: &[Point]) -> Vec<f32> {
145 let n = points.len();
146 let mut theta = vec![0.0; n];
147 for i in 1..(n - 1) {
148 theta[i] = short_angle(&points[i - 1], &points[i], &points[i + 1]) / std::f32::consts::PI;
149 }
150 theta
151}
152
153/// Computes the smallest turning angle between vectors (a,b) and (b,c) in radians in the interval [0..PI].
154fn short_angle(a: &Point, b: &Point, c: &Point) -> f32 {
155 let length_ab = geometry::euclidean_distance(a, b);
156 let length_bc = geometry::euclidean_distance(b, c);
157 if (length_ab * length_bc).abs() <= f32::EPSILON {
158 return 0.0;
159 }
160 // compute cosine of the angle between vectors (a,b) and (b,c)
161 let dot = (b.x - a.x) * (c.x - b.x) + (b.y - a.y) * (c.y - b.y);
162 let cos_angle = dot / (length_ab * length_bc);
163
164 // deal with special cases near limits of the [-1,1] interval
165 if cos_angle <= -1.0 {
166 std::f32::consts::PI
167 } else if cos_angle >= 1.0 {
168 0.0
169 } else {
170 // return the angle between vectors (a,b) and (b,c) in the interval [0,PI]
171 cos_angle.acos()
172 }
173}