module ParasitemiaCore.KdTree
open System
+open System.Collections.Generic
type I2DCoords =
abstract X : 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 -> 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
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))