1 |
torben |
2585 |
/* |
2 |
|
|
The MIT License (MIT) |
3 |
|
|
[OSI Approved License] |
4 |
|
|
The MIT License (MIT) |
5 |
|
|
|
6 |
|
|
Copyright (c) 2014 Daniel Glasson |
7 |
|
|
|
8 |
|
|
Permission is hereby granted, free of charge, to any person obtaining a copy |
9 |
|
|
of this software and associated documentation files (the "Software"), to deal |
10 |
|
|
in the Software without restriction, including without limitation the rights |
11 |
|
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
12 |
|
|
copies of the Software, and to permit persons to whom the Software is |
13 |
|
|
furnished to do so, subject to the following conditions: |
14 |
|
|
|
15 |
|
|
The above copyright notice and this permission notice shall be included in |
16 |
|
|
all copies or substantial portions of the Software. |
17 |
|
|
|
18 |
|
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
19 |
|
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
20 |
|
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
21 |
|
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
22 |
|
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
23 |
|
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
24 |
|
|
THE SOFTWARE. |
25 |
|
|
*/ |
26 |
|
|
|
27 |
|
|
package geocode.kdtree; |
28 |
|
|
|
29 |
|
|
import java.util.ArrayList; |
30 |
|
|
import java.util.Collections; |
31 |
|
|
import java.util.List; |
32 |
|
|
|
33 |
|
|
/** |
34 |
|
|
* |
35 |
|
|
* @author Daniel Glasson |
36 |
|
|
* A KD-Tree implementation to quickly find nearest points |
37 |
|
|
* Currently implements createKDTree and findNearest as that's all that's required here |
38 |
|
|
*/ |
39 |
|
|
public class KDTree<T extends KDNodeComparator<T>> { |
40 |
|
|
private KDNode<T> root; |
41 |
|
|
|
42 |
|
|
public KDTree( List<T> items ) { |
43 |
|
|
root = createKDTree(items, 0); |
44 |
|
|
} |
45 |
|
|
|
46 |
|
|
public T findNearest( T search ) { |
47 |
|
|
return findNearest(root, search, 0).location; |
48 |
|
|
} |
49 |
|
|
|
50 |
|
|
// Only ever goes to log2(items.length) depth so lack of tail recursion is a non-issue |
51 |
|
|
private KDNode<T> createKDTree( List<T> items, int depth ) { |
52 |
|
|
if ( items.isEmpty() ) { |
53 |
|
|
return null; |
54 |
|
|
} |
55 |
|
|
Collections.sort(items, items.get(0).getComparator(depth % 3)); |
56 |
|
|
int currentIndex = items.size()/2; |
57 |
|
|
return new KDNode<T>(createKDTree(new ArrayList<T>(items.subList(0, currentIndex)), depth+1), createKDTree(new ArrayList<T>(items.subList(currentIndex + 1, items.size())), depth+1), items.get(currentIndex)); |
58 |
|
|
} |
59 |
torben |
2603 |
|
60 |
torben |
2597 |
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
61 |
|
|
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
62 |
|
|
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
63 |
|
|
KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left; |
64 |
|
|
KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf |
65 |
torben |
2603 |
if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
66 |
torben |
2597 |
best = currentNode; // Set best as required |
67 |
|
|
} |
68 |
|
|
if ( other != null ) { |
69 |
|
|
if ( currentNode.location.axisSquaredDistance(search, depth % 3) < best.location.squaredDistance(search) ) { |
70 |
|
|
KDNode<T> possibleBest = findNearest( other, search, depth + 1 ); |
71 |
|
|
if ( possibleBest.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
72 |
|
|
best = possibleBest; |
73 |
|
|
} |
74 |
|
|
} |
75 |
|
|
} |
76 |
|
|
return best; // Work back up |
77 |
|
|
} |
78 |
torben |
2585 |
} |