From 6e5558c4c38957622216de24f2d115a0da90cce6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Wed, 27 Mar 2013 09:33:52 +0100 Subject: Algorithms-I : 5-KdTrees: fix null pointer in KdTree --- Algorithms/Part-I/5-KdTrees/KdTree.java | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/Algorithms/Part-I/5-KdTrees/KdTree.java b/Algorithms/Part-I/5-KdTrees/KdTree.java index 73d9a90..bcf4609 100644 --- a/Algorithms/Part-I/5-KdTrees/KdTree.java +++ b/Algorithms/Part-I/5-KdTrees/KdTree.java @@ -100,7 +100,7 @@ public class KdTree // does the tree contain the point p? public boolean contains(Point2D p) { - if (root == null) return false; + if ((p == null) || (root == null)) return false; return get(root, p, true); } @@ -113,7 +113,11 @@ public class KdTree cmp = Point2D.Y_ORDER.compare(p, n.p); if (cmp < 0) + { + if (n.left == null) return false; return get(n.left, p, !vsplit); + } + if (n.right == null) return false; return get(n.right, p, !vsplit); } @@ -163,6 +167,8 @@ public class KdTree { Stack stack = new Stack(); + if ((rect == null) || (root == null)) return stack; + range(root, rect, stack, true); return stack; @@ -191,10 +197,11 @@ public class KdTree // a nearest neighbor in the tree to p; null if tree is empty public Point2D nearest(Point2D p) { - if (p == null) return null; - if (root == null) return null; + if ((p == null) || (root == null)) return null; + NearestChampion ncp = new NearestChampion(null, Double.MAX_VALUE); nearest(root, p, ncp, true); + return ncp.p; } -- cgit v1.1-2-g2b99