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 |
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
61 |
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
62 |
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
63 |
KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left; |
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 |
KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf |
65 |
if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) ) { |
66 |
best = currentNode; // Set best as required |
best = currentNode; // Set best as required |
67 |
} |
} |
68 |
if ( other != null ) { |
if ( other != null ) { |
75 |
} |
} |
76 |
return best; // Work back up |
return best; // Work back up |
77 |
} |
} |
|
|
|
|
/* backup af udgave med isNodeCompatible |
|
|
private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) { |
|
|
int direction = search.getComparator(depth % 3).compare( search, currentNode.location ); |
|
|
KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right; |
|
|
KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left; |
|
|
KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf |
|
|
if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) && search.isNodeCompatible(currentNode.location) ) { |
|
|
best = currentNode; // Set best as required |
|
|
} |
|
|
if ( other != null ) { |
|
|
if ( currentNode.location.axisSquaredDistance(search, depth % 3) < best.location.squaredDistance(search) ) { |
|
|
KDNode<T> possibleBest = findNearest( other, search, depth + 1 ); |
|
|
if ( possibleBest.location.squaredDistance(search) < best.location.squaredDistance(search) && search.isNodeCompatible(possibleBest.location)) { |
|
|
best = possibleBest; |
|
|
} |
|
|
} |
|
|
} |
|
|
return best; // Work back up |
|
|
}*/ |
|
78 |
} |
} |