1 /*
2 * Copyright (C) 2018 Alberto Irurueta Carro (alberto@irurueta.com)
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 package com.irurueta.navigation.indoor;
17
18 import com.irurueta.geometry.Point;
19 import com.irurueta.navigation.LockedException;
20 import com.irurueta.navigation.NotReadyException;
21
22 /**
23 * Estimates position using Wi-Fi signals indoor and the Weighted k-Nearest
24 * Neighbours (WkNN) algorithm.
25 * WkNN algorithm is based on <a href="https://github.com/ajnas/WiFiPS">https://github.com/ajnas/WiFiPS</a>.
26 *
27 * @param <P> a {@link Point} type.
28 */
29 public abstract class WeightedKNearestNeighboursPositionSolver<P extends Point<?>> {
30
31 /**
32 * Default minimum allowed distance between received Wi-Fi fingerprints.
33 */
34 public static final double DEFAULT_EPSILON = 1e-7;
35
36 /**
37 * Minimum required number of fingerprints and their distances.
38 * If only 1 fingerprint is used, this algorithm will return provided fingerprint
39 * position, however, some accuracy might be lost due to numerical computations.
40 * For that reason, when only one fingerprint is provided, this algorithm will
41 * simply return the fingerprint position.
42 */
43 public static final int MIN_FINGERPRINTS = 1;
44
45 /**
46 * Known located Wi-Fi fingerprints.
47 */
48 protected RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] fingerprints;
49
50 /**
51 * Euclidean distances between WiFi signal fingerprints (expressed in dB's).
52 */
53 protected double[] distances;
54
55 /**
56 * Listener to be notified of events raised by this instance.
57 */
58 protected WeightedKNearestNeighboursPositionSolverListener<P> listener;
59
60 /**
61 * Estimated inhomogeneous position coordinates.
62 */
63 protected double[] estimatedPositionCoordinates;
64
65 /**
66 * Indicates if this instance is locked because indoor is being
67 * estimated.
68 */
69 protected boolean locked;
70
71 /**
72 * Minimum allowed distance between received Wi-Fi signal strengths.
73 */
74 private double epsilon = DEFAULT_EPSILON;
75
76 /**
77 * Constructor.
78 */
79 protected WeightedKNearestNeighboursPositionSolver() {
80 }
81
82 /**
83 * Constructor.
84 * Sets known located Wi-Fi fingerprints and Euclidean distances between Wi-Fi
85 * signal fingerprints.
86 *
87 * @param fingerprints known located Wi-Fi fingerprints.
88 * @param distances Euclidean distances between Wi-Fi signal fingerprints
89 * (expressed in dB's).
90 * @throws IllegalArgumentException if either fingerprints or distances are null,
91 * don't have the same length or their length is smaller than 1.
92 */
93 protected WeightedKNearestNeighboursPositionSolver(
94 final RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] fingerprints,
95 final double[] distances) {
96 internalSetFingerprintsAndDistances(fingerprints, distances);
97 }
98
99 /**
100 * Constructor.
101 *
102 * @param listener listener to be notified of events raised by this instance.
103 */
104 protected WeightedKNearestNeighboursPositionSolver(
105 final WeightedKNearestNeighboursPositionSolverListener<P> listener) {
106 this.listener = listener;
107 }
108
109 /**
110 * Constructor.
111 * Sets known located Wi-Fi fingerprints and Euclidean distances between Wi-Fi
112 * signal fingerprints.
113 *
114 * @param fingerprints known located Wi-Fi fingerprints.
115 * @param distances Euclidean distances between Wi-Fi signal fingerprints
116 * (expressed in dB's).
117 * @param listener listener to be notified of events raised by this instance.
118 * @throws IllegalArgumentException if either fingerprints or distances are null,
119 * don't have the same length or their length is smaller than 1.
120 */
121 protected WeightedKNearestNeighboursPositionSolver(
122 final RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] fingerprints,
123 final double[] distances, final WeightedKNearestNeighboursPositionSolverListener<P> listener) {
124 this(fingerprints, distances);
125 this.listener = listener;
126 }
127
128 /**
129 * Gets listener to be notified of events raised by this instance.
130 *
131 * @return listener to be notified of events raised by this instance.
132 */
133 public WeightedKNearestNeighboursPositionSolverListener<P> getListener() {
134 return listener;
135 }
136
137 /**
138 * Sets listener to be notified of events raised by this instance.
139 *
140 * @param listener listener to be notified of events raised by this instance.
141 * @throws LockedException if instance is busy solving the position.
142 */
143 public void setListener(final WeightedKNearestNeighboursPositionSolverListener<P> listener) throws LockedException {
144 if (isLocked()) {
145 throw new LockedException();
146 }
147 this.listener = listener;
148 }
149
150 /**
151 * Gets known located Wi-Fi fingerprints.
152 *
153 * @return known located Wi-Fi fingerprints.
154 */
155 public RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] getFingerprints() {
156 return fingerprints;
157 }
158
159 /**
160 * Gets euclidean distances between WiFi signal fingerprints
161 * (expressed in dB's).
162 *
163 * @return euclidean distances between WiFi signal fingerprints.
164 */
165 public double[] getDistances() {
166 return distances;
167 }
168
169 /**
170 * Indicates whether solver is ready to find a solution.
171 *
172 * @return true if solver is ready, false otherwise.
173 */
174 public boolean isReady() {
175 return fingerprints != null && distances != null && fingerprints.length >= MIN_FINGERPRINTS;
176 }
177
178 /**
179 * Returns boolean indicating if estimator is locked because estimation is under
180 * progress.
181 *
182 * @return true if solver is locked, false otherwise.
183 */
184 public boolean isLocked() {
185 return locked;
186 }
187
188 /**
189 * Sets known located Wi-Fi fingerprints and Euclidean distances between Wi-Fi
190 * signal fingerprints.
191 *
192 * @param fingerprints known located Wi-Fi fingerprints.
193 * @param distances Euclidean distances between Wi-Fi signal fingerprints
194 * (expressed in dB's).
195 * @throws IllegalArgumentException if either fingerprints or distances are null,
196 * don't have the same length or their length is smaller than 1.
197 * @throws LockedException if instance is busy solving the position.
198 */
199 public void setFingerprintsAndDistances(
200 final RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] fingerprints,
201 final double[] distances) throws LockedException {
202 if (isLocked()) {
203 throw new LockedException();
204 }
205 internalSetFingerprintsAndDistances(fingerprints, distances);
206 }
207
208 /**
209 * Gets minimum allowed distance between Wi-Fi signal fingerprints.
210 *
211 * @return minimum allowed distance between Wi-Fi signal fingerprints.
212 */
213 public double getEpsilon() {
214 return epsilon;
215 }
216
217 /**
218 * Sets minimum allowed distance between WiFi signal fingerprints.
219 *
220 * @param epsilon minimum allowed distance between WiFi signal fingerprints.
221 * strengths.
222 * @throws IllegalArgumentException if provided value is zero or negative.
223 * @throws LockedException if instance is busy solving the indoor problem.
224 */
225 public void setEpsilon(final double epsilon) throws LockedException {
226 if (isLocked()) {
227 throw new LockedException();
228 }
229
230 if (epsilon <= 0.0) {
231 throw new IllegalArgumentException();
232 }
233
234 this.epsilon = epsilon;
235 }
236
237 /**
238 * Estimates position.
239 *
240 * @throws NotReadyException if solver is not ready.
241 * @throws LockedException if instance is busy solving position.
242 */
243 public void solve() throws NotReadyException, LockedException {
244 if (!isReady()) {
245 throw new NotReadyException();
246 }
247 if (isLocked()) {
248 throw new LockedException();
249 }
250
251 try {
252 locked = true;
253
254 if (listener != null) {
255 listener.onSolveStart(this);
256 }
257
258 final var num = fingerprints.length;
259 final var dims = getNumberOfDimensions();
260 if (num == 1) {
261 // only one fingerprint available
262 estimatedPositionCoordinates = new double[dims];
263 for (var i = 0; i < dims; i++) {
264 final var p = fingerprints[0].getPosition();
265 estimatedPositionCoordinates[i] = p.getInhomogeneousCoordinate(i);
266 }
267 } else {
268 // multiple fingerprints available
269 final var coords = new double[dims];
270 var sum = 0.0;
271 double w;
272 for (var i = 0; i < num; i++) {
273 // weighted average and weight summation
274 w = 1.0 / distances[i];
275 sum += w;
276
277 final var p = fingerprints[i].getPosition();
278 for (var j = 0; j < dims; j++) {
279 coords[j] += w * p.getInhomogeneousCoordinate(j);
280 }
281 }
282
283 // normalize by weight summation
284 if (sum != 0.0) {
285 for (var j = 0; j < dims; j++) {
286 coords[j] /= sum;
287 }
288 }
289
290 estimatedPositionCoordinates = coords;
291 }
292
293 if (listener != null) {
294 listener.onSolveEnd(this);
295 }
296 } finally {
297 locked = false;
298 }
299 }
300
301 /**
302 * Gets estimated inhomogeneous position coordinates.
303 *
304 * @return estimated inhomogeneous position coordinates.
305 */
306 public double[] getEstimatedPositionCoordinates() {
307 return estimatedPositionCoordinates;
308 }
309
310 /**
311 * Gets estimated position and stores result into provided instance.
312 *
313 * @param estimatedPosition instance where estimated position will be stored.
314 */
315 public void getEstimatedPosition(final P estimatedPosition) {
316 if (estimatedPositionCoordinates != null) {
317 for (var i = 0; i < estimatedPositionCoordinates.length; i++) {
318 estimatedPosition.setInhomogeneousCoordinate(i, estimatedPositionCoordinates[i]);
319 }
320 }
321 }
322
323 /**
324 * Gets estimated position.
325 *
326 * @return estimated position.
327 */
328 public abstract P getEstimatedPosition();
329
330 /**
331 * Gets number of dimensions of location points.
332 *
333 * @return number of dimensions of location points.
334 */
335 public abstract int getNumberOfDimensions();
336
337 /**
338 * Sets known located Wi-Fi fingerprints and Euclidean distances between Wi-Fi
339 * signal fingerprints.
340 *
341 * @param fingerprints known located Wi-Fi fingerprints.
342 * @param distances Euclidean distances between Wi-Fi signal fingerprints
343 * (expressed in dB's).
344 * @throws IllegalArgumentException if either fingerprints or distances are null,
345 * don't have the same length or their length is smaller than 1.
346 */
347 protected void internalSetFingerprintsAndDistances(
348 final RssiFingerprintLocated<WifiAccessPoint, RssiReading<WifiAccessPoint>, P>[] fingerprints,
349 final double[] distances) {
350 if (fingerprints == null || distances == null) {
351 throw new IllegalArgumentException();
352 }
353
354 if (fingerprints.length < MIN_FINGERPRINTS) {
355 throw new IllegalArgumentException();
356 }
357
358 if (fingerprints.length != distances.length) {
359 throw new IllegalArgumentException();
360 }
361
362 this.fingerprints = fingerprints;
363 this.distances = distances;
364
365 // fix distances if needed
366 for (var i = 0; i < this.distances.length; i++) {
367 if (this.distances[i] < epsilon) {
368 this.distances[i] = epsilon;
369 }
370 }
371 }
372 }