Feb 19, 2011

Random points distributed inside a triangle.

For a particular project for the office where I work, this month I had to develop a random distribution of points inside a triangle using Grasshopper. The aim is then to CNC cut holes in a complex triangular mesh, so I started from a single triangle to understand the geometry and the mathematical possibilities to perform this operation.

If you need to create a random series of points on a surface, it is very simple: you just divide the surface using U and V parameters... and you can randomize U and V to obtain a random result.

The problem is that the distribution is not entirely random, but it follows the U and V pattern.
For a Sphere you will obtain points more concentrated on the poles.
In this particular case, in a triangle, you will obtain the points more concentrated in one of the vertices.

(the image show just the UV subdivision, without any random function)

After a brief research I discovered some possible solutions to solve this issue.

I will skip this option as it is not what I want, but you can always create a grid of points on the same plane of the triangle, and than pick only the points that are inside the borders.
Not random, and not what I am looking for.


One possible approach is to use math and random numbers.

There is a mathematical way to create a random point inside any given triangle. You can see an hardcore reference here. or an easier and more understandable version here. (at least for non-mathematicians)

The basic formula is:
P = aA + bB + cC.

"where a+b+c=1 and a,b,c are each ≥ 0. Knowing a and b permits you to calculate c=1-a-b. So if you can generate two random numbers a and b, each in [0,1], such that their sum ≤ 1, you’ve got a random point in your triangle."

I used this basic math in Grasshopper generating a C# script to generate points.
This is the script for your reference:

private void RunScript(double a, double b, double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Az, double Bz, double Cz, ref object Point)

    double c = 0;
    double px, py, pz;

    if (a + b > 1)
      a = 1 - a;
      b = 1 - b;

    c = 1 - a - b;

    px = (a * Ax) + (b * Bx) + (c * Cx);
    py = (a * Ay) + (b * By) + (c * Cy);
    pz = (a * Az) + (b * Bz) + (c * Cz);

    Point3d point1 = new Point3d(px, py, pz);
    Point = point1;

Running this script you can generate any number of points inside a triangle.
This is the result:

The problem now is... how can you control the distribution?!
The answer is, you can't. The points are randomly generated... If you could control them, they were not random. (mmm)

But in my particular case I wanted to generate points with a certain distance between each other... kind of "equally distributed in a random way...".

My solution (I'm not sure if it is the only possible solution...) is then to filter the result, eliminating all the points that are too close between each other with a certain threshold value.
To do this you need a big for-loop that checks all the distances between all the points, ad exclude the once that are in a certain radius. Really complex. (at least for me).

Thanks god there is a great tool Kangaroo that added a command in Grasshopper: removeDuplicatePts.

Exactly what it is needed in this case...!

After a filter with this tool, plus filtering all the points too close to the borders, this is the result:

(second image shows only the selected points, the circles represent the minimum distance between selected points)

(Just as a reference, to filter the points too close to the borders, I've created an offset of the borders, and tested if the points were inside or outside.)

This is a video to see the random generation changing the radius between points, and changing the quantity of points generated:

A different approach is to use the incredible tool called Kangaroo. (in the previous approach I've used only one of the math commands, but in this approach I will use the physics simulation)
You can create a definition similar to the one used by Daniel Picker in this video:

adapting it for a triangle or for a triangular mesh.
This is the result I've obtained in my case...: (the quality of the video is a bit poor... sorry...)

On the left side you see the definition by Daniel Picker adapted for this case. When I move the points of the triangle, Kangaroo re-calculate a repulsion with springs and re-distribute the points in the new resulting shape.

The problem that I have encountered is that the points are generated from a starting condition...
This means that probably a better way to do it would be to start with all the points in the center, and only then run Kangaroo.

This is the result with this second attempt:

The result is more accurate, or better to say that the points are distributed in a more even way.

There is surely a way to the same with Galapagos... but as I reached the desired result with the previous methods, I leave this to someone else... if you create a definition that solve the issue with Galapagos... well let me know, and I can add it here ;)


I hope to receive comments to understand if the approaches are correct, and if there are better ways to do the same thing, please let me know.
And I hope this will help someone with the same problem to solve!

No comments:

Post a Comment