Splitting algorithm does not handle equal coordinates properly

[aplusm]

I further investigate Issue #17 by looking at the code and discover that splitting algorithm was at the root of this issue.

More precisely, this piece of code is where the problem occurs :

let sortedValues = values.sorted { (a, b) -> Bool in
                return a.kdDimension(currentSplittingDimension) < b.kdDimension(currentSplittingDimension)
            }

let median = sortedValues.count / 2
let leftTree = KDTree(values: Array(sortedValues[0..<median]), depth: depth+1)
let rightTree = KDTree(values: Array(sortedValues[median+1..<sortedValues.count]), depth: depth+1)      

To simplify, let's say we'll split along x-axis. (currentSplittingDimension = 0)

The leftTree should contains all points whose x-coordinate is strictly less than x-coordinate of median value, which is not enforced by this algorithm, if some points share an identical x-coordinate.

This approach, even if not optimal, is a simple way of fixing this issue (untested) :

let splitMedianValue = sortedValues[median].kdDimension(0)
let leftValues = sortedValues.filter({ (point) -> Bool in
            return point.kdDimension(0) < splitMedianValue
 })

let leftTree = KDTree(values: leftValues, depth: depth+1)

This should replace the fixed push for Issue #17 in contains which is not optimal (traversing left AND right) for nearly equal coordinate.

This will also fixed the remove issue (see my last comments on Issue #17 )

[Bersaelor]

Feel free to open a Pull-Request :)

[aplusm]

I opened pullRequest #22

[Bersaelor]

Splendid, thank you for opening the PR and solving the issue.

That gave me the time to work on the serialization/deserialization issue.