I feel Populate Geometry is too slow comparing to its simple functionality.

For example, 50000 points takes 14mins on my machine. Populate 2D was even slower.

Why is this? Is it computing Voronoi diagram or something?

Is there a way to speed this up?

Populate geometry is not so simple because it looks at distance between points. There are some discussion on that on old Grasshopper forum

https://www.grasshopper3d.com/m/discussion?id=2985220%3ATopic%3A929095

You could go a lot faster with mesh and populating without looking at distance.

Here a script for mesh.

100 000 points in 1 s

I think I publiate it on a dendro topics.

fast mesh populate LEGACY.gh (32.6 KB)

```
/// <summary>
/// Fast populate on mesh using triangle populate, but gives more density on edges
///Laurent Delrieu 18/8/2019
/// </summary>
/// <param name="mesh"></param>
/// <param name="nPoints">number of point wanted</param>
/// <param name="seed">seed parameter for the random generator</param>
/// <returns>List of points</returns>
List<Point3d> MeshPopulate(Mesh mesh, int nPoints, int seed)
{
Mesh m = mesh.DuplicateMesh();
m.Faces.ConvertQuadsToTriangles();
Random rnd = new Random(seed);
// List<double> surfaceFaces = new List<double>();
List<double> sumSurfaceFaces = new List<double>();
List<Point3d> points = new List<Point3d>();
double totalArea = 0.0;
for (int i = 0; i < m.Faces.Count; i++)
{
double area = MeshFaceArea(i, m);
totalArea += area;
sumSurfaceFaces.Add(totalArea);
}
for (int i = 0; i < m.Faces.Count; i++)
{
double pointsOnAllFacesBefore = 0.0;
if (i > 0)
{
pointsOnAllFacesBefore = (double) nPoints * sumSurfaceFaces[i - 1] / totalArea;
}
double pointsOnAllFaces = (double) nPoints * sumSurfaceFaces[i] / totalArea;
int nPointOnFace = (int) Math.Max((int) pointsOnAllFaces - (int) pointsOnAllFacesBefore, 0);
points.AddRange(PointsOnMeshFace(i, m, nPointOnFace, rnd));
}
return points;
}
/// <summary>
/// Populate a TRIANGULAR FACE
/// </summary>
/// <param name="meshfaceindex"></param>
/// <param name="m"></param>
/// <param name="n"></param>
/// <param name="rnd"></param>
/// <returns></returns>
List<Point3d> PointsOnMeshFace(int meshfaceindex, Mesh m, int n, Random rnd)
{
List<Point3d> points = new List<Point3d>();
//get points into a nice, concise format
Point3d[] pts = new Point3d[4];
pts[0] = m.Vertices[m.Faces[meshfaceindex].A];
pts[1] = m.Vertices[m.Faces[meshfaceindex].B];
pts[2] = m.Vertices[m.Faces[meshfaceindex].C];
Vector3d v1 = m.Vertices[m.Faces[meshfaceindex].C] - m.Vertices[m.Faces[meshfaceindex].A];
Vector3d v2 = m.Vertices[m.Faces[meshfaceindex].B] - m.Vertices[m.Faces[meshfaceindex].A];
for (int i = 0; i < n; i++)
{
double b1 = rnd.NextDouble();
double b2 = rnd.NextDouble();
if ((b2 + b1) > 1.0)
{
b2 = 1.0 - b2;
b1 = 1.0 - b1;
}
points.Add((Point3d) m.Vertices[m.Faces[meshfaceindex].A] + v1 * b1 + v2 * b2);
}
return points;
}
//Algorithm
//http://james-ramsden.com/area-of-a-mesh-face-in-c-in-grasshopper/
double MeshFaceArea(int meshfaceindex, Mesh m)
{
//get points into a nice, concise format
Point3d[] pts = new Point3d[4];
pts[0] = m.Vertices[m.Faces[meshfaceindex].A];
pts[1] = m.Vertices[m.Faces[meshfaceindex].B];
pts[2] = m.Vertices[m.Faces[meshfaceindex].C];
if(m.Faces[meshfaceindex].IsQuad) pts[3] = m.Vertices[m.Faces[meshfaceindex].D];
//calculate areas of triangles
double a = pts[0].DistanceTo(pts[1]);
double b = pts[1].DistanceTo(pts[2]);
double c = pts[2].DistanceTo(pts[0]);
double p = 0.5 * (a + b + c);
//Added 18/08/2019 Math.Max to suppress less than 0 value and NaN on 0 area mesh
double area1 = Math.Sqrt(Math.Max(p * (p - a) * (p - b) * (p - c), 0.0));
//if quad, calc area of second triangle
double area2 = 0;
if(m.Faces[meshfaceindex].IsQuad)
{
a = pts[0].DistanceTo(pts[2]);
b = pts[2].DistanceTo(pts[3]);
c = pts[3].DistanceTo(pts[0]);
p = 0.5 * (a + b + c);
//Added 18/08/2019 Math.Max to suppress less than 0 value and NaN on 0 area mesh
area2 = Math.Sqrt(Math.Max(p * (p - a) * (p - b) * (p - c), 0.0));
}
return area1 + area2;
}
```

