How to uniformly fill a volume of a convexHull given by a list of 3d points?

Question

I have a convexHull given by a list of 3d points generated by scipy.spatial.ConvexHull.

I want that entire volume uniformly filled with 3d points, in some efficient manner.

If i had a fast way of knowing if a point is inside or out of a convexHull, I could maybe vectorize going over each voxel in some resolution and returning its center if it is "inside" or returning nothing for that voxel if it is "outside".

---

Example:

for 2d points, like in scipy's example of ConvexHull,

I would like to compute a list of points which are evenly spaced inside the red line.

How can this be done rather efficiently?

Answer 1

Here is some (unoptimized) sample code demonstrating the use of the .equations attribute which contains surface normals to the convex hull.

import numpy as np
from scipy import spatial

## set up example ##
# create sample points
np.random.seed(17)
samples = np.random.uniform(-5,5,(100,2))
# pick convex subset
outline = samples[(samples**2).sum(1)<4]
outline = spatial.ConvexHull(outline)
# choose tolerance for detection of boundary points
eps = 1e-9

## classify ##
outside = (outline.equations@np.c_[samples, np.ones(len(samples))].T > eps).any(0)
inside = (outline.equations@np.c_[samples, np.ones(len(samples))].T < -eps).all(0)
boundary = ~(outside|inside)

## plot ##
import pylab
closed = np.tile(outline.points[outline.vertices],(2,1))
closed = closed[:len(closed)//2+1]
pylab.plot(*closed.T,'b')
pylab.plot(*samples[outside].T,'og')
pylab.plot(*samples[inside].T,'or')
pylab.plot(*samples[boundary].T,'oy')
pylab.show()