Stackoverflow error on a particular data set

[richardbuckalew]

This is a very useful package and I am glad it exists! However, I am running into an issue that prevents me from using it on my current problem.

I am generating concave hulls for geographical areas defined as a set of points. My data looks something like this:

10774-element Vector{Vector{Float64}}: [-81.63708721383487, 41.507421718898236] [-81.67480512381863, 41.49937078401172] [-81.52623304669797, 41.3797972072863] [-81.52928635788142, 41.52610608166444] [-81.76827514216981, 41.394218430091435] [-81.63467143712768, 41.48253201219702] ⋮ [-81.7002780693197, 41.35709503926154] [-81.650521058994, 41.497859911135556] [-81.63580570919844, 41.52793109388903] [-81.63667541801959, 41.524631468946836] [-81.7303254328199, 41.44382664262665] [-81.61037392565544, 41.50488520134781]

I have 15 such areas, and running ConcaveHull.concave_hull(data) works (very quickly!) for some of them, and apparently gets caught in an infinite recursion in others, returning a StackOverflowError:

ERROR: StackOverflowError: Stacktrace: [1] knn_kernel!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, index::Int64, point::StaticArrays.SVector{2, Float64}, best_idxs::Vector{Int64}, best_dists::Vector{Float64}, min_dist::Float64, skip::ConcaveHull.var"#2#6"{Vector{Bool}}) @ NearestNeighbors C:\Users\richa\.julia\packages\NearestNeighbors\LQ0xY\src\kd_tree.jl:171 [2] knn_kernel!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, index::Int64, point::StaticArrays.SVector{2, Float64}, best_idxs::Vector{Int64}, best_dists::Vector{Float64}, min_dist::Float64, skip::ConcaveHull.var"#2#6"{Vector{Bool}}) (repeats 8 times) @ NearestNeighbors C:\Users\richa\.julia\packages\NearestNeighbors\LQ0xY\src\kd_tree.jl:202 [3] _knn(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, point::StaticArrays.SVector{2, Float64}, best_idxs::Vector{Int64}, best_dists::Vector{Float64}, skip::ConcaveHull.var"#2#6"{Vector{Bool}}) @ NearestNeighbors C:\Users\richa\.julia\packages\NearestNeighbors\LQ0xY\src\kd_tree.jl:165 [4] knn_point!(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, point::StaticArrays.SVector{2, Float64}, sortres::Bool, dist::Vector{Float64}, idx::Vector{Int64}, skip::ConcaveHull.var"#2#6"{Vector{Bool}}) @ NearestNeighbors C:\Users\richa\.julia\packages\NearestNeighbors\LQ0xY\src\knn.jl:32 [5] knn(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, point::StaticArrays.SVector{2, Float64}, k::Int64, sortres::Bool, skip::ConcaveHull.var"#2#6"{Vector{Bool}}) @ NearestNeighbors C:\Users\richa\.julia\packages\NearestNeighbors\LQ0xY\src\knn.jl:46 [6] concave_hull(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, k::Int64) @ ConcaveHull C:\Users\richa\.julia\packages\ConcaveHull\vMk2U\src\concave_hull.jl:81 [7] concave_hull(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, k::Int64) (repeats 538 times) @ ConcaveHull C:\Users\richa\.julia\packages\ConcaveHull\vMk2U\src\concave_hull.jl:106 [8] concave_hull(tree::NearestNeighbors.KDTree{StaticArrays.SVector{2, Float64}, Distances.Euclidean, Float64}, k::Int64) (repeats 4477 times) @ ConcaveHull C:\Users\richa\.julia\packages\ConcaveHull\vMk2U\src\concave_hull.jl:123 [9] concave_hull(points::Vector{Vector{Float64}}, k::Int64) @ ConcaveHull C:\Users\richa\.julia\packages\ConcaveHull\vMk2U\src\concave_hull.jl:135 [10] getPlanBounds(df::DataFrame, planName::Symbol) @ Main c:\Users\richa\xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\_work\main.jl:35 [11] top-level scope @ REPL[24]:1

I'm sure the above is not enough for you to diagnose the problem, if it's not known to you, but maybe you guys know of something I might try?

Thanks!

[Sov-trotter]

Facing similar issue for yet another dataset. We you able to find a solution? Any alternatives?

[richardbuckalew]

No solution because concave hulls didn't end up being my best solution anyway. But I did identify the source of the error: one of my data points was too far away from the rest of the set. I don't remember any of the details now but I recall that it's a standard algorithm and so it wouldn't be too hard to make a fix.