Randomly selecting points inside a triangle
johndcook.com
johndcook.com
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.
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:
/|\
/ A|B\
/____|__\
/ | \
/ | \
’——————————+—————`
________________
| A / | \B|
| / | \|
’——————————+—————`
⋰|\
⋰ A|B\
⋰____|__\
⋰ | \
⋰ | \
’——————————+—————`
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.
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.
[1] https://blender.stackexchange.com/a/221597/60486 [2] https://docs.python.org/3/library/random.html#random.triangu...
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.
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?
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.
That's what the article suggests.
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).
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...?
Affine transformations just scale the probability density by a constant, so a uniform distribution is still uniform.
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.
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...?
const r = sqrt(random()) * radius;
const theta = random() * TAU;