Finding the connected islands in a set of random points

I am working on a grasshopper definition to create a random pattern out of spheres that are populated on a 3d object’s exterior. It is fairly basic and looks something like this.


However, since the end goal is a 3D print, I would like to know the number of “islands” based on a point’s proximity to every other points populated around the object. This is so that I do not have any disconnected parts that would create large holes in the print. From my searching, it seems like a connected components graph is the way to achieve this goal using the closest point or point proximity component in Grasshopper.

I have found an article about connected components in an undirected graph and it seems like its is a step in the right direction, but I was wondering if someone here has made an implementation of this in a plugin or a python component. I have limited experience implementing algorithms, so any help would be greatly appreciated.

I have just put the code in the link inside a Python component, looks like working pretty well


point_islands_maybe.gh (20.8 KB)

mesh spheres represent isolated points (not connected within connection-range)
point islands are previewed with same colours

1 Like

Wow this is great! Thank you so much!

So besides the algorithm listed, you have added a bit of Grasshopper Tree wizardry that I would not have known how to do. I am sure its complicated, but can you explain some of what you did?

happy you liked it :slight_smile:

the basic flow is the following:

the Python script returns the indexes of the original points, not the points themselves (can be seen in A)
the data is organized like all the indexes of the points that fall within the set distance from each other (which means “that are part of the same island”) are listed under the same branch

group B process this information in this way:
list length component C returns how many items are inside each branch
so it tells us exactly how many points are inside each island

islands with exactly just 1 point are counted (in B)
→ then their indexes are used to return the original points in section E, which draws a sphere around them (so they are easy and fast to see)

islands with more than 1 point are counted (in B)
→ then their indexes are used to return the original points in section D, which previews each island with the same color

section D could be 90% shrinked by using a single component Random Color from the awesome plugin Wombat:

as always, this is just a “dirty prototype” to get to the final solution: there are for sure many ways to make this definition slender, faster, ecc etc
if you have 300 points then it’s ok like this… if you have 3 million points you might want to work it a bit more :slight_smile: a minute now can save one hour later :slight_smile:

2 Likes

Thank you for all this explanation! It is much appreciated

This python component has been working well most of the time. However, I am running into some problems with a file with around 7k points. It seems that once the point count gets over a certain number, I start getting sudden crashes in which Rhino closes without warning or an error report. Grasshopper thankfully saves a recovery file, but the crashes are quite annoying since they are unpredictable.

What would I want to do if I wanted to optimize the Python component so that it could (hopefully) handle more points?

it might easily be that the Python code can be optimized, I say this because mine was literally a copy paste from the original source linked in the first posts, and also because I’d really not be able to optimize it myself :slight_smile: (lack of knowledge)

I don’t know if it’s helpful, I noticed that by placing a data-dam in between the Proximity3D component and the Python, it handles even 15K points in less than 300ms, I didn’t try to push it further


point_islands_maybe_maybe.gh (22.7 KB)

but whenever the graph is fully connected (one single huge island) and has 5Kish+ points, it crashes regardless of the presence of the data-dem component

Update:

All along I thought that this had to be an operation that would be super simple and should be implemented right into grasshopper. Turns out, it is in fact a single component that is many times faster than any code I could write myself. I was looking for the “Point Groups” component.
image