There are other quite elegent methods for triangle and simplices.
For a triangle, drawing α and β uniform over [0,1) the barycentric coordinates given by (1-sqrt(α), sqrt(alpha)(1-β), βsqrt(alpha)) is uniform over the triangle. No rejection and no test for flipping.
For simplices (triangle, tetrahedron, 5-cell etc) barycentric coordinates obtained by drawing uniformly from (0,1] taking a log and normalizing will be uniform within the simplex.
I wrote about this and other related sampling below.
The middle horizontal line cuts the height of the triangle in half. Rotating the upper two “quarter” triangles A and B by 180° around the end points of the horizontal line completes the lower half to a rectangle:
Depending on the coordinate representation/quantization, one drawback might however be that if a random point lands exactly on one of the edges of A and B, the mapping between the triangle and the rectangle is not a bijection. (For example, the single edge between A and B in the triangle becomes two separate edges in the rectangle. Likewise for the middle horizontal line, and conversely for the diagonal triangle edges.)
A tidbit here some might be interested in is that a version of the accept-flip method works for simplices of arbitrary dimension.
For an n-simplex, start by generating a random point in an n-cube (i.e. n uniform random numbers between 0 and 1).
Next, sort the coordinates. This leaves you with a chain `0 <= c_1 <= ... <= c_n <= 1`.
Taking successive differences from this chain gives you n+1 numbers `d_j` (`0 <= j <= n`) that sum to 1.
Finally, the random point in the n-simplex is just `j_0 v_0 + ... + j_n v_n`, where `v_j` are the vertices of the simplex.
It's not hard to verify that this produces the accept-flip technique in dimension 2. As for why it's uniform: the sorting step is mapping a coordinate in the cube into a fundamental domain for the action of the symmetric group (which breaks the cube into a number of simplices of equal size); the other steps are linear maps, which therefore preserve the uniformity.
I coauthored the paper "Trailing the Dovetail Shuffle to its Lair" which solved the GSR model for riffle shuffling in closed form, leading to the recommendation to shuffle a 52 card deck seven times.
Your picture is a great geometric way to think about riffle shuffling. Your n-simplex represents a sorted deck of n cards. Choosing a point uniformly at random in this simplex makes the needed choices all at once to predetermine an arbitrary number of riffle shuffles. Think of k riffle shuffles as a single 2^k shuffle (as if you had 2^k hands); we can now study an "a-shuffle". Scale the n-simplex by a factor of a. Where does our random point end up? Either view all of space as tiled by your n-cubes, or reduce all coordinates mod 1. Either way the random point ends up in some n-simplex described by a different (or the same) order (mod 1) of the coordinates. That's your shuffle.
For a single shuffle of two cards, doubling the 2-simplex ("up-triangle") covers three up-triangles and one down-triangle, so the odds of reversing the cards is 1 in 4. This makes sense if you imagine two "stowaway" cards face up, placed at random in a face-down deck. Shuffling the deck, to reverse these cards they can't both be in the same packet, and being in different packets only reverses them half the time.
Increasing "a" for two cards, one sees the up and down-triangle counts converge to a 1:1 ratio. The error "fringe" looks like a numerical integration error.
I solved this problem in Blender [1] in the past using python's `random.triangular()` [2], and the name suggests this problem is the best example of when you would need `triangular()` and how its distribution works.
I'm certainly not knowledgeable about these algorithms, but I'm willing to look foolish.
In any regular polygon, you can fill it with a line of any thickness by starting at one vertex and spiraling inward until the shape is completely filled. The line can be as thin as required for any application.
The problem is now transformed into finding random points on a finite line.
I don't have the mathematical chops to know, but I'd guess that finding the length of such a line and coverting to the 2d coordinates of any point on the line would be possible perhaps even practical. Does anyone here know if this is possible?
So from a mathematical perspective, the issue is that your "line" (path) actually has zero thickness, and so there are gaps between the spiral windings. If you sample a point from any finite-length path then you have probability zero of hitting any of the points in the gaps between segments. (Maybe you don't care about this if the gaps are sufficiently small, but from a mathematical perspective it's not strictly valid.)
And you can't just say "the path is infinitely long and spirals infinitely many times" because then you have no way of uniformly sampling a random real number between zero and infinity (it can be proven that no such probability distribution exists).
But I think the basic idea is sound and you make it work by formulating it slightly differently:
1. Divide up the triangle into infinite concentric triangles
2. Choose a random triangle with probability proportional to that triangle's length
3. Choose a random point on that triangle's perimeter
The interesting part is step 2. If you parameterize the triangles by a scale factor s, ranging from 0 to 1, then the perimeter is proportional to s. So I believe you can choose s appropriately by choosing x uniformly at random from 0..1 and letting s = sqrt(x). See https://en.wikipedia.org/wiki/Triangular_distribution
Then step 3 is mathematically straightforward: if the lengths of the triangle's sides are a,b,c, you choose a random number between 0 and a+b+c, and "wrap" that length around the triangle's perimeter. Then you have to do the correct coordinate transformation to find the appropriate point on the scaled triangle you chose.
So I think it would work, but it probably wouldn't be any simpler to implement than the "accept-flip" method described in the article.
Generate random points inside a square (trivial), mirror one half by the diagonal (preserves distribution), transform coordinates inside the resulting triangle to the given triangle.
Not really. Using a parallelogram means each x-coordinate’s allowed range depends on the y-coordinate and vice versa, but using a square, the coordinates are independent.
Wouldn't that subsequent transform distort the sample distribution? As you make the angle at one vertex more obtuse, the density of the point mapping increases more there relative to the points near the other, more acute vertices.
You can think of it this way. There's a density function on the shapes in question. Whenever you transform the 2d space, you have to adjust the density at the same time to preserve "volume" (area times density).
Non-linear transforms, such as interpreting a square as polar coordinates to obtain a disk, will expand or shrink area differently in different parts of the space, which means that if you start with a uniform density, you end up with a non-uniform density. But linear/affine transforms affect area the same everywhere in the space, and so if the density is uniform to begin with, it remains uniform.
Thanks, I should have reminded myself that my intuitions are often non-mathematical. I don't even know how I decided that a change in angle would have a non-linear effect on density.
I also had an intuition that the aspect ratio change would squish the distribution. I guess this aspect ratio doesn't matter for the density distribution of dimensionless points.
But, if doing something like splatting a pixel/sprite at each point coordinate, would the sprite shape need to be transformed to match...?
no, this person is not suggesting a parallelogram but rather performing an affine transformation on the triangle to make it a right triangle so they can pick a random point in a square instead. as another commenter mentioned, I believe this distorts the distribution and won't do the right thing.
ah, excellent point. thanks. this works if they are transforming the triangle to be a right triangle to make a rectangle but if they are making it half a square, that could not be accomplished solely with affine transformations (if I figure correctly...)
There's no distortion for the purposes of randomness (there would be if you cared about distance between specific points before/after the transformation), but the blog article fails to actually explain the method.
Clicking through to SO explains it (but assumes you can read numpy). The `s * u` and `t * v` (where `u` and `v` are vectors) are the transformation from right-triangle (half of square) to triangle (half of parallelgram).
Hmm, is this "car(ing) about distance between specific points" something that would matter if we were going to operate in reverse and splat something at each point to render the triangle?
I think that sort of splatting is how I intuitively think about this problem, and likely where I went wrong in thinking there would be a distortion of the density function. I'm not confident whether this actually matters though. Would it still approximate the same distribution regardless of what splat shape is used...?
I didn't want to be that critical right out of the gate, but yeah if an "experienced consultant" thinks that this is worth writing about at this level of detail, then that makes me trust them less, not more.
Go away kitten, your comment appears to be low-quality.
"Generate in a parallelogram" is pretty obvious, unless you are truly clueless. Every post of johndcook that I find posted to HN is interesting, and definitely of high quality.
Here was a cute idea I thought of. Divide the triangle into 4 by joining the midpoints (a "triforce" shape). The four triangles are congruent, each equal to a quarter of the larger triangle. Generate a uniform 1/4 probability event in your favourite way (flip two coins) and accordingly choose one of the triangles to contain your point. Repeat this indefinitely to get an exponentially small triangle containing your point.
I think this should be a uniform distribution by symmetry. Obviously the boundaries of the triangles never get picked but that's a measure 0 set.
I doubt I'm more geometrically inclined than the average HN user, but to me the general "accept-flip" method mentioned here seems trivial, obvious, and already solved, to the extent that I'm surprised it's worth writing more about or considering any alternatives.
Generating random points uniformly in a circle without rejection is at least mildly more interesting, as you need to scale one factor by a square root:
Wait, wouldn't this result in the opposite of what you want? You want to shift the distribution out, not crowd the center, so you probably want to square your random instead.
Squaring numbers in (0,1) makes them smaller, pulling the random radius closer to center. As an example consider 0.9. Squaring it gets 0.81 vs 0.949 taking the square root.
There are other quite elegent methods for triangle and simplices.
For a triangle, drawing α and β uniform over [0,1) the barycentric coordinates given by (1-sqrt(α), sqrt(alpha)(1-β), βsqrt(alpha)) is uniform over the triangle. No rejection and no test for flipping.
For simplices (triangle, tetrahedron, 5-cell etc) barycentric coordinates obtained by drawing uniformly from (0,1] taking a log and normalizing will be uniform within the simplex.
I wrote about this and other related sampling below.
https://abhila.sh/writing/5/Random_Sampling.html
https://abhila.sh/writing/8/Random_Sampling_2.html
> Create a parallelogram by attaching a flipped copy of the triangle.
You don’t need to duplicate the triangle. You can also turn any triangle into an equal-area rectangle like this: https://youtu.be/nVz3kCrJLWo?t=77
Bad ASCII art:
The middle horizontal line cuts the height of the triangle in half. Rotating the upper two “quarter” triangles A and B by 180° around the end points of the horizontal line completes the lower half to a rectangle: Depending on the coordinate representation/quantization, one drawback might however be that if a random point lands exactly on one of the edges of A and B, the mapping between the triangle and the rectangle is not a bijection. (For example, the single edge between A and B in the triangle becomes two separate edges in the rectangle. Likewise for the middle horizontal line, and conversely for the diagonal triangle edges.)A tidbit here some might be interested in is that a version of the accept-flip method works for simplices of arbitrary dimension.
For an n-simplex, start by generating a random point in an n-cube (i.e. n uniform random numbers between 0 and 1).
Next, sort the coordinates. This leaves you with a chain `0 <= c_1 <= ... <= c_n <= 1`.
Taking successive differences from this chain gives you n+1 numbers `d_j` (`0 <= j <= n`) that sum to 1.
Finally, the random point in the n-simplex is just `j_0 v_0 + ... + j_n v_n`, where `v_j` are the vertices of the simplex.
It's not hard to verify that this produces the accept-flip technique in dimension 2. As for why it's uniform: the sorting step is mapping a coordinate in the cube into a fundamental domain for the action of the symmetric group (which breaks the cube into a number of simplices of equal size); the other steps are linear maps, which therefore preserve the uniformity.
I coauthored the paper "Trailing the Dovetail Shuffle to its Lair" which solved the GSR model for riffle shuffling in closed form, leading to the recommendation to shuffle a 52 card deck seven times.
Your picture is a great geometric way to think about riffle shuffling. Your n-simplex represents a sorted deck of n cards. Choosing a point uniformly at random in this simplex makes the needed choices all at once to predetermine an arbitrary number of riffle shuffles. Think of k riffle shuffles as a single 2^k shuffle (as if you had 2^k hands); we can now study an "a-shuffle". Scale the n-simplex by a factor of a. Where does our random point end up? Either view all of space as tiled by your n-cubes, or reduce all coordinates mod 1. Either way the random point ends up in some n-simplex described by a different (or the same) order (mod 1) of the coordinates. That's your shuffle.
For a single shuffle of two cards, doubling the 2-simplex ("up-triangle") covers three up-triangles and one down-triangle, so the odds of reversing the cards is 1 in 4. This makes sense if you imagine two "stowaway" cards face up, placed at random in a face-down deck. Shuffling the deck, to reverse these cards they can't both be in the same packet, and being in different packets only reverses them half the time.
Increasing "a" for two cards, one sees the up and down-triangle counts converge to a 1:1 ratio. The error "fringe" looks like a numerical integration error.
I solved this problem in Blender [1] in the past using python's `random.triangular()` [2], and the name suggests this problem is the best example of when you would need `triangular()` and how its distribution works.
[1] https://blender.stackexchange.com/a/221597/60486 [2] https://docs.python.org/3/library/random.html#random.triangu...
I'm certainly not knowledgeable about these algorithms, but I'm willing to look foolish.
In any regular polygon, you can fill it with a line of any thickness by starting at one vertex and spiraling inward until the shape is completely filled. The line can be as thin as required for any application.
The problem is now transformed into finding random points on a finite line. I don't have the mathematical chops to know, but I'd guess that finding the length of such a line and coverting to the 2d coordinates of any point on the line would be possible perhaps even practical. Does anyone here know if this is possible?
So from a mathematical perspective, the issue is that your "line" (path) actually has zero thickness, and so there are gaps between the spiral windings. If you sample a point from any finite-length path then you have probability zero of hitting any of the points in the gaps between segments. (Maybe you don't care about this if the gaps are sufficiently small, but from a mathematical perspective it's not strictly valid.)
And you can't just say "the path is infinitely long and spirals infinitely many times" because then you have no way of uniformly sampling a random real number between zero and infinity (it can be proven that no such probability distribution exists).
But I think the basic idea is sound and you make it work by formulating it slightly differently:
1. Divide up the triangle into infinite concentric triangles
2. Choose a random triangle with probability proportional to that triangle's length
3. Choose a random point on that triangle's perimeter
The interesting part is step 2. If you parameterize the triangles by a scale factor s, ranging from 0 to 1, then the perimeter is proportional to s. So I believe you can choose s appropriately by choosing x uniformly at random from 0..1 and letting s = sqrt(x). See https://en.wikipedia.org/wiki/Triangular_distribution
Then step 3 is mathematically straightforward: if the lengths of the triangle's sides are a,b,c, you choose a random number between 0 and a+b+c, and "wrap" that length around the triangle's perimeter. Then you have to do the correct coordinate transformation to find the appropriate point on the scaled triangle you chose.
So I think it would work, but it probably wouldn't be any simpler to implement than the "accept-flip" method described in the article.
Generate random points inside a square (trivial), mirror one half by the diagonal (preserves distribution), transform coordinates inside the resulting triangle to the given triangle.
Not square, rectangle. The article speaks of a parallelogram but you can the distribution will be the same for the rectangle.
Square works just as well.
That's essentially the accept-flip method of the article, isn't it?
Not really. Using a parallelogram means each x-coordinate’s allowed range depends on the y-coordinate and vice versa, but using a square, the coordinates are independent.
Wouldn't that subsequent transform distort the sample distribution? As you make the angle at one vertex more obtuse, the density of the point mapping increases more there relative to the points near the other, more acute vertices.
Affine transformations don't change relative density.
You can think of it this way. There's a density function on the shapes in question. Whenever you transform the 2d space, you have to adjust the density at the same time to preserve "volume" (area times density).
Non-linear transforms, such as interpreting a square as polar coordinates to obtain a disk, will expand or shrink area differently in different parts of the space, which means that if you start with a uniform density, you end up with a non-uniform density. But linear/affine transforms affect area the same everywhere in the space, and so if the density is uniform to begin with, it remains uniform.
Thanks, I should have reminded myself that my intuitions are often non-mathematical. I don't even know how I decided that a change in angle would have a non-linear effect on density.
I also had an intuition that the aspect ratio change would squish the distribution. I guess this aspect ratio doesn't matter for the density distribution of dimensionless points.
But, if doing something like splatting a pixel/sprite at each point coordinate, would the sprite shape need to be transformed to match...?
I believe an affine transformation would keep density perfectly consistent across the whole area.
You mean inside the resulting rectangle?
That's what the article suggests.
no, this person is not suggesting a parallelogram but rather performing an affine transformation on the triangle to make it a right triangle so they can pick a random point in a square instead. as another commenter mentioned, I believe this distorts the distribution and won't do the right thing.
https://en.wikipedia.org/wiki/Probability_density_function#V...
Affine transformations just scale the probability density by a constant, so a uniform distribution is still uniform.
ah, excellent point. thanks. this works if they are transforming the triangle to be a right triangle to make a rectangle but if they are making it half a square, that could not be accomplished solely with affine transformations (if I figure correctly...)
But you can just map one right triangle to the other without affecting the distribution.
There's no distortion for the purposes of randomness (there would be if you cared about distance between specific points before/after the transformation), but the blog article fails to actually explain the method.
Clicking through to SO explains it (but assumes you can read numpy). The `s * u` and `t * v` (where `u` and `v` are vectors) are the transformation from right-triangle (half of square) to triangle (half of parallelgram).
Hmm, is this "car(ing) about distance between specific points" something that would matter if we were going to operate in reverse and splat something at each point to render the triangle?
I think that sort of splatting is how I intuitively think about this problem, and likely where I went wrong in thinking there would be a distortion of the density function. I'm not confident whether this actually matters though. Would it still approximate the same distribution regardless of what splat shape is used...?
If it's the whole triangle, use a Dirichlet RNG with alpha=1.
What's a "whole triangle" ? Google leads me nowhere.
meaning each point within the triangle has equal probability
This appears to be low-quality blogspam. It fails to even explain the main method (delegating to a handwaved "generate in a parallelogram").
A parallelogram is just a rectangle with extra steps. Maybe they could have mentioned what those steps are but it seems fairly straightforward
I didn't want to be that critical right out of the gate, but yeah if an "experienced consultant" thinks that this is worth writing about at this level of detail, then that makes me trust them less, not more.
Go away kitten, your comment appears to be low-quality.
"Generate in a parallelogram" is pretty obvious, unless you are truly clueless. Every post of johndcook that I find posted to HN is interesting, and definitely of high quality.
Here was a cute idea I thought of. Divide the triangle into 4 by joining the midpoints (a "triforce" shape). The four triangles are congruent, each equal to a quarter of the larger triangle. Generate a uniform 1/4 probability event in your favourite way (flip two coins) and accordingly choose one of the triangles to contain your point. Repeat this indefinitely to get an exponentially small triangle containing your point.
I think this should be a uniform distribution by symmetry. Obviously the boundaries of the triangles never get picked but that's a measure 0 set.
I doubt I'm more geometrically inclined than the average HN user, but to me the general "accept-flip" method mentioned here seems trivial, obvious, and already solved, to the extent that I'm surprised it's worth writing more about or considering any alternatives.
Generating random points uniformly in a circle without rejection is at least mildly more interesting, as you need to scale one factor by a square root:
Wait, wouldn't this result in the opposite of what you want? You want to shift the distribution out, not crowd the center, so you probably want to square your random instead.
Squaring numbers in (0,1) makes them smaller, pulling the random radius closer to center. As an example consider 0.9. Squaring it gets 0.81 vs 0.949 taking the square root.
Oh yes all of you are right. In my defense, I am stupid.
Because the numbers are less than 1 sqrt pulls them towards 1 (the edge)
assuming random() returns values 0<=r<=1, sqrt will shift the distribution outward
Yeah that would be at least nontrivial, but has been written about so much that the bar for a worthwhile article seems pretty high.
Obligatory xkcd: https://xkcd.com/1053/