Algorithms-I : 5-KdTrees: super fast

1 files changed, 35 insertions, 37 deletions

diff --git a/Algorithms/Part-I/5-KdTrees/KdTree.java b/Algorithms/Part-I/5-KdTrees/KdTree.java
index 6a13d16..3607976 100644
--- a/Algorithms/Part-I/5-KdTrees/KdTree.java
+++ b/Algorithms/Part-I/5-KdTrees/KdTree.java
@@ -9,7 +9,6 @@ public class KdTree
 
     private Node root;
     private int size;
-    NearestChampion ncp;
 
     private class Node {
         private Point2D p;
@@ -21,22 +20,11 @@ public class KdTree
         }
     }
 
-    private class NearestChampion {
-        private Point2D p;
-        private double d;
-        public NearestChampion(Point2D p, double d)
-        {
-            this.p = p;
-            this.d = d;
-        }
-    }
-
     // construct an empty tree of points
     public KdTree()
     {
         size = 0;
         root = null;
-        ncp = new NearestChampion(null, Double.MAX_VALUE);
     }
 
     // is the tree empty?
@@ -201,57 +189,67 @@ public class KdTree
     {
         if ((p == null) || (root == null)) return null;
 
-        ncp.p = null;
-        ncp.d = Double.MAX_VALUE;
-        nearest(root, p, ncp, true);
-
-        return ncp.p;
+        return nearest(root, p, null, Double.MAX_VALUE, true);
     }
 
-    private void nearest(Node n, Point2D p, NearestChampion ncp, boolean vsplit)
+    private Point2D nearest(Node n, Point2D p, Point2D ncp, double d, boolean vsplit)
     {
         double d2 = p.distanceSquaredTo(n.p);
-        if (d2 < ncp.d)
+        if (d2 < d)
         {
-            ncp.d = d2;
-            ncp.p = n.p;
+            ncp = n.p;
+            d = d2;
         }
+
         if (vsplit)
         {
-            double d3 = n.p.x() - p.x();
-            if (d3 > 0)
+            d2 = n.p.x() - p.x();
+            if (d2 > 0)
             {
                 if (n.left != null)
-                    nearest(n.left, p, ncp, !vsplit);
-                if (n.right != null && ((d3 * d3) < ncp.d))
-                    nearest(n.right, p, ncp, !vsplit);
+                {
+                    ncp = nearest(n.left, p, ncp, d, !vsplit);
+                    d = p.distanceSquaredTo(ncp);
+                }
+                if (n.right != null && ((d2 * d2) < d))
+                    ncp = nearest(n.right, p, ncp, d, !vsplit);
             }
             else
             {
                 if (n.right != null)
-                    nearest(n.right, p, ncp, !vsplit);
-                if (n.left != null && ((d3 * d3) < ncp.d))
-                    nearest(n.left, p, ncp, !vsplit);
+                {
+                    ncp = nearest(n.right, p, ncp, d, !vsplit);
+                    d = p.distanceSquaredTo(ncp);
+                }
+                if (n.left != null && ((d2 * d2) < d))
+                    ncp = nearest(n.left, p, ncp, d, !vsplit);
             }
         }
         else
         {
-            double d3 = n.p.y() - p.y();
-            if (d3 > 0)
+            d2 = n.p.y() - p.y();
+            if (d2 > 0)
             {
                 if (n.left != null)
-                    nearest(n.left, p, ncp, !vsplit);
-                if (n.right != null && ((d3 * d3) < ncp.d))
-                    nearest(n.right, p, ncp, !vsplit);
+                {
+                    ncp = nearest(n.left, p, ncp, d, !vsplit);
+                    d = p.distanceSquaredTo(ncp);
+                }
+                if (n.right != null && ((d2 * d2) < d))
+                    ncp = nearest(n.right, p, ncp, d, !vsplit);
             }
             else
             {
                 if (n.right != null)
-                    nearest(n.right, p, ncp, !vsplit);
-                if (n.left != null && ((d3 * d3) < ncp.d))
-                    nearest(n.left, p, ncp, !vsplit);
+                {
+                    ncp = nearest(n.right, p, ncp, d, !vsplit);
+                    d = p.distanceSquaredTo(ncp);
+                }
+                if (n.left != null && ((d2 * d2) < d))
+                    ncp = nearest(n.left, p, ncp, d, !vsplit);
             }
         }
+        return ncp;
     }
 
 }