diff options
Diffstat (limited to 'Algorithms')
| -rw-r--r-- | Algorithms/Part-I/5-KdTrees/KdTree.java | 44 |
1 files changed, 23 insertions, 21 deletions
diff --git a/Algorithms/Part-I/5-KdTrees/KdTree.java b/Algorithms/Part-I/5-KdTrees/KdTree.java index 3607976..d0c0fcd 100644 --- a/Algorithms/Part-I/5-KdTrees/KdTree.java +++ b/Algorithms/Part-I/5-KdTrees/KdTree.java @@ -192,13 +192,15 @@ public class KdTree return nearest(root, p, null, Double.MAX_VALUE, true); } - private Point2D nearest(Node n, Point2D p, Point2D ncp, double d, boolean vsplit) + private Point2D nearest(Node n, Point2D p, Point2D cp, double d, boolean vsplit) { + Point2D cp0 = cp; + double d1 = d; double d2 = p.distanceSquaredTo(n.p); - if (d2 < d) + if (d2 < d1) { - ncp = n.p; - d = d2; + cp0 = n.p; + d1 = d2; } if (vsplit) @@ -208,21 +210,21 @@ public class KdTree { if (n.left != null) { - ncp = nearest(n.left, p, ncp, d, !vsplit); - d = p.distanceSquaredTo(ncp); + cp0 = nearest(n.left, p, cp0, d1, !vsplit); + d1 = p.distanceSquaredTo(cp0); } - if (n.right != null && ((d2 * d2) < d)) - ncp = nearest(n.right, p, ncp, d, !vsplit); + if (n.right != null && ((d2 * d2) < d1)) + cp0 = nearest(n.right, p, cp0, d1, !vsplit); } else { if (n.right != null) { - ncp = nearest(n.right, p, ncp, d, !vsplit); - d = p.distanceSquaredTo(ncp); + cp0 = nearest(n.right, p, cp0, d1, !vsplit); + d1 = p.distanceSquaredTo(cp0); } - if (n.left != null && ((d2 * d2) < d)) - ncp = nearest(n.left, p, ncp, d, !vsplit); + if (n.left != null && ((d2 * d2) < d1)) + cp0 = nearest(n.left, p, cp0, d1, !vsplit); } } else @@ -232,24 +234,24 @@ public class KdTree { if (n.left != null) { - ncp = nearest(n.left, p, ncp, d, !vsplit); - d = p.distanceSquaredTo(ncp); + cp0 = nearest(n.left, p, cp0, d1, !vsplit); + d1 = p.distanceSquaredTo(cp0); } - if (n.right != null && ((d2 * d2) < d)) - ncp = nearest(n.right, p, ncp, d, !vsplit); + if (n.right != null && ((d2 * d2) < d1)) + cp0 = nearest(n.right, p, cp0, d1, !vsplit); } else { if (n.right != null) { - ncp = nearest(n.right, p, ncp, d, !vsplit); - d = p.distanceSquaredTo(ncp); + cp0 = nearest(n.right, p, cp0, d1, !vsplit); + d1 = p.distanceSquaredTo(cp0); } - if (n.left != null && ((d2 * d2) < d)) - ncp = nearest(n.left, p, ncp, d, !vsplit); + if (n.left != null && ((d2 * d2) < d1)) + cp0 = nearest(n.left, p, cp0, d1, !vsplit); } } - return ncp; + return cp0; } } |