19 package org.sleuthkit.autopsy.geolocation;
21 import java.util.ArrayDeque;
22 import java.util.ArrayList;
23 import java.util.Collection;
24 import java.util.Collections;
25 import java.util.Comparator;
26 import java.util.Deque;
27 import java.util.HashSet;
28 import java.util.Iterator;
29 import java.util.List;
31 import java.util.TreeSet;
56 private KdNode
root = null;
63 private static final Comparator<XYZPoint>
X_COMPARATOR =
new Comparator<XYZPoint>() {
68 public int compare(XYZPoint o1, XYZPoint o2) {
69 return Double.compare(o1.x, o2.x);
76 private static final Comparator<XYZPoint>
Y_COMPARATOR =
new Comparator<XYZPoint>() {
81 public int compare(XYZPoint o1, XYZPoint o2) {
82 return Double.compare(o1.y, o2.y);
89 private static final Comparator<XYZPoint>
Z_COMPARATOR =
new Comparator<XYZPoint>() {
94 public int compare(XYZPoint o1, XYZPoint o2) {
95 return Double.compare(o1.z, o2.z);
114 static final int X_AXIS = 0;
115 static final int Y_AXIS = 1;
116 static final int Z_AXIS = 2;
136 if (points == null || points.size() < 1) {
141 points.sort((a, b) -> KdNode.compareTo(depth, a, b));
144 int centerPtIdx = points.size() / 2;
145 KdNode thisNode =
new KdNode(points.get(centerPtIdx), depth, parent);
148 List<T> lesserList = centerPtIdx > 0 ? points.subList(0, centerPtIdx) : null;
150 List<T> greaterList = centerPtIdx < points.size() - 1 ? points.subList(centerPtIdx + 1, points.size()) : null;
151 thisNode.setGreater(
getBalancedNode(thisNode, greaterList, depth + 1));
163 public boolean add(T value) {
169 root =
new KdNode(value, 0, null);
175 if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
177 if (node.getLesser() == null) {
178 KdNode newNode =
new KdNode(value, node.getDepth() + 1, node);
179 node.setLesser(newNode);
182 node = node.getLesser();
185 if (node.getGreater() == null) {
186 KdNode newNode =
new KdNode(value, node.getDepth() + 1, node);
187 node.setGreater(newNode);
190 node = node.getGreater();
205 if (value == null || root == null) {
209 KdNode node = getNode(
this, value);
210 return (node != null);
222 if (tree == null || tree.
getRoot() == null || value == null) {
228 if (node.getPoint().equals(value)) {
230 }
else if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
232 if (node.getLesser() == null) {
235 node = node.getLesser();
238 if (node.getGreater() == null) {
241 node = node.getGreater();
255 @SuppressWarnings(
"unchecked")
257 if (value == null || root == null) {
258 return Collections.EMPTY_LIST;
262 TreeSet<KdNode> results =
new TreeSet<>(
new EuclideanComparator(value));
267 while (node != null) {
268 if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
271 node = node.getLesser();
275 node = node.getGreater();
282 Set<KdNode> examined =
new HashSet<>();
286 while (node != null) {
288 searchNode(value, node, numNeighbors, results, examined);
289 node = node.getParent();
294 Collection<T> collection =
new ArrayList<>(numNeighbors);
295 for (KdNode kdNode : results) {
296 collection.add((T) kdNode.getPoint());
311 private <T extends
KdTree.
XYZPoint>
void searchNode(T value, KdNode node,
int numNeighbors, TreeSet<KdNode> results, Set<KdNode> examined) {
316 Double lastDistance = Double.MAX_VALUE;
317 if (results.size() > 0) {
318 lastNode = results.last();
321 Double nodeDistance = node.getPoint().euclideanDistance(value);
322 if (nodeDistance.compareTo(lastDistance) < 0) {
324 }
else if (nodeDistance.equals(lastDistance)) {
326 }
else if (results.size() < numNeighbors) {
329 lastNode = results.last();
330 lastDistance = lastNode.getPoint().euclideanDistance(value);
333 KdNode lesser = node.getLesser();
334 KdNode greater = node.getGreater();
338 if (lesser != null && !examined.contains(lesser)) {
339 examined.add(lesser);
342 double valuePlusDistance;
345 nodePoint = node.getPoint().x;
346 valuePlusDistance = value.x - lastDistance;
349 nodePoint = node.getPoint().y;
350 valuePlusDistance = value.y - lastDistance;
353 nodePoint = node.getPoint().z;
354 valuePlusDistance = value.z - lastDistance;
357 boolean lineIntersectsCube = valuePlusDistance <= nodePoint;
360 if (lineIntersectsCube) {
361 searchNode(value, lesser, numNeighbors, results, examined);
364 if (greater != null && !examined.contains(greater)) {
365 examined.add(greater);
368 double valuePlusDistance;
371 nodePoint = node.getPoint().x;
372 valuePlusDistance = value.x + lastDistance;
375 nodePoint = node.getPoint().y;
376 valuePlusDistance = value.y + lastDistance;
379 nodePoint = node.getPoint().z;
380 valuePlusDistance = value.z + lastDistance;
383 boolean lineIntersectsCube = valuePlusDistance >= nodePoint;
386 if (lineIntersectsCube) {
387 searchNode(value, greater, numNeighbors, results, examined);
400 @SuppressWarnings(
"unchecked")
401 private <T extends XYZPoint>
void search(final KdNode node, final Deque<T> results) {
403 results.add((T) node.getPoint());
404 search(node.getGreater(), results);
405 search(node.getLesser(), results);
428 if (d1.compareTo(d2) < 0) {
430 }
else if (d2.compareTo(d1) < 0) {
433 return o1.getPoint().
compareTo(o2.getPoint());
445 final Deque<T> results =
new ArrayDeque<>();
446 search(root, results);
447 return results.iterator();
457 final Deque<T> results =
new ArrayDeque<>();
458 search(root, results);
459 return results.descendingIterator();
469 public static class KdNode implements Comparable<KdNode> {
506 return X_COMPARATOR.compare(point1, point2);
508 return Y_COMPARATOR.compare(point1, point2);
510 return Z_COMPARATOR.compare(point1, point2);
539 void setLesser(
KdNode node) {
557 void setGreater(
KdNode node) {
576 XYZPoint getPoint() {
585 return 31 * (DIMENSIONS + this.depth + this.getPoint().
hashCode());
596 if (!(obj instanceof
KdNode)) {
600 KdNode kdNode = (
KdNode) obj;
609 return compareTo(depth, this.getPoint(), o.getPoint());
617 StringBuilder builder =
new StringBuilder(200);
618 builder.append(
"dimensions=").append(DIMENSIONS).append(
" depth=").append(depth).append(
" point=").append(getPoint().
toString());
619 return builder.toString();
628 public static class XYZPoint implements Comparable<XYZPoint> {
630 protected final double x;
631 protected final double y;
632 protected final double z;
700 double lat1Radians = Math.toRadians(o1.
getX());
701 double lat2Radians = Math.toRadians(o2.
getX());
703 double deltaLatRadians = Math.toRadians(o2.
getX() - o1.
getX());
704 double deltaLongRadians = Math.toRadians(o2.
getY() - o1.
getY());
706 double a = Math.sin(deltaLatRadians / 2) * Math.sin(deltaLatRadians / 2)
707 + Math.cos(lat1Radians) * Math.cos(lat2Radians)
708 * Math.sin(deltaLongRadians / 2) * Math.sin(deltaLongRadians / 2);
710 double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
712 return EARTH_RADIUS * c;
720 return 31 * (int) (this.x + this.y + this.z);
738 return ((Double.compare(
this.x, xyzPoint.
x) == 0)
739 && (Double.compare(
this.y, xyzPoint.
y) == 0)
740 && (Double.compare(
this.z, xyzPoint.
z) == 0));
748 int xComp = X_COMPARATOR.compare(
this, o);
753 int yComp = Y_COMPARATOR.compare(
this, o);
757 return Z_COMPARATOR.compare(
this, o);
765 StringBuilder builder =
new StringBuilder(200);
767 builder.append(x).append(
", ");
768 builder.append(y).append(
", ");
771 return builder.toString();
static int compareTo(int depth, XYZPoint point1, XYZPoint point2)
XYZPoint(Double x, Double y)
boolean equals(Object obj)
KdNode getBalancedNode(KdNode parent, List< T > points, int depth)
Collection< T > nearestNeighbourSearch(int numNeighbors, T value)
static final int DIMENSIONS
Iterator< T > reverse_iterator()
int compareTo(XYZPoint o)
boolean equals(Object obj)
double euclideanDistance(XYZPoint o1)
static final double EARTH_RADIUS
static double euclideanDistance(XYZPoint o1, XYZPoint o2)
boolean contains(T value)
static final Comparator< XYZPoint > Y_COMPARATOR
int compare(KdNode o1, KdNode o2)
static final Comparator< XYZPoint > X_COMPARATOR
static final Comparator< XYZPoint > Z_COMPARATOR
KdNode(XYZPoint point, int depth, KdNode parent)