Sample uniformly random points within a triangle

Question

I would like to know how to get random vectors inside a triangle, in python, but it seemed more difficult than I expected. The plane would have coordinates like [a, b], [x, y], [u, v] (three points):

What I want to do

The simplest method is to sample uniformly within an area containing the triangle, and then reject points outside the triangle area. (And, if you're clever, you might even be able to reuse some of that rejected randomness without incurring a bias.) — Mateen Ulhaq, Jul 23 '21 at 01:46
Perhaps this may be of use: https://mathworld.wolfram.com/TrianglePointPicking.html — Mateen Ulhaq, Jul 23 '21 at 01:50
Not a Python question. See [Mathematics Stack Exchange](https://math.stackexchange.com/) — martineau, Jul 23 '21 at 01:55
I edited your question to refer to uniformly random points, but upon further review, are you also wanting the points not to be clustered together? One can make a simple modification to the uniform random point generator that I gave below where the input uniform distributions `S, T` are a random subset of some grid in which the spacing is s.t. points grid points are a tolerable distance apart. To reduce the rigidity, you can displace the grid points slightly in a random fashion. O(n). There's also reject sampling, which is roughly O(n^2) for n sufficiently small. — Mateen Ulhaq, Jul 23 '21 at 04:32
Does this answer your question? [Why do we need to triangulate a convex polygon in order to sample uniformly from it?](https://stackoverflow.com/questions/63776466/why-do-we-need-to-triangulate-a-convex-polygon-in-order-to-sample-uniformly-from) — Peter O., Jul 23 '21 at 04:56
If you want uniform sampling in a triangle without rejection, this is formula (1) in this [paper](http://www.cs.princeton.edu/~funk/tog02.pdf). Look at the triangle in the figure just after the formula for a graphical explanation. — jpmarinier, Jul 23 '21 at 09:15
Seems like a duplicate of https://stackoverflow.com/questions/47410054/ — Mark Dickinson, Jul 23 '21 at 14:50

Mateen Ulhaq · Accepted Answer · 2021-07-23T10:04:41.157

Let u and v be vectors defining a triangle centered at the origin. By this triangle point picking method, one can generate random points within a parallelogram defined by u and v. If points are outside the triangle, simply reject, or invert the points about the diagonal between u and v.

import random

def uniform_triangle(u, v):
    while True:
        s = random.random()
        t = random.random()
        in_triangle = s + t <= 1
        p = s * u + t * v if in_triangle else (1 - s) * u + (1 - t) * v
        yield p

Figure generated via:

from itertools import islice
import matplotlib.pyplot as plt
import numpy as np

triangle = np.array([
    [1, 2],
    [3, 8],
    [7, 5],
])

it = uniform_triangle(
    triangle[1] - triangle[0],
    triangle[2] - triangle[0],
)

points = np.array(list(islice(it, 0, 1000)))
points += triangle[0]

fig, ax = plt.subplots()
ax.scatter(points[:, 0], points[:, 1], s=1)
fig.savefig("triangle.png", dpi=200)

Sample uniformly random points within a triangle

1 Answers1