Incorrect volume estimate in Qhull.jl

General Usage
,
1

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?

2

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
3

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.

4

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

5

No problem. It already exceeds my limits :laughing:

1 Like
6

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

7

Another option: https://github.com/harveydevereux/AlphaShapes.jl

1 Like
8

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.

9

Thanks, Jeff. This looks promising.

10

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

11

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
12

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