Autopsy  4.19.3
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-2021 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 
92  private Pair<Double, Double> getBucketLocation(XYZPoint point) {
93  double y = euclideanDistance(new XYZPoint(0D, 0D), new XYZPoint(0D, point.getY())) / bucketSize;
94  if (point.getY() < 0) {
95  y = -y;
96  }
97 
98  double x = euclideanDistance(new XYZPoint(0D, point.getY()), new XYZPoint(point.getX(), point.getY())) / bucketSize;
99  if (point.getX() < 0) {
100  x = -x;
101  }
102 
103  return Pair.of(y, x);
104  }
105 
113  E findClosest(E point) {
114  Pair<Double, Double> calculated = getBucketLocation(point);
115  // search 2x2 grid around point for closest item. This is done so that if a point is on the
116  // edge of a grid square and a point in another square is actually closer.
117  int latBucket = (int) (double) calculated.getLeft();
118  int latBucket2 = Math.round(calculated.getLeft()) == latBucket ? latBucket - 1 : latBucket + 1;
119 
120  int lngBucket = (int) (double) calculated.getRight();
121  int lngBucket2 = Math.round(calculated.getRight()) == lngBucket ? lngBucket - 1 : lngBucket + 1;
122 
123  E closest1 = findClosestInBucket(latBucket, lngBucket, point);
124  E closest2 = findClosestInBucket(latBucket2, lngBucket, point);
125  E closest3 = findClosestInBucket(latBucket, lngBucket2, point);
126  E closest4 = findClosestInBucket(latBucket2, lngBucket2, point);
127 
128  return Stream.of(closest1, closest2, closest3, closest4)
129  .filter(c -> c != null && euclideanDistance(point, c) <= bucketSize / 2)
130  .min((a, b) -> Double.compare(euclideanDistance(point, a), euclideanDistance(point, b)))
131  .orElse(null);
132  }
133 
143  private E findClosestInBucket(int x, int y, E point) {
144  KdTree<E> thisLatLngMap = latLngMap.get(Pair.of(x, y));
145  if (thisLatLngMap == null) {
146  return null;
147  }
148 
149  Collection<E> closest = thisLatLngMap.nearestNeighbourSearch(1, point);
150  if (closest != null && closest.size() > 0) {
151  return closest.iterator().next();
152  } else {
153  return null;
154  }
155  }
156 
168  private static double euclideanDistance(KdTree.XYZPoint o1, KdTree.XYZPoint o2) {
169  if (o1.equals(o2)) {
170  return 0;
171  }
172 
173  double lat1Radians = Math.toRadians(o1.getY());
174  double lat2Radians = Math.toRadians(o2.getY());
175 
176  double deltaLatRadians = Math.toRadians(o2.getY() - o1.getY());
177  double deltaLongRadians = Math.toRadians(o2.getX() - o1.getX());
178 
179  double a = Math.sin(deltaLatRadians / 2) * Math.sin(deltaLatRadians / 2)
180  + Math.cos(lat1Radians) * Math.cos(lat2Radians)
181  * Math.sin(deltaLongRadians / 2) * Math.sin(deltaLongRadians / 2);
182 
183  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
184 
185  return EARTH_RADIUS * c;
186  }
187 }

Copyright © 2012-2022 Basis Technology. Generated on: Tue Jun 27 2023
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.