algorithm - Random points inside a parallelogram

Question

I have a 4 side convex Polygon defined by 4 points in 2D, and I want to be able to generate random points inside it.

If it really simplifies the problem, I can limit the polygon to a parallelogram, but a more general answer is preferred.

Generating random points until one is inside the polygon wouldn't work because it's really unpredictable the time it takes.

Answer 1

The question by the OP is a bit ambiguous so the question I will answer is: How to generate a point from a uniform distribution within an arbitrary quadrilateral, which is actually a generalization of How to generate a point from a uniform distribution within an arbitrary (convex) polygon. The answer is based on the case of generating a sample from a uniform distribution in a triangle (see http://mathworld.wolfram.com/TrianglePointPicking.html, which has a very nice explanation).

In order to accomplish this we:

1. Triangulate the polygon (i.e. generate a collection of non-overlapping triangular regions which cover the polygon). For the case of a quadrilateral, create an edge across any two non-adjacent vertices. For other polygons, see http://en.wikipedia.org/wiki/Polygon_triangulation for a starting point, or http://www.cgal.org/ if you just need a library.

   

2. To pick one of the triangles randomly, let us assign an index to each triangle (i.e. 0,1,2,...). For the quadrilateral, they will be 0,1. For each triangle we assign a weight equal as follows:

   

3. Then generate a random index i from the finite distribution over indexes given their weights. For the quadrilateral, this is a Bernoulli distribution:

   

4. Let v0, v1, v2 be vertices of the triangle (represented by their point locations, so that v0 = (x0,y0), etc. Then we generate two random numbers a0 and a1, both drawn uniformly from the interval [0,1]. Then we calculate the random point x by x = a0 (v1-v0) + a1 (v2-v0).

   

5. Note that with probability 0.5, x lies outside outside the triangle, however if it does, it lies inside the parallelogram composed of the union of the triangle with it's image after a rotation of pi around the midpoint of (v1,v2) (dashed lines in the image). In that case, we can generate a new point x' = v0 + R(pi)(x - v3), where R(pi) is a rotation by pi (180 deg). The point x' will be inside the triangle.

6. Further note that, if the quadrilateral was already a parallelogram, then we do not have to pick a triangle at random, we can pick either one deterministically, and then choose the point x without testing that it is inside it's source triangle.