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