Populate 2D sampling algorithm.

I noticed the density of the random points generated by the Populate 2D component looks very uniform. I wonder if it is based on Poison sampling algorithm or something similar? I planned to implement Poison disc sampling for Grasshopper but if the Populate 2D already uses this method I guess I can just extract the random numbers from it. Thanks.

Replies to This Discussion

Permalink Reply by David Rutten on October 11, 2013 at 7:10am

Hi Long,

it's a conditional random insertion algorithm. All the populate components work the same way. A number of random points are generated (depends on how large the pointset already is) and the one that is furthest away from all existing points is picked. Then generate more random points for the next iteration.

This doesn't guarantee that the points are really properly distributed, but it's fairly fast and it works on all types of geometry. However if the base geometry is extremely unbalanced (for example a mesh with a single enormous face and 10,000 tiny ones around the edges) then the distribution will reflect this.

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Long Nguyen on October 11, 2013 at 8:16am

Hi David

Thanks for the clarification. So each iteration in your algorithm will add only one point to the current set right. So seems like you have to generate a lot of random points and do lots of distance comparision. Sounds like your complexity is N^2, While the fastest poison disc sampling implementation that I know is NlogN. So perhaps poison is still faster, I will give it a try and let you know.

Thanks

Long

Permalink Reply by David Rutten on October 11, 2013 at 8:35am

True, for each point I end up adding to the set I generate somewhere between 10 and 1000 unused ones (to the nearest order of magnitude). However the distance check is not N^2, I use an adaptive oc-tree for fast Log(N) lookup.

David Rutten

david@mcneel.com

Tirol, Austria

RSS