Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generate random locations within a triangular domain

I want to generate x and y having a uniform distribution and limited by [xmin,xmax] and [ymin,ymax]

The points (x,y) should be inside a triangle.

How can I solve such a problem?

like image 240
Elena Popa Avatar asked Nov 21 '17 09:11

Elena Popa


People also ask

What is random triangular in Python?

Python Random triangular() Method The triangular() method returns a random floating number between the two specified numbers (both included), but you can also specify a third parameter, the mode parameter.

What is random triangle?

triangular() is an inbuilt method of the random module. It is used to return a random floating point number within a range with a bias towards one extreme. Syntax : random.triangular(low, high, mode) Parameters : low : the lower limit of the random number.


1 Answers

Here's some code that generates points uniformly on an arbitrary triangle in the plane.

import random
    
def point_on_triangle(pt1, pt2, pt3):
    """
    Random point on the triangle with vertices pt1, pt2 and pt3.
    """
    x, y = sorted([random.random(), random.random()])
    s, t, u = x, y - x, 1 - y
    return (s * pt1[0] + t * pt2[0] + u * pt3[0],
            s * pt1[1] + t * pt2[1] + u * pt3[1])

The idea is to compute a weighted average of the three vertices, with the weights given by a random break of the unit interval [0, 1] into three pieces (uniformly over all such breaks). Here x and y represent the places at which we break the unit interval, and s, t and u are the length of the pieces following that break. We then use s, t and u as the barycentric coordinates of the point in the triangle.

Here's a variant of the above that avoids the need to sort, instead making use of an absolute value call:

def point_on_triangle2(pt1, pt2, pt3):
    """
    Random point on the triangle with vertices pt1, pt2 and pt3.
    """
    x, y = random.random(), random.random()
    q = abs(x - y)
    s, t, u = q, 0.5 * (x + y - q), 1 - 0.5 * (q + x + y)
    return (
        s * pt1[0] + t * pt2[0] + u * pt3[0],
        s * pt1[1] + t * pt2[1] + u * pt3[1],
    )

Here's an example usage that generates 10000 points in a triangle:

pt1 = (1, 1)
pt2 = (2, 4)
pt3 = (5, 2)
points = [point_on_triangle(pt1, pt2, pt3) for _ in range(10000)]

And a plot obtained from the above, demonstrating the uniformity. The plot was generated by this code:

import matplotlib.pyplot as plt
x, y = zip(*points)
plt.scatter(x, y, s=0.1)
plt.show()

Here's the image:

enter image description here

And since you tagged the question with the "numpy" tag, here's a NumPy version that generates multiple samples at once. Note that it uses the matrix multiplication operator @, introduced in Python 3.5 and supported in NumPy >= 1.10. You'll need to replace that with a call to np.dot on older Python or NumPy versions.

import numpy as np

def points_on_triangle(v, n):
    """
    Give n random points uniformly on a triangle.

    The vertices of the triangle are given by the shape
    (2, 3) array *v*: one vertex per row.
    """
    x = np.sort(np.random.rand(2, n), axis=0)
    return np.column_stack([x[0], x[1]-x[0], 1.0-x[1]]) @ v


# Example usage
v = np.array([(1, 1), (2, 4), (5, 2)])
points = points_on_triangle(v, 10000)
like image 135
Mark Dickinson Avatar answered Sep 25 '22 14:09

Mark Dickinson