# Incorrect volume estimate in Qhull.jl

**URL:** <https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622>\
**Category:** General Usage\
**Tags:** question, convex-hull\
**Created:** [January 14, 2022, 1:40pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622 "2022-01-14T13:40:31Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 1:40pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/1 "2022-01-14T13:40:31Z")

</div>

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:

```julia
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](https://global.discourse-cdn.com/julialang/original/3X/2/3/23135931c830ac963237bc246d6181ea316c2414.png)

What is going wrong?

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [January 14, 2022, 2:28pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/2 "2022-01-14T14:28:40Z")

</div>

That computes the volume of the convex hull of the points: [Convex hull - Wikipedia](https://en.wikipedia.org/wiki/Convex_hull)

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

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 2:32pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/3 "2022-01-14T14:32:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [January 14, 2022, 3:37pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/4 "2022-01-14T15:37:12Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 3:40pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/5 "2022-01-14T15:40:04Z")

</div>

No problem. It already exceeds my limits 😆

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 14, 2022, 3:44pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/6 "2022-01-14T15:44:31Z")

</div>

You seem to need a concave hull.  
Check [ConcaveHull.jl](https://github.com/lstagner/ConcaveHull.jl) for a 2D implementation.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [January 14, 2022, 3:47pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/7 "2022-01-14T15:47:23Z")

</div>

Another option: [https://github.com/harveydevereux/AlphaShapes.jl](https://github.com/harveydevereux/AlphaShapes.jl)

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 3:47pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/8 "2022-01-14T15:47:38Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 3:49pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/9 "2022-01-14T15:49:32Z")

</div>

Thanks, Jeff. This looks promising.

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 3:51pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/10 "2022-01-14T15:51:24Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [January 14, 2022, 3:52pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/11 "2022-01-14T15:52:31Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [January 14, 2022, 3:56pm UTC](https://discourse.julialang.org/t/incorrect-volume-estimate-in-qhull-jl/74622/12 "2022-01-14T15:56:32Z")

</div>

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