Random points inside a parallelogram

by

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.

    enter image description here

  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:

    weight calculation

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

    enter image description here

  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).

    enter image description here

  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.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Expand a random range from 1–5 to 1–7
  3. An algorithm for inflating/deflating (offsetting, buffering) polygons
  4. How do I calculate the area of a 2d polygon?
  5. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  6. What distribution do you get from this broken random shuffle?
  7. Select k random elements from a list whose elements have weights
  8. Data structures for loaded dice?
  9. How do I efficiently determine if a polygon is convex, non-convex or complex?
  10. Pseudorandom Number Generator – Exponential Distribution
  11. Choosing n numbers with fixed sum
  12. Shuffle list, ensuring that no item remains in same position
  13. Is there an efficient algorithm to generate a 2D concave hull?
  14. Largest circle inside a non-convex polygon
  15. True random number generator [closed]
  16. Polygon enclosing a set of points
  17. Create a random permutation of 1..N in constant space
  18. Closest point to a given point
  19. Creating a random number generator from a coin toss
  20. How can I create an internal spiral for a polygon?
  21. Given a number, produce another random number that is the same every time and distinct from all other results
  22. Finding the best trade-off point on a curve
  23. Faster version of find for sorted vectors (MATLAB)
  24. Reverse complex 2D lookup table
  25. Reservoir sampling
  26. Generating shuffled range using a PRNG rather than shuffling
  27. Randomly choosing from a list with weighted probabilities
  28. A Good and SIMPLE Measure of Randomness
  29. Unbiased random number generator using a biased one
  30. how do I create a line of arbitrary thickness using Bresenham?

Leave a Comment