3 ms·
Generate random points inside a square (trivial), mirror one half by the diagonal (preserves distribution), transform coordinates inside the resulting triangle
by cluckindan 1y ago
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.
- mytailorisrich 1y agoThat's essentially the accept-flip method of the article, isn't it?
- cluckindan 1y agoNot 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.
- saltcured 1y agoWouldn'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.
- hatthew 1y agoI believe an affine transformation would keep density perfectly consistent across the whole area.
- atq2119 1y agoAffine 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.
- saltcured 1y agoThanks, 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...?
- emil-lp 1y agoYou mean inside the resulting rectangle? That's what the article suggests.
- aaronblohowiak 1y agono, 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.
- o11c 1y agoThere'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).
- saltcured 1y agoHmm, 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...?
- creata 1y agohttps://en.wikipedia.org/wiki/Probability_density_function#Vector_to_vector 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.
- Etherlord87 1y agoNot square, rectangle. The article speaks of a parallelogram but you can the distribution will be the same for the rectangle.
- cluckindan 1y agoSquare works just as well.