Autopsy  4.14.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.Set;
30 import java.util.TreeSet;
31 
50 public class KdTree<T extends KdTree.XYZPoint> implements Iterable<T> {
51 
52  // The code generally supports the idea of a third dimension, but for
53  // simplicity, the code will only use 2 dimensions.
54  private static final int DIMENSIONS = 2;
55  private KdNode root = null;
56 
57  private static final double EARTH_RADIUS = 6371e3;
58 
62  private static final Comparator<XYZPoint> X_COMPARATOR = new Comparator<XYZPoint>() {
66  @Override
67  public int compare(XYZPoint o1, XYZPoint o2) {
68  return Double.compare(o1.x, o2.x);
69  }
70  };
71 
75  private static final Comparator<XYZPoint> Y_COMPARATOR = new Comparator<XYZPoint>() {
79  @Override
80  public int compare(XYZPoint o1, XYZPoint o2) {
81  return Double.compare(o1.y, o2.y);
82  }
83  };
84 
88  private static final Comparator<XYZPoint> Z_COMPARATOR = new Comparator<XYZPoint>() {
92  @Override
93  public int compare(XYZPoint o1, XYZPoint o2) {
94  return Double.compare(o1.z, o2.z);
95  }
96  };
97 
98  static final int X_AXIS = 0;
99  static final int Y_AXIS = 1;
100  static final int Z_AXIS = 2;
101 
102  public KdNode getRoot() {
103  return root;
104  }
105 
113  public boolean add(T value) {
114  if (value == null) {
115  return false;
116  }
117 
118  if (root == null) {
119  root = new KdNode(value, 0, null);
120  return true;
121  }
122 
123  KdNode node = root;
124  while (true) {
125  if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
126  // Lesser
127  if (node.getLesser() == null) {
128  KdNode newNode = new KdNode(value, node.getDepth() + 1, node);
129  node.setLesser(newNode);
130  break;
131  }
132  node = node.getLesser();
133  } else {
134  // Greater
135  if (node.getGreater() == null) {
136  KdNode newNode = new KdNode(value, node.getDepth() + 1, node);
137  node.setGreater(newNode);
138  break;
139  }
140  node = node.getGreater();
141  }
142  }
143 
144  return true;
145  }
146 
154  public boolean contains(T value) {
155  if (value == null || root == null) {
156  return false;
157  }
158 
159  KdNode node = getNode(this, value);
160  return (node != null);
161  }
162 
171  private <T extends KdTree.XYZPoint> KdNode getNode(KdTree<T> tree, T value) {
172  if (tree == null || tree.getRoot() == null || value == null) {
173  return null;
174  }
175 
176  KdNode node = tree.getRoot();
177  while (true) {
178  if (node.getPoint().equals(value)) {
179  return node;
180  } else if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
181  // Lesser
182  if (node.getLesser() == null) {
183  return null;
184  }
185  node = node.getLesser();
186  } else {
187  // Greater
188  if (node.getGreater() == null) {
189  return null;
190  }
191  node = node.getGreater();
192  }
193  }
194  }
195 
205  @SuppressWarnings("unchecked")
206  public Collection<T> nearestNeighbourSearch(int numNeighbors, T value) {
207  if (value == null || root == null) {
208  return Collections.EMPTY_LIST;
209  }
210 
211  // Map used for results
212  TreeSet<KdNode> results = new TreeSet<>(new EuclideanComparator(value));
213 
214  // Find the closest leaf node
215  KdNode prev = null;
216  KdNode node = root;
217  while (node != null) {
218  if (KdNode.compareTo(node.getDepth(), value, node.getPoint()) <= 0) {
219  // Lesser
220  prev = node;
221  node = node.getLesser();
222  } else {
223  // Greater
224  prev = node;
225  node = node.getGreater();
226  }
227  }
228  KdNode leaf = prev;
229 
230  if (leaf != null) {
231  // Used to not re-examine nodes
232  Set<KdNode> examined = new HashSet<>();
233 
234  // Go up the tree, looking for better solutions
235  node = leaf;
236  while (node != null) {
237  // Search node
238  searchNode(value, node, numNeighbors, results, examined);
239  node = node.getParent();
240  }
241  }
242 
243  // Load up the collection of the results
244  Collection<T> collection = new ArrayList<>(numNeighbors);
245  for (KdNode kdNode : results) {
246  collection.add((T) kdNode.getPoint());
247  }
248  return collection;
249  }
250 
261  private <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int numNeighbors, TreeSet<KdNode> results, Set<KdNode> examined) {
262  examined.add(node);
263 
264  // Search node
265  KdNode lastNode;
266  Double lastDistance = Double.MAX_VALUE;
267  if (results.size() > 0) {
268  lastNode = results.last();
269  lastDistance = lastNode.getPoint().euclideanDistance(value);
270  }
271  Double nodeDistance = node.getPoint().euclideanDistance(value);
272  if (nodeDistance.compareTo(lastDistance) < 0) {
273  results.add(node);
274  } else if (nodeDistance.equals(lastDistance)) {
275  results.add(node);
276  } else if (results.size() < numNeighbors) {
277  results.add(node);
278  }
279  lastNode = results.last();
280  lastDistance = lastNode.getPoint().euclideanDistance(value);
281 
282  int axis = node.getDepth() % DIMENSIONS;
283  KdNode lesser = node.getLesser();
284  KdNode greater = node.getGreater();
285 
286  // Search children branches, if axis aligned distance is less than
287  // current distance
288  if (lesser != null && !examined.contains(lesser)) {
289  examined.add(lesser);
290 
291  double nodePoint;
292  double valuePlusDistance;
293  switch (axis) {
294  case X_AXIS:
295  nodePoint = node.getPoint().x;
296  valuePlusDistance = value.x - lastDistance;
297  break;
298  case Y_AXIS:
299  nodePoint = node.getPoint().y;
300  valuePlusDistance = value.y - lastDistance;
301  break;
302  default: // Z_AXIS
303  nodePoint = node.getPoint().z;
304  valuePlusDistance = value.z - lastDistance;
305  break;
306  }
307  boolean lineIntersectsCube = valuePlusDistance <= nodePoint;
308 
309  // Continue down lesser branch
310  if (lineIntersectsCube) {
311  searchNode(value, lesser, numNeighbors, results, examined);
312  }
313  }
314  if (greater != null && !examined.contains(greater)) {
315  examined.add(greater);
316 
317  double nodePoint;
318  double valuePlusDistance;
319  switch (axis) {
320  case X_AXIS:
321  nodePoint = node.getPoint().x;
322  valuePlusDistance = value.x + lastDistance;
323  break;
324  case Y_AXIS:
325  nodePoint = node.getPoint().y;
326  valuePlusDistance = value.y + lastDistance;
327  break;
328  default: //Z_AXIS
329  nodePoint = node.getPoint().z;
330  valuePlusDistance = value.z + lastDistance;
331  break;
332  }
333  boolean lineIntersectsCube = valuePlusDistance >= nodePoint;
334 
335  // Continue down greater branch
336  if (lineIntersectsCube) {
337  searchNode(value, greater, numNeighbors, results, examined);
338  }
339  }
340  }
341 
350  @SuppressWarnings("unchecked")
351  private <T extends XYZPoint> void search(final KdNode node, final Deque<T> results) {
352  if (node != null) {
353  results.add((T) node.getPoint());
354  search(node.getGreater(), results);
355  search(node.getLesser(), results);
356  }
357  }
358 
363  private final class EuclideanComparator implements Comparator<KdNode> {
364 
365  private final XYZPoint point;
366 
368  this.point = point;
369  }
370 
374  @Override
375  public int compare(KdNode o1, KdNode o2) {
376  Double d1 = point.euclideanDistance(o1.getPoint());
377  Double d2 = point.euclideanDistance(o2.getPoint());
378  if (d1.compareTo(d2) < 0) {
379  return -1;
380  } else if (d2.compareTo(d1) < 0) {
381  return 1;
382  }
383  return o1.getPoint().compareTo(o2.getPoint());
384  }
385  }
386 
393  @Override
394  public Iterator<T> iterator() {
395  final Deque<T> results = new ArrayDeque<>();
396  search(root, results);
397  return results.iterator();
398  }
399 
406  public Iterator<T> reverse_iterator() {
407  final Deque<T> results = new ArrayDeque<>();
408  search(root, results);
409  return results.descendingIterator();
410  }
411 
419  public static class KdNode implements Comparable<KdNode> {
420 
421  private final XYZPoint point;
422  private final int depth;
423  private final KdNode parent;
424 
425  private KdNode lesser = null;
426  private KdNode greater = null;
427 
435  public KdNode(XYZPoint point, int depth, KdNode parent) {
436  this.point = point;
437  this.depth = depth;
438  this.parent = parent;
439  }
440 
452  public static int compareTo(int depth, XYZPoint point1, XYZPoint point2) {
453  int axis = depth % DIMENSIONS;
454  switch (axis) {
455  case X_AXIS:
456  return X_COMPARATOR.compare(point1, point2);
457  case Y_AXIS:
458  return Y_COMPARATOR.compare(point1, point2);
459  default:
460  return Z_COMPARATOR.compare(point1, point2);
461  }
462  }
463 
469  int getDepth() {
470  return depth;
471  }
472 
480  KdNode getParent() {
481  return parent;
482  }
483 
489  void setLesser(KdNode node) {
490  lesser = node;
491  }
492 
498  KdNode getLesser() {
499  return lesser;
500  }
501 
507  void setGreater(KdNode node) {
508  greater = node;
509  }
510 
516  KdNode getGreater() {
517  return greater;
518  }
519 
526  XYZPoint getPoint() {
527  return point;
528  }
529 
533  @Override
534  public int hashCode() {
535  return 31 * (DIMENSIONS + this.depth + this.getPoint().hashCode());
536  }
537 
541  @Override
542  public boolean equals(Object obj) {
543  if (obj == null) {
544  return false;
545  }
546  if (!(obj instanceof KdNode)) {
547  return false;
548  }
549 
550  KdNode kdNode = (KdNode) obj;
551  return (this.compareTo(kdNode) == 0);
552  }
553 
557  @Override
558  public int compareTo(KdNode o) {
559  return compareTo(depth, this.getPoint(), o.getPoint());
560  }
561 
565  @Override
566  public String toString() {
567  StringBuilder builder = new StringBuilder(200);
568  builder.append("dimensions=").append(DIMENSIONS).append(" depth=").append(depth).append(" point=").append(getPoint().toString());
569  return builder.toString();
570  }
571  }
572 
578  public static class XYZPoint implements Comparable<XYZPoint> {
579 
580  protected final double x;
581  protected final double y;
582  protected final double z;
583 
590  public XYZPoint(Double latitude, Double longitude) {
591  x = latitude;
592  y = longitude;
593  z = 0;
594  }
595 
601  public double getX() {
602  return x;
603  }
604 
610  public double getY() {
611  return y;
612  }
613 
619  public double getZ() {
620  return z;
621  }
622 
630  public double euclideanDistance(XYZPoint o1) {
631  return euclideanDistance(o1, this);
632  }
633 
645  private static double euclideanDistance(XYZPoint o1, XYZPoint o2) {
646  if (o1.equals(o2)) {
647  return 0;
648  }
649 
650  double lat1Radians = Math.toRadians(o1.getX());
651  double lat2Radians = Math.toRadians(o2.getX());
652 
653  double deltaLatRadians = Math.toRadians(o2.getX() - o1.getX());
654  double deltaLongRadians = Math.toRadians(o2.getY() - o1.getY());
655 
656  double a = Math.sin(deltaLatRadians / 2) * Math.sin(deltaLatRadians / 2)
657  + Math.cos(lat1Radians) * Math.cos(lat2Radians)
658  * Math.sin(deltaLongRadians / 2) * Math.sin(deltaLongRadians / 2);
659 
660  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
661 
662  return EARTH_RADIUS * c;
663  }
664 
668  @Override
669  public int hashCode() {
670  return 31 * (int) (this.x + this.y + this.z);
671  }
672 
676  @Override
677  public boolean equals(Object obj) {
678  if (obj == null) {
679  return false;
680  }
681 
682  if (!(obj instanceof XYZPoint)) {
683  return false;
684  }
685 
686  XYZPoint xyzPoint = (XYZPoint) obj;
687 
688  return ((Double.compare(this.x, xyzPoint.x) == 0)
689  && (Double.compare(this.y, xyzPoint.y) == 0)
690  && (Double.compare(this.z, xyzPoint.z) == 0));
691  }
692 
696  @Override
697  public int compareTo(XYZPoint o) {
698  int xComp = X_COMPARATOR.compare(this, o);
699  if (xComp != 0) {
700  return xComp;
701  }
702 
703  int yComp = Y_COMPARATOR.compare(this, o);
704  if (yComp != 0) {
705  return yComp;
706  }
707  return Z_COMPARATOR.compare(this, o);
708  }
709 
713  @Override
714  public String toString() {
715  StringBuilder builder = new StringBuilder(200);
716  builder.append("(");
717  builder.append(x).append(", ");
718  builder.append(y).append(", ");
719  builder.append(z);
720  builder.append(")");
721  return builder.toString();
722  }
723  }
724 }
static int compareTo(int depth, XYZPoint point1, XYZPoint point2)
Definition: KdTree.java:452
Collection< T > nearestNeighbourSearch(int numNeighbors, T value)
Definition: KdTree.java:206
XYZPoint(Double latitude, Double longitude)
Definition: KdTree.java:590
static double euclideanDistance(XYZPoint o1, XYZPoint o2)
Definition: KdTree.java:645
static final Comparator< XYZPoint > Y_COMPARATOR
Definition: KdTree.java:75
static final Comparator< XYZPoint > X_COMPARATOR
Definition: KdTree.java:62
static final Comparator< XYZPoint > Z_COMPARATOR
Definition: KdTree.java:88
KdNode(XYZPoint point, int depth, KdNode parent)
Definition: KdTree.java:435

Copyright © 2012-2020 Basis Technology. Generated on: Wed Apr 8 2020
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.