56 |
int currentIndex = items.size()/2; |
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)); |
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 |
|
|
60 |
|
|
61 |
|
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
62 |
|
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
63 |
|
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
64 |
|
KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left; |
65 |
|
KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf |
66 |
|
if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
67 |
|
best = currentNode; // Set best as required |
68 |
|
} |
69 |
|
if ( other != null ) { |
70 |
|
if ( currentNode.location.axisSquaredDistance(search, depth % 3) < best.location.squaredDistance(search) ) { |
71 |
|
KDNode<T> possibleBest = findNearest( other, search, depth + 1 ); |
72 |
|
if ( possibleBest.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
73 |
|
best = possibleBest; |
74 |
|
} |
75 |
|
} |
76 |
|
} |
77 |
|
return best; // Work back up |
78 |
|
} |
79 |
|
|
80 |
|
/* backup af udgave med isNodeCompatible |
81 |
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
82 |
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
83 |
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
95 |
} |
} |
96 |
} |
} |
97 |
return best; // Work back up |
return best; // Work back up |
98 |
} |
}*/ |
99 |
} |
} |