Autopsy  4.17.0
Graphical digital forensics platform for The Sleuth Kit and other tools.
KdTree.java
Go to the documentation of this file.
1 /*
2  * Autopsy Forensic Browser
3  *
4  * Copyright 2019 Basis Technology Corp.
5  * contact: carrier <at> sleuthkit <dot> org
6  *
7  * Licensed under the Apache License, Version 2.0 (the "License");
8  * you may not use this file except in compliance with the License.
9  * You may obtain a copy of the License at
10  *
11  * http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing, software
14  * distributed under the License is distributed on an "AS IS" BASIS,
15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  * See the License for the specific language governing permissions and
17  * limitations under the License.
18  */
19 package org.sleuthkit.autopsy.geolocation;
20 
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;
30 import java.util.Set;
31 import java.util.TreeSet;
32 
51 public class KdTree<T extends KdTree.XYZPoint> implements Iterable<T> {
52 
53  // The code generally supports the idea of a third dimension, but for
54  // simplicity, the code will only use 2 dimensions.
55  private static final int DIMENSIONS = 2;
56  private KdNode root = null;
57 
58  private static final double EARTH_RADIUS = 6371e3;
59 
63  private static final Comparator<XYZPoint> X_COMPARATOR = new Comparator<XYZPoint>() {
67  @Override
68  public int compare(XYZPoint o1, XYZPoint o2) {
69  return Double.compare(o1.x, o2.x);
70  }
71  };
72 
76  private static final Comparator<XYZPoint> Y_COMPARATOR = new Comparator<XYZPoint>() {
80  @Override
81  public int compare(XYZPoint o1, XYZPoint o2) {
82  return Double.compare(o1.y, o2.y);
83  }
84  };
85 
89  private static final Comparator<XYZPoint> Z_COMPARATOR = new Comparator<XYZPoint>() {
93  @Override
94  public int compare(XYZPoint o1, XYZPoint o2) {
95  return Double.compare(o1.z, o2.z);
96  }
97  };
98 
102  public KdTree() {
103  }
104 
110  public KdTree(List<T> points) {
111  this.root = getBalancedNode(null, points, 0);
112  }
113 
114  static final int X_AXIS = 0;
115  static final int Y_AXIS = 1;
116  static final int Z_AXIS = 2;
117 
118  public KdNode getRoot() {
119  return root;
120  }
121 
134  private KdNode getBalancedNode(KdNode parent, List<T> points, int depth) {
135  // if no points, return null.
136  if (points == null || points.size() < 1) {
137  return null;
138  }
139 
140  // sort with comparator for depth
141  points.sort((a, b) -> KdNode.compareTo(depth, a, b));
142 
143  // find center point
144  int centerPtIdx = points.size() / 2;
145  KdNode thisNode = new KdNode(points.get(centerPtIdx), depth, parent);
146 
147  // recurse on lesser and greater
148  List<T> lesserList = centerPtIdx > 0 ? points.subList(0, centerPtIdx) : null;
149  thisNode.setLesser(getBalancedNode(thisNode, lesserList, depth + 1));
150  List<T> greaterList = centerPtIdx < points.size() - 1 ? points.subList(centerPtIdx + 1, points.size()) : null;
151  thisNode.setGreater(getBalancedNode(thisNode, greaterList, depth + 1));
152 
153  return thisNode;
154  }
155 
163  public boolean add(T value) {
164  if (value == null) {
165  return false;
166  }
167 
168  if (root == null) {
169  root = new KdNode(value, 0, null);
170  return true;
171  }
172 
173  KdNode node = root;
174  while (true) {
175  if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
176  // Lesser
177  if (node.getLesser() == null) {
178  KdNode newNode = new KdNode(value, node.getDepth() + 1, node);
179  node.setLesser(newNode);
180  break;
181  }
182  node = node.getLesser();
183  } else {
184  // Greater
185  if (node.getGreater() == null) {
186  KdNode newNode = new KdNode(value, node.getDepth() + 1, node);
187  node.setGreater(newNode);
188  break;
189  }
190  node = node.getGreater();
191  }
192  }
193 
194  return true;
195  }
196 
204  public boolean contains(T value) {
205  if (value == null || root == null) {
206  return false;
207  }
208 
209  KdNode node = getNode(this, value);
210  return (node != null);
211  }
212 
221  private <T extends KdTree.XYZPoint> KdNode getNode(KdTree<T> tree, T value) {
222  if (tree == null || tree.getRoot() == null || value == null) {
223  return null;
224  }
225 
226  KdNode node = tree.getRoot();
227  while (true) {
228  if (node.getPoint().equals(value)) {
229  return node;
230  } else if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
231  // Lesser
232  if (node.getLesser() == null) {
233  return null;
234  }
235  node = node.getLesser();
236  } else {
237  // Greater
238  if (node.getGreater() == null) {
239  return null;
240  }
241  node = node.getGreater();
242  }
243  }
244  }
245 
255  @SuppressWarnings("unchecked")
256  public Collection<T> nearestNeighbourSearch(int numNeighbors, T value) {
257  if (value == null || root == null) {
258  return Collections.EMPTY_LIST;
259  }
260 
261  // Map used for results
262  TreeSet<KdNode> results = new TreeSet<>(new EuclideanComparator(value));
263 
264  // Find the closest leaf node
265  KdNode prev = null;
266  KdNode node = root;
267  while (node != null) {
268  if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
269  // Lesser
270  prev = node;
271  node = node.getLesser();
272  } else {
273  // Greater
274  prev = node;
275  node = node.getGreater();
276  }
277  }
278  KdNode leaf = prev;
279 
280  if (leaf != null) {
281  // Used to not re-examine nodes
282  Set<KdNode> examined = new HashSet<>();
283 
284  // Go up the tree, looking for better solutions
285  node = leaf;
286  while (node != null) {
287  // Search node
288  searchNode(value, node, numNeighbors, results, examined);
289  node = node.getParent();
290  }
291  }
292 
293  // Load up the collection of the results
294  Collection<T> collection = new ArrayList<>(numNeighbors);
295  for (KdNode kdNode : results) {
296  collection.add((T) kdNode.getPoint());
297  }
298  return collection;
299  }
300 
311  private <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int numNeighbors, TreeSet<KdNode> results, Set<KdNode> examined) {
312  examined.add(node);
313 
314  // Search node
315  KdNode lastNode;
316  Double lastDistance = Double.MAX_VALUE;
317  if (results.size() > 0) {
318  lastNode = results.last();
319  lastDistance = lastNode.getPoint().euclideanDistance(value);
320  }
321  Double nodeDistance = node.getPoint().euclideanDistance(value);
322  if (nodeDistance.compareTo(lastDistance) < 0) {
323  results.add(node);
324  } else if (nodeDistance.equals(lastDistance)) {
325  results.add(node);
326  } else if (results.size() < numNeighbors) {
327  results.add(node);
328  }
329  lastNode = results.last();
330  lastDistance = lastNode.getPoint().euclideanDistance(value);
331 
332  int axis = node.getDepth() % DIMENSIONS;
333  KdNode lesser = node.getLesser();
334  KdNode greater = node.getGreater();
335 
336  // Search children branches, if axis aligned distance is less than
337  // current distance
338  if (lesser != null && !examined.contains(lesser)) {
339  examined.add(lesser);
340 
341  double nodePoint;
342  double valuePlusDistance;
343  switch (axis) {
344  case X_AXIS:
345  nodePoint = node.getPoint().x;
346  valuePlusDistance = value.x - lastDistance;
347  break;
348  case Y_AXIS:
349  nodePoint = node.getPoint().y;
350  valuePlusDistance = value.y - lastDistance;
351  break;
352  default: // Z_AXIS
353  nodePoint = node.getPoint().z;
354  valuePlusDistance = value.z - lastDistance;
355  break;
356  }
357  boolean lineIntersectsCube = valuePlusDistance <= nodePoint;
358 
359  // Continue down lesser branch
360  if (lineIntersectsCube) {
361  searchNode(value, lesser, numNeighbors, results, examined);
362  }
363  }
364  if (greater != null && !examined.contains(greater)) {
365  examined.add(greater);
366 
367  double nodePoint;
368  double valuePlusDistance;
369  switch (axis) {
370  case X_AXIS:
371  nodePoint = node.getPoint().x;
372  valuePlusDistance = value.x + lastDistance;
373  break;
374  case Y_AXIS:
375  nodePoint = node.getPoint().y;
376  valuePlusDistance = value.y + lastDistance;
377  break;
378  default: //Z_AXIS
379  nodePoint = node.getPoint().z;
380  valuePlusDistance = value.z + lastDistance;
381  break;
382  }
383  boolean lineIntersectsCube = valuePlusDistance >= nodePoint;
384 
385  // Continue down greater branch
386  if (lineIntersectsCube) {
387  searchNode(value, greater, numNeighbors, results, examined);
388  }
389  }
390  }
391 
400  @SuppressWarnings("unchecked")
401  private <T extends XYZPoint> void search(final KdNode node, final Deque<T> results) {
402  if (node != null) {
403  results.add((T) node.getPoint());
404  search(node.getGreater(), results);
405  search(node.getLesser(), results);
406  }
407  }
408 
413  private final class EuclideanComparator implements Comparator<KdNode> {
414 
415  private final XYZPoint point;
416 
418  this.point = point;
419  }
420 
424  @Override
425  public int compare(KdNode o1, KdNode o2) {
426  Double d1 = point.euclideanDistance(o1.getPoint());
427  Double d2 = point.euclideanDistance(o2.getPoint());
428  if (d1.compareTo(d2) < 0) {
429  return -1;
430  } else if (d2.compareTo(d1) < 0) {
431  return 1;
432  }
433  return o1.getPoint().compareTo(o2.getPoint());
434  }
435  }
436 
443  @Override
444  public Iterator<T> iterator() {
445  final Deque<T> results = new ArrayDeque<>();
446  search(root, results);
447  return results.iterator();
448  }
449 
456  public Iterator<T> reverse_iterator() {
457  final Deque<T> results = new ArrayDeque<>();
458  search(root, results);
459  return results.descendingIterator();
460  }
461 
469  public static class KdNode implements Comparable<KdNode> {
470 
471  private final XYZPoint point;
472  private final int depth;
473  private final KdNode parent;
474 
475  private KdNode lesser = null;
476  private KdNode greater = null;
477 
485  public KdNode(XYZPoint point, int depth, KdNode parent) {
486  this.point = point;
487  this.depth = depth;
488  this.parent = parent;
489  }
490 
502  public static int compareTo(int depth, XYZPoint point1, XYZPoint point2) {
503  int axis = depth % DIMENSIONS;
504  switch (axis) {
505  case X_AXIS:
506  return X_COMPARATOR.compare(point1, point2);
507  case Y_AXIS:
508  return Y_COMPARATOR.compare(point1, point2);
509  default:
510  return Z_COMPARATOR.compare(point1, point2);
511  }
512  }
513 
519  int getDepth() {
520  return depth;
521  }
522 
530  KdNode getParent() {
531  return parent;
532  }
533 
539  void setLesser(KdNode node) {
540  lesser = node;
541  }
542 
548  KdNode getLesser() {
549  return lesser;
550  }
551 
557  void setGreater(KdNode node) {
558  greater = node;
559  }
560 
566  KdNode getGreater() {
567  return greater;
568  }
569 
576  XYZPoint getPoint() {
577  return point;
578  }
579 
583  @Override
584  public int hashCode() {
585  return 31 * (DIMENSIONS + this.depth + this.getPoint().hashCode());
586  }
587 
591  @Override
592  public boolean equals(Object obj) {
593  if (obj == null) {
594  return false;
595  }
596  if (!(obj instanceof KdNode)) {
597  return false;
598  }
599 
600  KdNode kdNode = (KdNode) obj;
601  return (this.compareTo(kdNode) == 0);
602  }
603 
607  @Override
608  public int compareTo(KdNode o) {
609  return compareTo(depth, this.getPoint(), o.getPoint());
610  }
611 
615  @Override
616  public String toString() {
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();
620  }
621  }
622 
628  public static class XYZPoint implements Comparable<XYZPoint> {
629 
630  protected final double x;
631  protected final double y;
632  protected final double z;
633 
640  public XYZPoint(Double x, Double y) {
641  this.x = x;
642  this.y = y;
643  z = 0;
644  }
645 
651  public double getX() {
652  return x;
653  }
654 
660  public double getY() {
661  return y;
662  }
663 
669  public double getZ() {
670  return z;
671  }
672 
680  public double euclideanDistance(XYZPoint o1) {
681  return euclideanDistance(o1, this);
682  }
683 
695  private static double euclideanDistance(XYZPoint o1, XYZPoint o2) {
696  if (o1.equals(o2)) {
697  return 0;
698  }
699 
700  double lat1Radians = Math.toRadians(o1.getX());
701  double lat2Radians = Math.toRadians(o2.getX());
702 
703  double deltaLatRadians = Math.toRadians(o2.getX() - o1.getX());
704  double deltaLongRadians = Math.toRadians(o2.getY() - o1.getY());
705 
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);
709 
710  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
711 
712  return EARTH_RADIUS * c;
713  }
714 
718  @Override
719  public int hashCode() {
720  return 31 * (int) (this.x + this.y + this.z);
721  }
722 
726  @Override
727  public boolean equals(Object obj) {
728  if (obj == null) {
729  return false;
730  }
731 
732  if (!(obj instanceof XYZPoint)) {
733  return false;
734  }
735 
736  XYZPoint xyzPoint = (XYZPoint) obj;
737 
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));
741  }
742 
746  @Override
747  public int compareTo(XYZPoint o) {
748  int xComp = X_COMPARATOR.compare(this, o);
749  if (xComp != 0) {
750  return xComp;
751  }
752 
753  int yComp = Y_COMPARATOR.compare(this, o);
754  if (yComp != 0) {
755  return yComp;
756  }
757  return Z_COMPARATOR.compare(this, o);
758  }
759 
763  @Override
764  public String toString() {
765  StringBuilder builder = new StringBuilder(200);
766  builder.append("(");
767  builder.append(x).append(", ");
768  builder.append(y).append(", ");
769  builder.append(z);
770  builder.append(")");
771  return builder.toString();
772  }
773  }
774 }
static int compareTo(int depth, XYZPoint point1, XYZPoint point2)
Definition: KdTree.java:502
KdNode getBalancedNode(KdNode parent, List< T > points, int depth)
Definition: KdTree.java:134
Collection< T > nearestNeighbourSearch(int numNeighbors, T value)
Definition: KdTree.java:256
static double euclideanDistance(XYZPoint o1, XYZPoint o2)
Definition: KdTree.java:695
static final Comparator< XYZPoint > Y_COMPARATOR
Definition: KdTree.java:76
static final Comparator< XYZPoint > X_COMPARATOR
Definition: KdTree.java:63
static final Comparator< XYZPoint > Z_COMPARATOR
Definition: KdTree.java:89
KdNode(XYZPoint point, int depth, KdNode parent)
Definition: KdTree.java:485

Copyright © 2012-2021 Basis Technology. Generated on: Tue Jan 19 2021
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.