3
$\begingroup$

I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)?

I find approaches for 2D case like the one described here but none in the case of polyhedrons(3D). Whether extending this approach for 2D is the only way, in which case that random point will still be forced to be on the surface of a triangle of a tetrahedron in the 3D triangulation of the given polyhedron?

|cite|improve this question
$\endgroup$
6
$\begingroup$

If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow for high dimensions and "unboxy" polytopes though, because the bounding box potentially has a huge volume compared to the region you're interested in.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am using polyhedrons to represent machine components which are three dimensional and non-convex. BTW, what do you mean by "unboxy" polytopes? $\endgroup$ – Pranav Jul 14 '16 at 8:31
  • 1
    $\begingroup$ If the polytope looks like a hypercube, sampling by using the bounding hypercube works ok. If it is very different from a cube, the runtime explodes. $\endgroup$ – adrianN Jul 14 '16 at 8:43
  • $\begingroup$ Will this approach for convex polytope work if the polytope has holes...I mean will that random point always lie inside polytope but not in hole? $\endgroup$ – Pranav Jul 14 '16 at 11:58
  • $\begingroup$ If it has holes, it's not convex. You will have to read the papers to see whether the methods can be adapted and perhaps ask a new question. $\endgroup$ – adrianN Jul 14 '16 at 12:13
  • $\begingroup$ I have edited this question accordingly. $\endgroup$ – Pranav Jul 14 '16 at 12:29
3
$\begingroup$

To implement adrianN's rejection sampling method, you will need a function to determine if a point is inside your polyhedron. This not-completely-trivial problem is discussed in my book Computational Geometry in C, and there is code available.

      Fig7.10

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Will it also work for polyhedrons with holes?...Actually, in my problem, I get this polyhedron after symmetric difference between 2 input polyhedrons, which often creates holes. $\endgroup$ – Pranav Jul 14 '16 at 13:35
  • 1
    $\begingroup$ @Pranav: Yes, because it just counts ray crossings. $\endgroup$ – Joseph O'Rourke Jul 14 '16 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.