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?

$\endgroup$

2 Answers 2

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.

$\endgroup$
5
  • $\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
    Commented Jul 14, 2016 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
    Commented Jul 14, 2016 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
    Commented Jul 14, 2016 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
    Commented Jul 14, 2016 at 12:13
  • $\begingroup$ I have edited this question accordingly. $\endgroup$
    – Pranav
    Commented Jul 14, 2016 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

$\endgroup$
2
  • $\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
    Commented Jul 14, 2016 at 13:35
  • 1
    $\begingroup$ @Pranav: Yes, because it just counts ray crossings. $\endgroup$ Commented Jul 14, 2016 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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