The module scipy.spatial.ConvexHull can only compute the Minkowski sum of two 2D convex hulls. But I would like to calculate the Minkowski sum of two 3D convex hulls. I am wondering if there is another package that would offer this capacity. Or otherwise, I would like to learn about efficient algorithm to solve the problem that I could implement in Python.
When you speak about convex hulls, do you mean convex hulls of finite number of points? If so, then there is a very simple formula: let x1, x2, ..., xn and y1, ..., ym be two finite sets (in one the same linear space of arbitrary dimension) then
conv(x1, ..., xn) + conv(y1, ..., ym) = conv(xk + yj : k = 1, ... , n, j = 1, ... , m)
In addition to the very helpful answer given by @ Vladimir Kadets, there is a bit more to add.
A good paper directly related to the topic for this thread is
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
https://arxiv.org/pdf/0911.5086.pdf
Recall that a convex polytope is the convex hull of a finite set of points (for more about this, see page 2). For the Minkowski sum of polytopes, see page 20.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Computer Graphics and Animation
- 3D