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
20 import java.util.ArrayList;
21 import java.util.Collection;
22 import java.util.List;
23
24 /**
25 * Finds k-nearest radio source fingerprints based on their signal Euclidean distances
26 * (not their actual location) where mean values are removed to account for possible
27 * biases when measuring from different devices.
28 * Typically, this class should be preferred over {@link RadioSourceKNearestFinder}.
29 *
30 * @param <P> a {@link Point} type.
31 * @param <S> a {@link RadioSource type}.
32 */
33 public class RadioSourceNoMeanKNearestFinder<P extends Point<?>, S extends RadioSource> {
34
35 /**
36 * Collection of fingerprints to match against.
37 */
38 private final Collection<? extends RssiFingerprintLocated<S, RssiReading<S>, P>> mFingerprints;
39
40 /**
41 * Constructor.
42 *
43 * @param fingerprints collection of fingerprints to match against.
44 * @throws IllegalArgumentException if collection of fingerprints is null.
45 */
46 public RadioSourceNoMeanKNearestFinder(
47 final Collection<? extends RssiFingerprintLocated<S, RssiReading<S>, P>> fingerprints) {
48 if (fingerprints == null) {
49 throw new IllegalArgumentException();
50 }
51 mFingerprints = fingerprints;
52 }
53
54 /**
55 * Finds nearest fingerprint to provided one, in terms of signal Euclidean distances
56 * (with removed signal means), within the collection of provided fingerprints.
57 *
58 * @param fingerprint fingerprint to find the nearest to.
59 * @return nearest fingerprint or null if none could be found.
60 */
61 public RssiFingerprintLocated<S, RssiReading<S>, P> findNearestTo(
62 final RssiFingerprint<S, RssiReading<S>> fingerprint) {
63 return findNearestTo(fingerprint, mFingerprints);
64 }
65
66 /**
67 * Finds k-nearest fingerprints to provided one, in terms of signal Euclidean distances
68 * (with removed signal means), within the collection of provided fingerprints.
69 *
70 * @param fingerprint fingerprint to find the k-nearest ones to.
71 * @param k number of nearest fingerprints to find.
72 * @return nearest fingerprints ordered from closest to farthest or an empty list if none could be found.
73 * @throws IllegalArgumentException if either fingerprint is null or k is less than 1.
74 */
75 public List<RssiFingerprintLocated<S, RssiReading<S>, P>> findKNearestTo(
76 final RssiFingerprint<S, RssiReading<S>> fingerprint, final int k) {
77 return findKNearestTo(fingerprint, mFingerprints, k);
78 }
79
80 /**
81 * Finds k-nearest fingerprints to provided one, in terms of signal Euclidean distances
82 * (with removed signal means), within the collection of provided fingerprints.
83 *
84 * @param fingerprint fingerprint to find the k-nearest ones to.
85 * @param k number of nearest fingerprints to find.
86 * @param nearestFingerprints list where found nearest fingerprints will be stored ordered from closest to farthest
87 * or an empty list if none could be found.
88 * @param nearestSqrDistances list where squared signal Euclidean distances corresponding to found fingerprints will
89 * be stored or an empty list if no fingerprint is found.
90 * @throws IllegalArgumentException if any parameter is null or k is less than 1.
91 */
92 public void findKNearestTo(
93 final RssiFingerprint<S, RssiReading<S>> fingerprint, final int k,
94 final List<RssiFingerprintLocated<S, RssiReading<S>, P>> nearestFingerprints,
95 final List<Double> nearestSqrDistances) {
96 findKNearestTo(fingerprint, mFingerprints, k, nearestFingerprints, nearestSqrDistances);
97 }
98
99 /**
100 * Gets collection of fingerprints to match against.
101 *
102 * @return collection of fingerprints to match against.
103 */
104 public Collection<RssiFingerprintLocated<S, RssiReading<S>, P>> getFingerprints() {
105 //noinspection unchecked
106 return (Collection<RssiFingerprintLocated<S, RssiReading<S>,P>>) mFingerprints;
107 }
108
109 /**
110 * Finds nearest fingerprint to provided one, in terms of signal Euclidean distances
111 * (with removed signal means), within the collection of provided fingerprints.
112 *
113 * @param fingerprint fingerprint to find the nearest to.
114 * @param fingerprints collection of fingerprints to make the search for the nearest one.
115 * @param <P> a {@link Point} type.
116 * @param <S> a {@link RadioSource} type.
117 * @return nearest fingerprint or null if none could be found.
118 * @throws IllegalArgumentException if either fingerprint or collection of fingerprints is null.
119 */
120 @SuppressWarnings("Duplicates")
121 public static <P extends Point<?>, S extends RadioSource> RssiFingerprintLocated<S, RssiReading<S>, P>
122 findNearestTo(final RssiFingerprint<S, RssiReading<S>> fingerprint,
123 final Collection<? extends RssiFingerprintLocated<S, RssiReading<S>, P>> fingerprints) {
124 if (fingerprint == null || fingerprints == null) {
125 throw new IllegalArgumentException();
126 }
127
128 var bestSqrDist = Double.MAX_VALUE;
129 RssiFingerprintLocated<S, RssiReading<S>, P> result = null;
130 for (final var f : fingerprints) {
131 var sqrDist = f.noMeanSqrDistanceTo(fingerprint);
132 if (sqrDist < bestSqrDist) {
133 bestSqrDist = sqrDist;
134 result = f;
135 }
136 }
137
138 return result;
139 }
140
141 /**
142 * Finds k-nearest fingerprints to provided one, in terms of signal Euclidean distances, within the collection
143 * of provided fingerprints.
144 *
145 * @param fingerprint fingerprint to find the k-nearest ones to.
146 * @param fingerprints collection of fingerprints to make the search for the nearest ones.
147 * @param k number of nearest fingerprints to find.
148 * @param <P> a {@link Point} type.
149 * @param <S> a {@link RadioSource} type.
150 * @return nearest fingerprints ordered from closest to farthest or an empty list if none could be found.
151 * @throws IllegalArgumentException if either fingerprint or collection of fingerprints is null, or k is less than
152 * 1.
153 */
154 @SuppressWarnings("DuplicatedCode")
155 public static <P extends Point<?>, S extends RadioSource> List<RssiFingerprintLocated<S, RssiReading<S>, P>>
156 findKNearestTo(final RssiFingerprint<S, RssiReading<S>> fingerprint,
157 final Collection<? extends RssiFingerprintLocated<S, RssiReading<S>, P>> fingerprints,
158 final int k) {
159
160 final var result = new ArrayList<RssiFingerprintLocated<S, RssiReading<S>, P>>();
161 final var nearestSqrDistances = new ArrayList<Double>();
162 findKNearestTo(fingerprint, fingerprints, k, result, nearestSqrDistances);
163
164 return result;
165 }
166
167 /**
168 * Finds k-nearest fingerprints to provided one, in terms of signal Euclidean distances, within the collection
169 * of provided fingerprints.
170 *
171 * @param fingerprint fingerprint to find the k-nearest ones to.
172 * @param fingerprints collection of fingerprints ot make the search for the nearest ones.
173 * @param k number of nearest fingerprints to find.
174 * @param nearestFingerprints list where found nearest fingerprints will be stored ordered from closest to farthest
175 * or an empty list if none could be found.
176 * @param nearestSqrDistances list where squared signal Euclidean distances corresponding to found fingerprints will
177 * be stored or an empty list if no fingerprint is found.
178 * @param <P> a {@link Point} type.
179 * @param <S> a {@link RadioSource} type.
180 * @throws IllegalArgumentException if any parameter is null or k is less than 1.
181 */
182 @SuppressWarnings("Duplicates")
183 public static <P extends Point<?>, S extends RadioSource> void findKNearestTo(
184 final RssiFingerprint<S, RssiReading<S>> fingerprint,
185 final Collection<? extends RssiFingerprintLocated<S, RssiReading<S>, P>> fingerprints, final int k,
186 final List<RssiFingerprintLocated<S, RssiReading<S>, P>> nearestFingerprints,
187 final List<Double> nearestSqrDistances) {
188
189 if (fingerprint == null || fingerprints == null || k < 1 || nearestFingerprints == null
190 || nearestSqrDistances == null) {
191 throw new IllegalArgumentException();
192 }
193
194 nearestSqrDistances.clear();
195 nearestFingerprints.clear();
196
197 var maxSqrDist = Double.MAX_VALUE;
198 for (final var f : fingerprints) {
199 final var sqrDist = f.noMeanSqrDistanceTo(fingerprint);
200 if (sqrDist < maxSqrDist || nearestSqrDistances.size() < k) {
201
202 // find insertion point
203 var pos = -1;
204 var i = 0;
205 for (final var sd : nearestSqrDistances) {
206 if (sqrDist < sd) {
207 // insertion point found
208 pos = i;
209 break;
210 }
211 i++;
212 }
213
214 if (pos >= 0) {
215 nearestSqrDistances.add(pos, sqrDist);
216 nearestFingerprints.add(pos, f);
217 } else {
218 nearestSqrDistances.add(sqrDist);
219 nearestFingerprints.add(f);
220 }
221
222 // remove results exceeding required number of k neighbours to be found
223 if (nearestFingerprints.size() > k) {
224 nearestSqrDistances.remove(k);
225 nearestFingerprints.remove(k);
226 }
227
228 // update maxSqrDist to the largest squared distance value contained in result list distances
229 maxSqrDist = nearestSqrDistances.get(nearestSqrDistances.size() - 1);
230 }
231 }
232 }
233 }