Index: src/Common/NetTopologySuite/Index/KdTree/KdTree.cs =================================================================== diff -u -r8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9 -r5fc71a385897af92ccb092f2f969b5709afab85a --- src/Common/NetTopologySuite/Index/KdTree/KdTree.cs (.../KdTree.cs) (revision 8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9) +++ src/Common/NetTopologySuite/Index/KdTree/KdTree.cs (.../KdTree.cs) (revision 5fc71a385897af92ccb092f2f969b5709afab85a) @@ -20,20 +20,18 @@ public class KdTree where T : class { + private readonly double _tolerance; private KdNode _root; // ReSharper disable once UnusedField.Compiler - private KdNode _last = null; + private readonly KdNode _last = null; private long _numberOfNodes; - private readonly double _tolerance; /// /// Creates a new instance of a KdTree with a snapping tolerance of 0.0. /// (I.e. distinct points will not be snapped) /// public KdTree() - : this(0.0) - { - } + : this(0.0) {} /// /// Creates a new instance of a KdTree, specifying a snapping distance tolerance. @@ -53,13 +51,14 @@ { get { - if (_root == null) return true; + if (_root == null) + { + return true; + } return false; } } - - /// /// Inserts a new point in the kd-tree, with no data. /// @@ -126,8 +125,8 @@ } leafNode = currentNode; currentNode = isLessThan - ? currentNode.Left - : currentNode.Right; + ? currentNode.Left + : currentNode.Right; isOddLevel = !isOddLevel; } @@ -148,13 +147,52 @@ return node; } + /// + /// Performs a range search of the points in the index. + /// + /// The range rectangle to query + /// A collection of the KdNodes found + public ICollection> Query(Envelope queryEnv) + { + KdNode last = null; + ICollection> result = new Collection>(); + QueryNode(_root, _last, queryEnv, true, result); + return result; + } + + /// + /// Performs a range search of the points in the index. + /// + /// The range rectangle to query + /// A collection to accumulate the result nodes into + public void Query(Envelope queryEnv, ICollection> result) + { + QueryNode(_root, _last, queryEnv, true, result); + } + + /// + /// Performs a nearest neighbor search of the points in the index. + /// + /// The point to search the nearset neighbor for + public KdNode NearestNeighbor(ICoordinate coord) + { + KdNode result = null; + var closestDistSq = double.MaxValue; + NearestNeighbor(_root, _last, coord, ref result, ref closestDistSq); + return result; + } + private static void QueryNode(KdNode currentNode, KdNode bottomNode, - Envelope queryEnv, bool odd, ICollection> result) + Envelope queryEnv, bool odd, ICollection> result) { if (currentNode == null) + { return; + } if (currentNode == bottomNode) + { return; + } double min; double max; @@ -186,43 +224,22 @@ { QueryNode(currentNode.Right, bottomNode, queryEnv, !odd, result); } - } - /// - /// Performs a range search of the points in the index. - /// - /// The range rectangle to query - /// A collection of the KdNodes found - public ICollection> Query(Envelope queryEnv) - { - KdNode last = null; - ICollection> result = new Collection>(); - QueryNode(_root, _last, queryEnv, true, result); - return result; - } - - /// - /// Performs a range search of the points in the index. - /// - /// The range rectangle to query - /// A collection to accumulate the result nodes into - public void Query(Envelope queryEnv, ICollection> result) - { - QueryNode(_root, _last, queryEnv, true, result); - } - private static void NearestNeighbor(KdNode currentNode, KdNode bottomNode, - ICoordinate queryCoordinate, ref KdNode closestNode, ref double closestDistanceSq) + ICoordinate queryCoordinate, ref KdNode closestNode, ref double closestDistanceSq) { while (true) { if (currentNode == null) + { return; + } if (currentNode == bottomNode) + { return; + } - var distSq = Math.Pow(currentNode.X - queryCoordinate.X, 2) + Math.Pow(currentNode.Y - queryCoordinate.Y, 2); @@ -232,21 +249,24 @@ closestDistanceSq = distSq; } - var searchLeft = false; var searchRight = false; if (currentNode.Left != null) + { searchLeft = (Math.Pow(currentNode.Left.X - queryCoordinate.X, 2) + Math.Pow(currentNode.Left.Y - queryCoordinate.Y, 2)) < closestDistanceSq; + } if (currentNode.Right != null) + { searchRight = (Math.Pow(currentNode.Right.X - queryCoordinate.X, 2) + Math.Pow(currentNode.Right.Y - queryCoordinate.Y, 2)) < closestDistanceSq; + } if (searchLeft) { NearestNeighbor(currentNode.Left, bottomNode, queryCoordinate, ref closestNode, - ref closestDistanceSq); + ref closestDistanceSq); } if (searchRight) @@ -257,18 +277,5 @@ break; } } - - /// - /// Performs a nearest neighbor search of the points in the index. - /// - /// The point to search the nearset neighbor for - public KdNode NearestNeighbor(ICoordinate coord) - { - KdNode result = null; - var closestDistSq = double.MaxValue; - NearestNeighbor(_root, _last, coord, ref result, ref closestDistSq); - return result; - } - } } \ No newline at end of file