From 55d7ed16a9760e9582b6b8b838b2f97922638b18 Mon Sep 17 00:00:00 2001
From: Anton Tananaev <anton.tananaev@gmail.com>
Date: Mon, 11 Apr 2016 15:23:49 +1200
Subject: Implement location search tree

---
 src/org/traccar/helper/LocationTree.java      | 116 ++++++++++++++++++++++++++
 test/org/traccar/helper/LocationTreeTest.java |  29 +++++++
 2 files changed, 145 insertions(+)
 create mode 100644 src/org/traccar/helper/LocationTree.java
 create mode 100644 test/org/traccar/helper/LocationTreeTest.java

diff --git a/src/org/traccar/helper/LocationTree.java b/src/org/traccar/helper/LocationTree.java
new file mode 100644
index 000000000..1d7d8ab25
--- /dev/null
+++ b/src/org/traccar/helper/LocationTree.java
@@ -0,0 +1,116 @@
+/*
+ * Copyright 2016 Anton Tananaev (anton.tananaev@gmail.com)
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.traccar.helper;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+public class LocationTree {
+
+    public static class Item {
+
+        private Item left, right;
+        private float x, y;
+        private String data;
+
+        public Item(float x, float y) {
+            this(x, y, null);
+        }
+
+        public Item(float x, float y, String data) {
+            this.x = x;
+            this.y = y;
+            this.data = data;
+        }
+
+        public String getData() {
+            return data;
+        }
+
+        private float squaredDistance(Item item) {
+            return (x - item.x) * (x - item.x) + (y - item.y) * (y - item.y);
+        }
+
+        private float axisSquaredDistance(Item item, int axis) {
+            if (axis == 0) {
+                return (x - item.x) * (x - item.x);
+            } else {
+                return (y - item.y) * (y - item.y);
+            }
+        }
+
+    }
+
+    private Item root;
+
+    private ArrayList<Comparator<Item>> comparators = new ArrayList<>();
+
+    public LocationTree(List<Item> items) {
+        comparators.add(new Comparator<Item>() {
+            @Override
+            public int compare(Item o1, Item o2) {
+                return Float.compare(o1.x, o2.x);
+            }
+        });
+        comparators.add(new Comparator<Item>() {
+            @Override
+            public int compare(Item o1, Item o2) {
+                return Float.compare(o1.y, o2.y);
+            }
+        });
+        root = createTree(items, 0);
+    }
+
+    private Item createTree(List<Item> items, int depth) {
+        if (items.isEmpty()) {
+            return null;
+        }
+        Collections.sort(items, comparators.get(depth % 2));
+        int currentIndex = items.size() / 2;
+        Item median = items.get(currentIndex);
+        median.left = createTree(new ArrayList<>(items.subList(0, currentIndex)), depth + 1);
+        median.right = createTree(new ArrayList<>(items.subList(currentIndex + 1, items.size())), depth + 1);
+        return median;
+    }
+
+    public Item findNearest(Item search) {
+        return findNearest(root, search, 0);
+    }
+
+    private Item findNearest(Item current, Item search, int depth) {
+        int direction = comparators.get(depth % 2).compare(search, current);
+
+        Item next = (direction < 0) ? current.left : current.right;
+        Item other = (direction < 0) ? current.right : current.left;
+        Item best = (next == null) ? current : findNearest(next, search, depth + 1);
+        if (current.squaredDistance(search) < best.squaredDistance(search)) {
+            best = current;
+        }
+        if (other != null) {
+            if (current.axisSquaredDistance(search, depth % 2) < best.squaredDistance(search)) {
+                Item possibleBest = findNearest(other, search, depth + 1);
+                if (possibleBest.squaredDistance(search) < best.squaredDistance(search) ) {
+                    best = possibleBest;
+                }
+            }
+        }
+
+        return best;
+    }
+
+}
diff --git a/test/org/traccar/helper/LocationTreeTest.java b/test/org/traccar/helper/LocationTreeTest.java
new file mode 100644
index 000000000..afbbbc94c
--- /dev/null
+++ b/test/org/traccar/helper/LocationTreeTest.java
@@ -0,0 +1,29 @@
+package org.traccar.helper;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class LocationTreeTest {
+    
+    @Test
+    public void testLocationTree() {
+
+        List<LocationTree.Item> items = new ArrayList<>();
+        items.add(new LocationTree.Item(1, 1, "a"));
+        items.add(new LocationTree.Item(3, 2, "b"));
+        items.add(new LocationTree.Item(1, 3, "c"));
+        items.add(new LocationTree.Item(4, 3, "d"));
+
+        LocationTree tree = new LocationTree(items);
+
+        Assert.assertEquals("a", tree.findNearest(new LocationTree.Item(1f, 1f)).getData());
+        Assert.assertEquals("d", tree.findNearest(new LocationTree.Item(10f, 10f)).getData());
+        Assert.assertEquals("c", tree.findNearest(new LocationTree.Item(1f, 2.5f)).getData());
+        Assert.assertEquals("a", tree.findNearest(new LocationTree.Item(1.5f, 1.5f)).getData());
+
+    }
+
+}
-- 
cgit v1.2.3