Autopsy  4.18.0
Graphical digital forensics platform for The Sleuth Kit and other tools.
LatLngMap.java
Go to the documentation of this file.
1 /*
2  * Autopsy Forensic Browser
3  *
4  * Copyright 2020 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.datasourcesummary.datamodel;
20 
21 import java.util.Collection;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.function.Function;
25 import java.util.stream.Collectors;
26 import java.util.stream.Stream;
27 import org.apache.commons.lang3.tuple.Pair;
30 
35 class LatLngMap<E extends KdTree.XYZPoint> {
36 
37  // radius of Earth in kilometers
38  private static final double EARTH_RADIUS = 6371;
39 
40  // 300 km buckets with 150km accuracy
41  private static final double DEFAULT_BUCKET_SIZE = 300;
42 
43  // maps the determined pair of (north/south index, east/west index) to the KdTree containing all items within that bucket.
44  private final Map<Pair<Integer, Integer>, KdTree<E>> latLngMap;
45 
46  private final double bucketSize;
47 
48  // calculates the bucket for a specific point provided.
49  private final Function<XYZPoint, Pair<Integer, Integer>> bucketCalculator = (point) -> {
50  Pair<Double, Double> dPair = getBucketLocation(point);
51  return Pair.of((int) (double) dPair.getLeft(), (int) (double) dPair.getRight());
52  };
53 
59  LatLngMap(List<E> pointsToAdd) {
60  this(pointsToAdd, DEFAULT_BUCKET_SIZE);
61  }
62 
70  LatLngMap(List<E> pointsToAdd, double bucketSize) {
71  this.bucketSize = bucketSize;
72 
73  Map<Pair<Integer, Integer>, List<E>> latLngBuckets = pointsToAdd.stream()
74  .collect(Collectors.groupingBy((pt) -> bucketCalculator.apply(pt)));
75 
76  this.latLngMap = latLngBuckets.entrySet().stream()
77  .map(e -> Pair.of(e.getKey(), new KdTree<E>(e.getValue())))
78  .collect(Collectors.toMap(p -> p.getKey(), p -> p.getValue()));
79  }
80 
91  private Pair<Double, Double> getBucketLocation(XYZPoint point) {
92  double y = euclideanDistance(new XYZPoint(0D, 0D), new XYZPoint(0D, point.getY())) / bucketSize;
93  if (point.getY() < 0) {
94  y = -y;
95  }
96 
97  double x = euclideanDistance(new XYZPoint(0D, point.getY()), new XYZPoint(point.getX(), point.getY())) / bucketSize;
98  if (point.getX() < 0) {
99  x = -x;
100  }
101 
102  return Pair.of(y, x);
103  }
104 
111  E findClosest(E point) {
112  Pair<Double, Double> calculated = getBucketLocation(point);
113  // search 2x2 grid around point for closest item. This is done so that if a point is on the
114  // edge of a grid square and a point in another square is actually closer.
115  int latBucket = (int) (double) calculated.getLeft();
116  int latBucket2 = Math.round(calculated.getLeft()) == latBucket ? latBucket - 1 : latBucket + 1;
117 
118  int lngBucket = (int) (double) calculated.getRight();
119  int lngBucket2 = Math.round(calculated.getRight()) == lngBucket ? lngBucket - 1 : lngBucket + 1;
120 
121  E closest1 = findClosestInBucket(latBucket, lngBucket, point);
122  E closest2 = findClosestInBucket(latBucket2, lngBucket, point);
123  E closest3 = findClosestInBucket(latBucket, lngBucket2, point);
124  E closest4 = findClosestInBucket(latBucket2, lngBucket2, point);
125 
126  return Stream.of(closest1, closest2, closest3, closest4)
127  .filter(c -> c != null && euclideanDistance(point, c) <= bucketSize / 2)
128  .min((a, b) -> Double.compare(euclideanDistance(point, a), euclideanDistance(point, b)))
129  .orElse(null);
130  }
131 
140  private E findClosestInBucket(int x, int y, E point) {
141  KdTree<E> thisLatLngMap = latLngMap.get(Pair.of(x, y));
142  if (thisLatLngMap == null) {
143  return null;
144  }
145 
146  Collection<E> closest = thisLatLngMap.nearestNeighbourSearch(1, point);
147  if (closest != null && closest.size() > 0) {
148  return closest.iterator().next();
149  } else {
150  return null;
151  }
152  }
153 
165  private static double euclideanDistance(KdTree.XYZPoint o1, KdTree.XYZPoint o2) {
166  if (o1.equals(o2)) {
167  return 0;
168  }
169 
170  double lat1Radians = Math.toRadians(o1.getY());
171  double lat2Radians = Math.toRadians(o2.getY());
172 
173  double deltaLatRadians = Math.toRadians(o2.getY() - o1.getY());
174  double deltaLongRadians = Math.toRadians(o2.getX() - o1.getX());
175 
176  double a = Math.sin(deltaLatRadians / 2) * Math.sin(deltaLatRadians / 2)
177  + Math.cos(lat1Radians) * Math.cos(lat2Radians)
178  * Math.sin(deltaLongRadians / 2) * Math.sin(deltaLongRadians / 2);
179 
180  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
181 
182  return EARTH_RADIUS * c;
183  }
184 }

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