sqrt error with knn on BallTree

[mkborregaard]

I'm trying to get nearest neighbours with Haversine distances. I use these two .asc (delimited) files:
current: https://www.dropbox.com/s/egfv2tjhbjwacl4/PresentDaySpeciesOverlap.asc?dl=0
future: https://www.dropbox.com/s/r8mirakim75utyd/Future2080SpeciesOverlap.asc?dl=0

It's hard to make the MWE really minimal:

import DelimitedFiles: readdlm, writedlm
import NearestNeighbors: BallTree, knn
import Distances: Haversine

current = replace!(readdlm("PresentDaySpeciesOverlap.asc", ' ', skipstart = 6), -9999=>NaN)
future = replace!(readdlm("Future2080SpeciesOverlap.asc", ' ', skipstart = 6), -9999=>NaN)

present = [[x[1], x[2]] for x in CartesianIndices(current) if current[x] == 1]
potential = [[x[1], x[2]] for x in CartesianIndices(current) if current[x] == 0 && future[x] == 1]

tree = BallTree(float(reduce(hcat, present)), Haversine(6371))
inds, dists = knn(tree, float(reduce(hcat, potential)), 1) #errors

The error message is

DomainError with -5.551115123125783e-17:
sqrt will only return a complex result if called with a complex argument. Try sqrt(Complex(x)).
throw_complex_domainerror(::Symbol, ::Float64) at math.jl:32
sqrt at math.jl:492 [inlined]
(::Haversine{Int64})(::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::StaticArrays.SArray{Tuple{2},Float64,1,2}) at haversine.jl:33
add_points_knn! at generic.jl:24 [inlined]
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:161
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:173
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:180
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:180
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:180
knn_kernel!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Int64, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::typeof(NearestNeighbors.always_false)) at ball_tree.jl:178
_knn(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Array{Int64,1}, ::Array{Float64,1}, ::Function) at ball_tree.jl:148
knn_point!(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::StaticArrays.SArray{Tuple{2},Float64,1,2}, ::Bool, ::Array{Float64,1}, ::Array{Int64,1}, ::Function) at knn.jl:30
knn(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Array{StaticArrays.SArray{Tuple{2},Float64,1,2},1}, ::Int64, ::Bool, ::Function) at knn.jl:22
knn(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Array{Float64,2}, ::Int64, ::Bool, ::Function) at knn.jl:55
knn(::BallTree{StaticArrays.SArray{Tuple{2},Float64,1,2},2,Float64,Haversine{Int64}}, ::Array{Float64,2}, ::Int64) at knn.jl:48
getdists(::Array{Float64,2}, ::Array{Float64,2}) at dist.jl:14
top-level scope at dist.jl:23

Seems like some 0 distance is interpreted as a small (<eps) negative number.

[KristofferC]

Put a debug printout at

NearestNeighbors.jl/src/tree_ops.jl

Line 99 in 8d9db7a

dist_d = evaluate(tree.metric, tree.data[idx], point, do_end)

and then file a bug report with the two points to Distances for producing negative distance between two points?

[mkborregaard]

sure let me try

[mkborregaard]

got it