Thanks Laurent! This is helpful! Maybe Iâ€™ll use a simple orthogonal grid instead

Populate Geometry is an O(n^{2}) algorithm where it looks for a good position which isnâ€™t too close to any existing point. And many points are tried for at most 1000 times. `50000*50000/2*1000/2=`

is a huge number.

@mikity_kogekoge you can always aim high and implement this one if you need uniform feature - http://graphics.cs.umass.edu/pubs/sa_2010.pdf

If you do so make sure to share it with us

Hello, Iâ€™m trying to write a nearly O(n) algorithm for this.

The idea is a sort of Astronomical simulationâ€¦(so, itâ€™s not exactly the same to the Poisson sampling)

Obviously there are nxn pairs to evaluate, but only pairs that are close to each other need to be evaluated, which can suppress the computations lower than n2.

The prototype attached has two issues so far. (some points pop out, points march along a curve slightly inset from the boundary curve.)

But the performance is already good.

pts |Astronomical Simulation |Polulate Geometry

5000pt |21s |11s

50000pt |4.1m | 14.4m

As can be seen from the attached image below, the distribution of the points is more uniform.

But I assume, the random-ness in the Poisson sampling is something intended.

It would be great if someone give me some feedback before further proceeding.

Thanks!

(the rhino file attached below is very big, as it contains 50000points in the document)

sampling.3dm (18.6 MB)

sampling.gh (10.0 KB)

(left, astronomical simulation, right, Populate Geoemtry)

Okay, worked it out. Removed some issues and brought in parallel computing.

The result is, 2.3mins for 50000 points. (Core i7, 1.8Ghz)

sampling.gh (14.6 KB)

There is still place for improvement

Resulting in this

Unfortunately, I canâ€™t disclose internals for it But it does pretty much the same

18seconds! nice!

Umm Itâ€™s actually 0,18 s => ~180 ms and it does more than just generaing those. I would have to dive with profiler in it to get pregeneration time value only

180ms!

Iâ€™m curious whatâ€™s the order of your algorithm? since there is a chance you are using 100x faster machine/languageâ€¦(my script is written in Python, yours may be in C++)

This measured time suggests that my script is nearly O(n). (it should fall somewhere between O(n) and O(n2))

I rewrote your code in C# and it was like 20x faster. Iâ€™d recommend to try avoiding `dict`

as they are quite slow.

Tried many of thoseâ€¦ Iâ€™m using here a bit of Poisson with own multithreaded twist

Nope my is C# - Iâ€™m not aware of Py overhead but it may also lay in structures @gankeyu points exactly that some of those are causing unnecessary and big overheads Rule of thumb wherever you can use a finite array of elements youâ€™ll be surprised how it can speed up things - dynamic allocation of memory just have itâ€™s time cost

Not true at least in Python, especially if you do a lot of searching, **dictionaries are far faster** and superior in comparison to lists or tuples, especially if you add new values on the fly. Lookups in lists are O(n) and in **dictionaries O(1)** on average. Sets can even be faster, but you canâ€™t easily associate data to other data. Dictionaries and sets are hash tables which are fast but memory hungry

True, and Iâ€™d even add one-dimensional, butâ€¦

â€¦ as I understand it, itâ€™s not the dynamic allocation thatâ€™s the problem in this case. *Dynamic allocation* refers to storing data in heap memory (dynamic memory), as opposed to on the stack. Btw, in C# nearly everything is heap allocated.

The **copying** is the issue here. Finite arrays stay at a fixed memory address and a fixed amount of space has been pre-allocated for the data type to be stored. Other data structure, like lists, vectors, and so fourth that you can on the fly add to, allocate only so much memory when they are instantiated. While adding elements, once the memory has been filled, the entire data structure needs to get copied to another memory location, where more space is available, and this copying takes a lot of time and happens over and over the more items you add.

Perfectly explained. My explanation just wasnâ€™t precise enough

What is the GUI from that youâ€™re showing above in your preview?

Oh, now I see where the highly optimised algorithms come into play! Looks promising!!

`dict`

is faster if you are doing an arbitrary-key lookup. But the OP was utilizing `dict`

as a way to store sequential data. He used `0`

, `1`

, `2`

â€¦ as keys, under which situation `list`

is almost a better alternative.

Btw, in C# nearly everything is heap allocated.

Yes. The issue here is in OPâ€™s code, tons of list are created dynamically, which are big performance overheads.

OPâ€™s code is a mess! I took a quick peek, but quickly gave up. I mean no offense @mikity_kogekoge, but you should take a look at PEP8.