Generate a random point in space (x, y, z) with a boundary

Question

I would like to generate a uniformly random coordinate that is inside a convex bounding box defined by its (at least) 4 vertices (for the case of a tetrahedron).

Can someone suggest an algorithm that I can use?

Thanks!

---

If a point is generated in a bounding box, how do you detect whether or not it is outside the geometry but inside the box?

Answer 1

There's a lot that's unspecified in your question, such as what distribution you want to use. For the sake of this answer, I'll assume a uniform distribution.

The straightforward way to handle an arbitrary volume uniform distribution is to choose three uniformly random numbers as coordinates in the range of the bounding rectilinear solid enclosing your volume, then check to see if the chosen coordinate lies within the volume. If the coordinate is not within the volume, discard it and generate a new one.

If this is not sufficient, due to its non-constant performance or whatever other reason, you'll need to constrain your problem (say, to only tetrahedra) and do a bunch of calculus to compute the necessary random distributions and model the dependencies between the axes.

For example, you could start with the x axis and integrate the area of the intersecting shapes between the volume and the plane where x = t. This will give you a function p(x) which, when normalized, is the probability density function along the X axis. (If you want nonuniform distribution, you need to put that in the integrated function, too.)

Then you need to do another set of integrals to determine p(y|x0), the probability distribution function on the Y axis given the chosen x coordinate. Finally, you'll need to determine p(z|x0,y0), the probability distribution function on the z axis.

Once you have all this, you need to use whatever random number algorithm you have to choose random numbers in these distributions: first choose x0 from p(x), then use that to choose y0 from p(y|x0), then use those to choose z0 from p(z|x0,y0), and you'll have your result (x0, y0, z0).

---

There are various algorithms to determine if a point is outside a volume, but a simple one could be:

• For each polygon face:
  • Compute its characteristic planes.
    • Use cross product to compute plane normals.
    • One vertex of the face and the plane normal are sufficient to define the plane.
    • Remember the right-hand rule and choose the points so that the plane normal consistently points into or out of the polyhedron.
  • Check that the random point lies on the "inside" half-space of that plane.
    • A half-space is the set of all points on one side of the plane.
    • Compute the vector from the plane vertex to the random point.
    • Compute the dot product between the plane normal and this vector.
• If you defined the plane normals to point out of the polyhedron, then all dot products must be negative.
• If you defined the plane normals to point into the polyhedron, then all dot products must be positive.

Note that you only have to recompute characteristic planes when the volume moves, not for each random point.

There are probably much better algorithms out there, and their discussion is outside the scope of this question and answer. This algorithm is what I could come up with with no research, and is probably as good as a bubble sort.