Add the old search for kdTree + benchmark project

[master-thesis.git] / Parasitemia / ParasitemiaCore / KdTree.fs

diff --git a/Parasitemia/ParasitemiaCore/KdTree.fs b/Parasitemia/ParasitemiaCore/KdTree.fs
index 3a51aac..ec21a0f 100644 (file)
--- a/Parasitemia/ParasitemiaCore/KdTree.fs
+++ b/Parasitemia/ParasitemiaCore/KdTree.fs
@@ -94,3 +94,33 @@ type Tree<'a when 'a :> I2DCoords> =
 
         searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1
         result
+
+    [<Obsolete>]
+    member this.SearchOld (searchRegion : Region) : 'a list =
+        let rec valuesFrom (tree : Tree<'a>) (acc : 'a list) : 'a list =
+            match tree with
+            | Node (_, left, right) -> (valuesFrom right (valuesFrom left acc))
+            | Leaf v -> v :: acc
+
+        let rec searchWithRegion (tree : Tree<'a>) (currentRegion : Region) (depth : int) : 'a list =
+            match tree with
+            | Leaf v -> if searchRegion.Contains v.X v.Y then [v] else []
+            | Node (splitValue, part1, part2) ->
+                let valuesInRegion (region : Region) (treeRegion : Tree<'a>) =
+                    if region.IsSub searchRegion then
+                        valuesFrom treeRegion []
+                    elif region.Intersects searchRegion then
+                        searchWithRegion treeRegion region (depth + 1)
+                    else
+                        []
+
+                if depth % 2 = 1 then // Vertical splitting.
+                    let leftRegion = { currentRegion with maxX = splitValue }
+                    let rightRegion = { currentRegion with minX = splitValue }
+                    (valuesInRegion leftRegion part1) @ (valuesInRegion rightRegion part2)
+                else // Horizontal splitting.
+                    let downRegion = { currentRegion with maxY = splitValue }
+                    let upRegion = { currentRegion with minY = splitValue }
+                    (valuesInRegion downRegion part1) @ (valuesInRegion upRegion part2)
+
+        searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1