From 883262806aaa1deacd1e1482e2136f8857e515ed Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Wed, 27 Mar 2013 12:44:06 +0100
Subject: Algorithms-I : 5-KdTrees: speed up maths

---
 Algorithms/Part-I/5-KdTrees/KdTree.java   | 18 +++++++++---------
 Algorithms/Part-I/5-KdTrees/PointSET.java |  2 +-
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/Algorithms/Part-I/5-KdTrees/KdTree.java b/Algorithms/Part-I/5-KdTrees/KdTree.java
index bcf4609..e11a769 100644
--- a/Algorithms/Part-I/5-KdTrees/KdTree.java
+++ b/Algorithms/Part-I/5-KdTrees/KdTree.java
@@ -207,7 +207,7 @@ public class KdTree
 
     private void nearest(Node n, Point2D p, NearestChampion ncp, boolean vsplit)
     {
-        double d2 = p.distanceTo(n.p);
+        double d2 = p.distanceSquaredTo(n.p);
         if (d2 < ncp.d)
         {
             ncp.d = d2;
@@ -215,37 +215,37 @@ public class KdTree
         }
         if (vsplit)
         {
-            double nx = n.p.x();
-            if (p.x() < nx)
+            double d3 = n.p.x() - p.x();
+            if (d3 > 0)
             {
                 if (n.left != null)
                     nearest(n.left, p, ncp, !vsplit);
-                if (n.right != null && ((nx - p.x()) < ncp.d))
+                if (n.right != null && ((d3 * d3) < ncp.d))
                     nearest(n.right, p, ncp, !vsplit);
             }
             else
             {
                 if (n.right != null)
                     nearest(n.right, p, ncp, !vsplit);
-                if (n.left != null && ((p.x() - nx) < ncp.d))
+                if (n.left != null && ((d3 * d3) < ncp.d))
                     nearest(n.left, p, ncp, !vsplit);
             }
         }
         else
         {
-            double ny = n.p.y();
-            if (p.y() < ny)
+            double d3 = n.p.y() - p.y();
+            if (d3 > 0)
             {
                 if (n.left != null)
                     nearest(n.left, p, ncp, !vsplit);
-                if (n.right != null && ((ny - p.y()) < ncp.d))
+                if (n.right != null && ((d3 * d3) < ncp.d))
                     nearest(n.right, p, ncp, !vsplit);
             }
             else
             {
                 if (n.right != null)
                     nearest(n.right, p, ncp, !vsplit);
-                if (n.left != null && ((p.y() - ny) < ncp.d))
+                if (n.left != null && ((d3 * d3) < ncp.d))
                     nearest(n.left, p, ncp, !vsplit);
             }
         }
diff --git a/Algorithms/Part-I/5-KdTrees/PointSET.java b/Algorithms/Part-I/5-KdTrees/PointSET.java
index f5594de..5500512 100644
--- a/Algorithms/Part-I/5-KdTrees/PointSET.java
+++ b/Algorithms/Part-I/5-KdTrees/PointSET.java
@@ -61,7 +61,7 @@ public class PointSET
         double d = Double.MAX_VALUE;
         for (Point2D o : set)
         {
-            double d2 = p.distanceTo(o);
+            double d2 = p.distanceSquaredTo(o);
             if (d2 < d) {
                 d = d2;
                 p0 = o;
-- 
cgit v1.1-2-g2b99