Error: Unable to construct concave hull

[henry2004y]

Hi,

I have encountered the error message Unable to construct concave hull, but I don't understand the reason. Here is the script:

using DelimitedFiles, ConcaveHull

points = readdlm("points.txt", ',', header=true)[1]

v = [[points[i,1], points[i,2]] for i in 1:size(points,1)]

hull = concave_hull(v)

#using PyPlot
#scatter(points[:,1],points[:,2])

When I tried with some random points in a ring which looks similar to the attached data using the following script

using PyPlot, ConcaveHull
function ringpoints(lo::Integer, hi::Integer, ndots::Integer)
   canvas = zeros(2,ndots)
   i = 0
   while i < ndots
      r = rand()*(hi-lo) + lo
      θ = rand()*2π
      x = r*cos(θ)
      y = r*sin(θ)
      canvas[:,i+1] = [x, y]
      i += 1
   end
   return canvas
end

points = ringpoints(3,6,2000)
scatter(points[1,:], points[2,:])
v = [[points[1,i], points[2,i]] for i = 1:size(points,2)]
hull = concave_hull(v)

it just works fine.

So what is the problem with my data? Is there any constraint?

Thanks!

points.txt

[lstagner]

You are probably running in same problem as Issue #3

[henry2004y]

Thanks for your quick response! I really appreciate it!

Yes you are right, it's probably a similar issue. If I add a small perturbation to each data point, it works fine. I would suggest a slightly modified error message for this issue, to make it more clear.

However, I check again my data points to see if there are actually any duplicates:

using DelimitedFiles
points = readdlm("points.txt", ',', header=true)[1]
const ϵ = 1e-3
index = []
# check duplicate points!
for i=1:size(points,1)
   for j=i+1:size(points,1)
      if abs(points[j,1] - points[i,1]) < ϵ && abs(points[j,2] - points[i,2]) < ϵ
         push!(index, (i,j))
      end
   end
end

It returned nothing. This is very strange. What I can tell is that some points on the outer boundary have the same x or y coordinates, but will that affect the concave hull calculation?

[lstagner]

The issue is that there are more than 3 points that are co-linear with the edges of the concave hull. I have fixed the issue on master and it works with your data although you may want to use smooth out the hull by increasing the number of neighbors used.