HN Reader

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

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 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?

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.

> 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:

           /|\
         / A|B\
       /____|__\
     /      |   \
   /        |    \
 ’——————————+—————`

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:

  ________________
 | A /      |   \B|
 | /        |    \|
 ’——————————+—————`

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

If it's the whole triangle, use a Dirichlet RNG with alpha=1.

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.

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.

This appears to be low-quality blogspam. It fails to even explain the main method (delegating to a handwaved "generate in a parallelogram").