X-Git-Url: http://git.euphorik.ch/?p=master-thesis.git;a=blobdiff_plain;f=Parasitemia%2FParasitemiaCore%2FKdTree.fs;h=ec21a0f35d28491dd91c40149f26ee1a3363d896;hp=4e20f242497135266d6fedac3b6d47f18122ceaf;hb=6250f10c807301a760b8659f9c00ca6dbbd4c7b7;hpb=b87b35b922551f122228df1fd9c530bbb807935a

diff --git a/Parasitemia/ParasitemiaCore/KdTree.fs b/Parasitemia/ParasitemiaCore/KdTree.fs
index 4e20f24..ec21a0f 100644
--- a/Parasitemia/ParasitemiaCore/KdTree.fs
+++ b/Parasitemia/ParasitemiaCore/KdTree.fs
@@ -1,6 +1,7 @@
 module ParasitemiaCore.KdTree
 
 open System
+open System.Collections.Generic
 
 type I2DCoords =
     abstract X : float32
@@ -8,17 +9,17 @@ type I2DCoords =
 
 // Compare 'e1' and 'e2' by X.
 let cmpX (e1 : I2DCoords) (e2 : I2DCoords) : int =
-    match e1.X.CompareTo(e2.X) with
-    | 0 -> match e1.Y.CompareTo(e2.Y) with
-           | 0 -> e1.GetHashCode().CompareTo(e2.GetHashCode())
+    match e1.X.CompareTo e2.X with
+    | 0 -> match e1.Y.CompareTo e2.Y with
+           | 0 -> e1.GetHashCode().CompareTo (e2.GetHashCode ())
            | v -> v
     | v -> v
 
 // Compare 'e1' and 'e2' by Y.
 let cmpY (e1 : I2DCoords) (e2 : I2DCoords) : int =
-    match e1.Y.CompareTo(e2.Y) with
-    | 0 -> match e1.X.CompareTo(e2.X) with
-           | 0 -> e1.GetHashCode().CompareTo(e2.GetHashCode())
+    match e1.Y.CompareTo e2.Y with
+    | 0 -> match e1.X.CompareTo e2.X with
+           | 0 -> e1.GetHashCode().CompareTo (e2.GetHashCode ())
            | v -> v
     | v -> v
 
@@ -62,7 +63,40 @@ type Tree<'a when 'a :> I2DCoords> =
 
         buildTreeFromSortedArray xSorted ySorted 1
 
-    member this.Search (searchRegion : Region) : 'a list =
+    member this.Search (searchRegion : Region) : List<'a> =
+        let result = List<'a> ()
+        let rec valuesFrom (tree : Tree<'a>) =
+            match tree with
+            | Node (_, left, right) ->
+                valuesFrom right
+                valuesFrom left
+            | Leaf v ->
+                result.Add v
+
+        let rec searchWithRegion (tree : Tree<'a>) (currentRegion : Region) (depth : int) =
+            match tree with
+            | Leaf v ->
+                if searchRegion.Contains v.X v.Y then
+                    result.Add v
+            | Node (splitValue, part1, part2) ->
+                let inline valuesInRegion (region : Region) (treeRegion : Tree<'a>) =
+                    if region.IsSub searchRegion then
+                        valuesFrom treeRegion
+                    elif region.Intersects searchRegion then
+                        searchWithRegion treeRegion region (depth + 1)
+
+                if depth % 2 = 1 then // Vertical splitting.
+                    valuesInRegion { currentRegion with maxX = splitValue } part1 // Left region.
+                    valuesInRegion { currentRegion with minX = splitValue } part2 // Right region.
+                else // Horizontal splitting.
+                    valuesInRegion { currentRegion with maxY = splitValue } part1 // Down region.
+                    valuesInRegion { currentRegion with minY = splitValue } part2 // Up region.
+
+        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))
@@ -90,63 +124,3 @@ type Tree<'a when 'a :> I2DCoords> =
                     (valuesInRegion downRegion part1) @ (valuesInRegion upRegion part2)
 
         searchWithRegion this { minX = Single.MinValue; maxX = Single.MaxValue; minY = Single.MinValue; maxY = Single.MaxValue } 1
-
-///// Tests. TODO: to put in a unit test.
-
-type Point (x : float32, y : float32) =
-    interface I2DCoords with
-        member this.X = x
-        member this.Y = y
-
-    override this.ToString () =
-        sprintf "(%.1f, %.1f)" x y
-
-// TODO: test with identical X or Y coords
-let test () =
-    let pts =
-        [
-            Point(1.0f, 1.0f)
-            Point(2.0f, 2.0f)
-            Point(1.5f, 3.6f)
-            Point(3.0f, 3.2f)
-            Point(4.0f, 4.0f)
-            Point(3.5f, 1.5f)
-            Point(2.5f, 0.5f)
-        ]
-
-    let tree = Tree.BuildTree pts
-    Utils.dprintfn "Tree: %A" tree
-
-    let s1 = tree.Search { minX = 0.0f; maxX = 5.0f; minY = 0.0f; maxY = 5.0f } // All points.
-    Utils.dprintfn "s1: %A" s1
-
-    let s2 = tree.Search { minX = 2.8f; maxX = 4.5f; minY = 3.0f; maxY = 4.5f }
-    Utils.dprintfn "s2: %A" s2
-
-    let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f }
-    Utils.dprintfn "s3: %A" s3
-
-let test2 () =
-    let pts =
-        [
-            Point(1.0f, 1.0f)
-            Point(1.0f, 2.0f)
-            Point(1.0f, 3.0f)
-        ]
-
-    let tree = Tree.BuildTree pts
-    Utils.dprintfn "Tree: %A" tree
-
-    let s1 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 1.0f; maxY = 1.0f }
-    Utils.dprintfn "s1: %A" s1
-
-    let s2 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 2.0f; maxY = 2.0f }
-    Utils.dprintfn "s2: %A" s2
-
-    // This case result is wrong: FIXME
-    let s3 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 3.0f; maxY = 3.0f }
-    Utils.dprintfn "s3: %A" s3
-
-    let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f }
-    Utils.dprintfn "s4: %A" s4
-