X-Git-Url: http://git.euphorik.ch/?p=master-thesis.git;a=blobdiff_plain;f=Parasitemia%2FParasitemia%2FKdTree.fs;h=7da0255ef02fa4e0c9c3a5ebed21b0a2d9f89027;hp=dd0247ab029eda4592472247bc54aafcbb9a868e;hb=044b0ae69df3ac565432545b2fa934589016f9bd;hpb=dec96d50e56e1932bbfa09e6bedf90d6b707ccbd diff --git a/Parasitemia/Parasitemia/KdTree.fs b/Parasitemia/Parasitemia/KdTree.fs index dd0247a..7da0255 100644 --- a/Parasitemia/Parasitemia/KdTree.fs +++ b/Parasitemia/Parasitemia/KdTree.fs @@ -3,43 +3,43 @@ open System type I2DCoords = - abstract X : float - abstract Y : float + abstract X : float32 + abstract Y : float32 // 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 -> 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 -> match e1.X.CompareTo(e2.X) with | 0 -> e1.GetHashCode().CompareTo(e2.GetHashCode()) | v -> v | v -> v -type Region = { minX: float; maxX: float; minY: float; maxY: float } with +type Region = { minX: float32; maxX: float32; minY: float32; maxY: float32 } with member this.Contains px py : bool = - px >= this.minX && px <= this.maxX && + px >= this.minX && px <= this.maxX && py >= this.minY && py <= this.maxY member this.IsSub otherRegion : bool = - this.minX >= otherRegion.minX && this.maxX <= otherRegion.maxX && + this.minX >= otherRegion.minX && this.maxX <= otherRegion.maxX && this.minY >= otherRegion.minY && this.maxY <= otherRegion.maxY - member this.Intersects otherRegion : bool = + member this.Intersects otherRegion : bool = this.minX < otherRegion.maxX && this.maxX >= otherRegion.minX && this.minY < otherRegion.maxY && this.maxY >= otherRegion.minY -type Tree<'a when 'a :> I2DCoords> = - | Node of float * Tree<'a> * Tree<'a> +type Tree<'a when 'a :> I2DCoords> = + | Node of float32 * Tree<'a> * Tree<'a> | Leaf of 'a - static member buildTree (l: 'a list) : Tree<'a> = + static member BuildTree (l: 'a list) : Tree<'a> = let xSorted = List.toArray l let ySorted = List.toArray l Array.sortInPlaceWith cmpX xSorted @@ -47,11 +47,11 @@ type Tree<'a when 'a :> I2DCoords> = let rec buildTreeFromSortedArray (pXSorted: 'a[]) (pYSorted: 'a[]) (depth: int) : Tree<'a> = if pXSorted.Length = 1 - then + then Leaf pXSorted.[0] - else + else if depth % 2 = 1 // 'depth' is odd -> vertical splitting else horizontal splitting. - then + then let leftX, rightX = Array.splitAt ((pXSorted.Length + 1) / 2) pXSorted let splitElement = Array.last leftX let leftY, rightY = Array.partition (fun (e: 'a) -> cmpX e splitElement <= 0) pYSorted // FIXME: Maybe this operation can be optimized. @@ -64,7 +64,7 @@ type Tree<'a when 'a :> I2DCoords> = buildTreeFromSortedArray xSorted ySorted 1 - static member search (tree: Tree<'a>) (searchRegion: Region) : 'a list = + member this.Search (searchRegion: Region) : 'a list = let rec valuesFrom (tree: Tree<'a>) : 'a list = match tree with | Leaf v -> [v] @@ -74,32 +74,32 @@ type Tree<'a when 'a :> I2DCoords> = 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>) = + 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 + else [] if depth % 2 = 1 // Vertical splitting. - then - let leftRegion = { currentRegion with maxX = splitValue } + then + 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 downRegion = { currentRegion with maxY = splitValue } let upRegion = { currentRegion with minY = splitValue } (valuesInRegion downRegion part1) @ (valuesInRegion upRegion part2) - - searchWithRegion tree { minX = Double.MinValue; maxX = Double.MaxValue; minY = Double.MinValue; maxY = Double.MaxValue } 1 - - + + 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: float, y: float) = +type Point (x: float32, y: float32) = interface I2DCoords with member this.X = x member this.Y = y @@ -108,47 +108,47 @@ type Point (x: float, y: float) = sprintf "(%.1f, %.1f)" x y // TODO: test with identical X or Y coords -let test () = +let test () = let pts = [ - Point(1.0, 1.0) - Point(2.0, 2.0) - Point(1.5, 3.6) - Point(3.0, 3.2) - Point(4.0, 4.0) - Point(3.5, 1.5) - Point(2.5, 0.5) ] - - let tree = Tree.buildTree 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 tree { minX = 0.0; maxX = 5.0; minY = 0.0; maxY = 5.0 } // All points. + 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 tree { minX = 2.8; maxX = 4.5; minY = 3.0; maxY = 4.5 } + 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 tree { minX = 2.0; maxX = 2.0; minY = 2.0; maxY = 2.0 } + + let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f } Utils.dprintfn "s3: %A" s3 -let test2 () = +let test2 () = let pts = [ - Point(1.0, 1.0) - Point(1.0, 2.0) - Point(1.0, 3.0) ] - - let tree = Tree.buildTree 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 tree { minX = 1.0; maxX = 1.0; minY = 1.0; maxY = 1.0 } + + 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 tree { minX = 1.0; maxX = 1.0; minY = 2.0; maxY = 2.0 } + 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 tree { minX = 1.0; maxX = 1.0; minY = 3.0; maxY = 3.0 } + 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 tree { minX = 0.0; maxX = 2.0; minY = 0.0; maxY = 4.0 } + let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f } Utils.dprintfn "s4: %A" s4 - +