Incorrect volume estimate in Qhull.jl

I am trying to use QHull.jl to estimate the volume of points in high dimensional space. Unfortunately, some of the results from simple 2D examples seem to be in correct.

Here is a MWE:

using Plots, QHull, Random

Random.seed!(3325)

points1 = rand(10000, 2)

# shift the second set of points up and to the right

points2 = rand(10000, 2) .+ .9

points3 = vcat(points1, points2)

hull = chull(points3)

# expected result 1 + 1 - .1^2 = 1.99

# obtained result ≈ 2.78

print(hull.volume)

scatter(points3[:,1], points3[:,2], leg=false, grid=false)

Here is the plot:

area

What is going wrong?

That computes the volume of the convex hull of the points: Convex hull - Wikipedia

The convex hull of those two squares has area 1.9^2 - 0.9^2 = 2.8.

2 Likes

Ah ok. I see. Thanks for clarifying

Do you know of a way to estimate the volume of arbitrary shapes? In my use case, I do not know what the shape will be.

Sorry convex hulls are about the limit of my geometry knowledge!

No problem. It already exceeds my limits :laughing:

1 Like

You seem to need a concave hull.
Check ConcaveHull.jl for a 2D implementation.

Another option: GitHub - harveydevereux/AlphaShapes.jl: Basic implementation of alpha shapes

1 Like

Thanks for the lead. I did come across that before finding QHull.jl, but my particular use case is multidimensional and might be concave or convex.

Thanks, Jeff. This looks promising.

Do you happen to know the status of AlphaShapes.jl? Currently, it is unregistered.

Nope, I recognized your problem as one addressed by alpha shapes, so I googled for “alpha shapes julia”. There may be other implementations.

1 Like

Thank you. It’s good to know that alpha shapes is a relevant search term.