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.

Solution 1

A. If you can restrict your input to parallelogram, this is really simple:

1. Take two random numbers between 0 and 1. We'll call then u and v.

2. If your parallelogram is defined by the points ABCD such that AB, BC, CD and DA are the sides, then take your point as being:

    p = A + (u * AB) + (v * AD)
   

Where AB is the vector from A to B and AD the vector from A to D.

B. Now, if you cannot, you can still use the barycentric coordinates. The barycentric coordinates correspond, for a quad, to 4 coordinates (a,b,c,d) such that a+b+c+d=1. Then, any point P within the quad can be described by a 4-uple such that:

P = a A + b B + c C + d D

In your case, you can draw 4 random numbers and normalize them so that they add up to 1. That will give you a point. Note that the distribution of points will NOT be uniform in that case.

C. You can also, as proposed elsewhere, decompose the quad into two triangles and use the half-parallelogram method (i.e., as the parallelogram but you add the condition u+v=1) or the barycentric coordinates for triangles. However, if you want uniform distribution, the probability of having a point in one of the triangle must be equal to the area of the triangle divided by the area of the quad.

Solution 2

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.

Solution 3

Assuming you want a uniform distribution: Form two triangles from your polygon. Pick which triangle to generate the point in according to their area ratio.

Call the corners of the triangle A, B, C, the side vectors AB, BC, AC and generate two random numbers in [0,1] called u and v. Let p = u * AB + v * AC.

If A+p is inside the triangle, return A+p

If A+p is outside the triangle, return A + AB + AC - p

(This is basically PierreBdR's formula except for the preprocessing and the last step that folds the point back into a triangle, so it can handle other shapes than parallelograms).

Solution 4

Your polygon is two triangles, so why not randomly select one of those, then find a random point in the triangle.

Probably not the best solution, but it'd work.

Solution 5

A somewhat less "naïve" approach would be to use a polygon fill algorithm, and then select points from the fill lines randomly.

C Code Sample

//  public-domain code by Darel Rex Finley, 2007

int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple “Bubble” sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  //  Code modified by SoloBold 27 Oct 2008
  //  The flagPixel method below will flag a pixel as a possible choice.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

View more solutions

Comments

[dmckee --- ex-moderator kitten]

I suspect this is not what Turambar needs, but it will work. Some lines are longer than others, so to get a uniform distribution, don't pick a line, then pick a pixel. Count the pixels, then choose one randomly, and find its location from the list...

[user2522201]

If you need a uniform distribution for the random points, make sure you take into account the area of each of the two triangles and weight appropriately.

[Thomas Ahle]

Great answer. Lovely pictures.

[Gabriel Littman]

I'm trying to implement this and I think it should be be x' = v0 + (v3 - x) Am I totally off base? Looking at it some more I'm not sure I'm right but my test case of v0 = [0,0] puts x' outside of the triangle.

[cheshirekow]

@gabriel_littman. I believe you are correct. In the graphic for the equation there is a missing R(pi), which is present in the text... i.e. rotation by 180 degrees. I think that rotation matrix is [-1, 0; 0, -1] which is to say that we take the negative of its operand.

[Gustavo Maciel]

This is the actual answer to the question!

[Pranav]

Whether barycenter approach will work for the case of polygons with holes?

[PierreBdR]

@Pranav No it won't ... barycentric coordinate requires continuous domain, and I would guess probably convex (to be checked).

[Andrew Stromme]

I've tried implementing this in python but I think something is broken. See gist.github.com/astromme/599de466236adc534bc6e33cf2af8e7b. For a triangle with points [0, 1], [1, 0], [1,0] v3 is [2, -1] which doesn't seem to make sense. Furthermore, I get points that are outside of the quad. Any ideas?

[Niyaz]

For anyone else looking, here is how to find if a point is inside a triangle: stackoverflow.com/questions/2049582/…