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.
emil-lp · 24m ago
You mean inside the resulting rectangle?
That's what the article suggests.
aaronblohowiak · 19m ago
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.
saltcured · 23m ago
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.
hatthew · 11m ago
I believe an affine transformation would keep density perfectly consistent across the whole area.
mytailorisrich · 26m ago
That's essentially the accept-flip method of the article, isn't it?
ok123456 · 31m ago
If it's the whole triangle, use a Dirichlet RNG with alpha=1.
hatthew · 18m ago
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.
spankalee · 14m ago
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, to not crowd the center, so you probably want to square your random instead.
hatthew · 7m ago
Yeah that would be at least nontrivial, but has been written about so much that the bar for a worthwhile article seems pretty high.
That's what the article suggests.
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.