diff options
| author | Jérémy Zurcher <jeremy@asynk.ch> | 2013-03-27 12:44:06 +0100 |
|---|---|---|
| committer | Jérémy Zurcher <jeremy@asynk.ch> | 2013-11-15 17:38:45 +0100 |
| commit | 883262806aaa1deacd1e1482e2136f8857e515ed (patch) | |
| tree | 72b87f3f9c5b5073264894310b1a54c3bfbc722c | |
| parent | 6e5558c4c38957622216de24f2d115a0da90cce6 (diff) | |
| download | coursera-883262806aaa1deacd1e1482e2136f8857e515ed.zip coursera-883262806aaa1deacd1e1482e2136f8857e515ed.tar.gz | |
Algorithms-I : 5-KdTrees: speed up maths
| -rw-r--r-- | Algorithms/Part-I/5-KdTrees/KdTree.java | 18 | ||||
| -rw-r--r-- | 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; |