Matlab, generate and build a point cloud distributed in a triangle

Question

I am trying to create a cloud of 2D points (evenly) distributed in a triangle. So far I have achieved the following results:

The code I used is:

N = 1000; X = -10:0.1:10; for i=1:N j = ceil(rand() * length(X)); x_i = X(j); y_i = (10 - abs(x_i)) * rand; E(:, i) = [x_i y_i]; end 

However, the points are not evenly distributed, which is clearly visible in the left and right corners. How can I improve this result? I also tried to find different shapes, no luck.

Answer 1

First you need to ask yourself what to evenly distribute the points inside the triangle.

To make a long story short, given all three vertices of the triangle, you need to convert two evenly distributed random values, for example:

 N = 1000; % # Number of points V = [-10, 0; 0, 10; 10, 0]; % # Triangle vertices, pairs of (x, y) t = sqrt(rand(N, 1)); s = rand(N, 1); P = (1 - t) * V(1, :) + bsxfun(@times, ((1 - s) * V(2, :) + s * V(3, :)), t); 

This will create a set of points that are evenly distributed inside the specified triangle:

 scatter(P(:, 1), P(:, 2), '.') 

Please note that this solution does not require repeated conditional manipulation of random numbers, so it cannot potentially fall into an infinite loop.

See this article for further reading.

Answer 2

This concentration of points will be expected from how you build points. Your points are evenly distributed along the X axis. At the extreme points of the triangle, there are approximately the same number of points present in the center of the triangle, but they are distributed along a much smaller area.

The first and best approach I can think of: brute force. Distribute the points equally around the larger region, and then delete those that are outside the region of interest to you.

 N = 1000; points = zeros(N,2); n = 0; while (n < N) n = n + 1; x_i = 20*rand-10; % generate a number between -10 and 10 y_i = 10*rand; % generate a number between 0 and 10 if (y_i > 10 - abs(x_i)) % if the points are outside the triangle n = n - 1; % decrease the counter to try to generate one more point else % if the point is inside the triangle points(n,:) = [x_i y_i]; % add it to a list of points end end % plot the points generated plot(points(:,1), points(:,2), '.'); title ('1000 points randomly distributed inside a triangle'); 

The result of the code I posted:

one important expression about rejection : random distribution does not mean "evenly" distributed! If you randomly generate data from a uniform distribution, this does not mean that it will be "evenly distributed" along the triangle. In fact, you will see some clusters of points.

Answer 3

You can imagine that a triangle is divided vertically into two halves and moves to one half so that, together with the other, it creates a rectangle. Now you randomly select a rectangle, which is easy, and then move the polygon back.

In addition, it is easier to work with units of length (the rectangle becomes a square), and then stretch the triangle to the desired size.

 x = [-10 10]; % //triangle base y = [0 10]; % //triangle height N = 1000; %// number of points points = rand(N,2); %// sample uniformly in unit square ind = points(:,2)>points(:,1); %// points to be unfolded points(ind,:) = [2-points(ind,2) points(ind,1)]; %// unfold them points(:,1) = x(1) + (x(2)-x(1))/2*points(:,1); %// stretch x as needed points(:,2) = y(1) + (y(2)-y(1))*points(:,2); %// stretch y as needed plot(points(:,1),points(:,2),'.') 

Answer 4

We can generalize this case. If you want to select points from some (n - 1) -dimensional simplex in UNIFORMLY Euclidean space (not necessarily a triangle - it can be any convex polyhedron), simply draw a vector from the symmetric n-dimensional Dirichlet distribution with parameter 1 - these are convex (or barycentric) coordinates relative to the vertices of the polyhedron.