Update KdTree tests.
[master-thesis.git] / Parasitemia / Tests / ParasitemiaCore.Tests / KdTreeTests.fs
1 namespace ParasitemiaCore.Tests
2
3 open Xunit
4 open Xunit.Abstractions
5
6 open ParasitemiaCore.KdTree
7
8 type Point (x : float32, y : float32) =
9 interface I2DCoords with
10 member this.X = x
11 member this.Y = y
12
13 override this.ToString () =
14 sprintf "(%.1f, %.1f)" x y
15
16 type KdTreeTests (output : ITestOutputHelper) =
17
18 // TODO: test with identical X or Y coords
19 [<Fact>]
20 member this.``Test`` () =
21 let pts =
22 [
23 Point (1.0f, 1.0f)
24 Point (2.0f, 2.0f)
25 Point (1.5f, 3.6f)
26 Point (3.0f, 3.2f)
27 Point (4.0f, 4.0f)
28 Point (3.5f, 1.5f)
29 Point (2.5f, 0.5f)
30 ]
31
32 let tree = Tree.BuildTree pts
33 output.WriteLine (sprintf "Tree: %A" tree)
34
35 let s1 = tree.Search { minX = 0.0f; maxX = 5.0f; minY = 0.0f; maxY = 5.0f } // All points.
36 output.WriteLine (sprintf "s1: %A" s1)
37
38 let s2 = tree.Search { minX = 2.8f; maxX = 4.5f; minY = 3.0f; maxY = 4.5f }
39 output.WriteLine (sprintf "s2: %A" s2)
40
41 let s3 = tree.Search { minX = 2.0f; maxX = 2.0f; minY = 2.0f; maxY = 2.0f }
42 output.WriteLine (sprintf "s3: %A" s3)
43
44 [<Fact>]
45 member this.``Test 2`` () =
46 let pts =
47 [
48 Point (1.0f, 1.0f)
49 Point (1.0f, 2.0f)
50 Point (1.0f, 3.0f)
51 ]
52
53 let tree = Tree.BuildTree pts
54 output.WriteLine (sprintf "Tree: %A" tree)
55
56 let s1 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 1.0f; maxY = 1.0f }
57 output.WriteLine (sprintf "s1: %A" s1)
58
59 let s2 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 2.0f; maxY = 2.0f }
60 output.WriteLine (sprintf "s2: %A" s2)
61
62 // This case result is wrong: FIXME
63 let s3 = tree.Search { minX = 1.0f; maxX = 1.0f; minY = 3.0f; maxY = 3.0f }
64 output.WriteLine (sprintf "s3: %A" s3)
65
66 let s4 = tree.Search { minX = 0.0f; maxX = 2.0f; minY = 0.0f; maxY = 4.0f }
67 output.WriteLine (sprintf "s4: %A" s4)
68
69 [<Fact>]
70 member this.``Benchmark`` () =
71 let min = -1_000.
72 let max = +1_000.
73 let windowSize = 10.
74 let nbPoints = 500_000
75 let n = 1_000
76
77 let rng = System.Random 42
78 let nextNumber (min : float) (max : float) =
79 (rng.NextDouble () * (max + abs min)) + min |> float32
80
81 let points =
82 [
83 for i = 1 to nbPoints do
84 let x = nextNumber min max
85 let y = nextNumber min max
86 yield Point (x, y)
87 ]
88
89 let sw = System.Diagnostics.Stopwatch ()
90 sw.Start ()
91
92 let tree = Tree.BuildTree points
93
94 sw.Stop ()
95 output.WriteLine (sprintf "Time to build = %A ms" sw.ElapsedMilliseconds)
96
97 sw.Restart ()
98
99 let mutable nbFound = 0
100 for i = 1 to n do
101 let minX = nextNumber min (max - windowSize)
102 let minY = nextNumber min (max - windowSize)
103 nbFound <- nbFound + (tree.Search { minX = minX; maxX = minX + float32 windowSize; minY = minY; maxY = minY + float32 windowSize } |> List.length)
104
105 sw.Stop ()
106 output.WriteLine (sprintf "nb found: %i. Time to search = %A ms" nbFound sw.ElapsedMilliseconds)
107
108
109