Selectively join points using geometry nodes

Question

I'm trying to connect a set of points to their nearest neighbour.

Steps I took:

Instance some points on a grid

Add a curve at each point and realize so I can affect them individually

Move the endpoint of each curve

I think I'm misunderstanding what Transfer Attribute is doing. I thought this is saying:

Take the points on my grid, calculate the closest point to each point, pass the field of those positions as an attribute. The Set Position node is then taking that field of positions and using it to move the endpoints of each curve.

Clearly, I'm missing something though!

Answer 1

Blender 3.6+

This answer is technically the same solution as shown here:
How could I get the distance of a point to its nearest point?

With Blender version 3.6 a new node is available that makes this task a lot easier: Index of Nearest.

The node Index of Nearest simply returns the index of the nearest point, which makes it just as easy to query its position with Sample Index. Then you just need to instantiate lines, and move their endpoints to the position of the nearest point:

_{(Blender 3.6+)}

Blender 3.1+

The desired result can be achieved with the technique The shortest edge trick.

All you have to do is to convert your randomly generated points into a triangulated mesh and apply the following principle:

If you use the node Distribute Points on Faces, you can achieve the triangulated mesh you need in this way, for example:

But if you use the node Distribute Points on Faces to create only the points, there is also a convenient alternative: The node Voronoi Texture.

If you only need randomly distributed points that you want to connect, it is sometimes easier to create a triangulated mesh directly instead of turning points into a triangulated mesh.

Here's an example of how that can work:

Once such a mesh is available, and this is actually the more complicated part in this case, it is easy to find out the shortest distance.

The procedure in this case would be as follows:

1. Create your points on a grid

   

2. Create the triangulated mesh

   

3. Shorten the edges by a certain factor

   

4. Find the nearest edge and instantiate your lines there.

   

Here is the blend file:

_{(Blender 3.1+)}

Answer 2

Even if this one is not as elegant as the one of quellenform, I will explain it as just another way to solve the task.

The Algorithm

First, we create a copy of the point cloud for every point in the cloud. We store the original index at every point in this cloud. Only, this copy does not include the original point itself. Then we take every combination of point and correlating point set, calculate the distance to this point for every point in the set and store this value at the point in the set.

We create another copy of the original point cloud and place every point of this cloud on the x-axis. These points are placed in a distance, that is greater than the maximum of all distances that we computed before. Every of these points represents the index of an original point.

Now, for every of the above created point sets, we place the points of the set in z-direction above the corresponding index point. And we place them in the distance that we computed before (z = distance).

Starting at the original points, this allows us to access the index point based on the index of the original point. Using the index point, we can find the nearest point of the generated sets. And using the index, that we stored at this point, we can access the position of the original point. Finally, this allows us, to draw a line from the starting point to this point, which is the closest point in the original set.

Implementing the Algorithm

We start with generating the large N*(N-1) point cloud:

First the index of every original point is saved as the Group ID at the point by using a Capture Attribute node. Next a Mesh Line with N-1 points is initialized on every of these points. The original Mesh Line Index is conserved by using a Capture Attribute node again.

As we want to skip a different point in every subset, we use the Mesh Line Index to calculate the “Original Index” for every point. Then we place every point of the Mesh Lines directly on the original points, so that we can use them to calculate distances.

Now that everything is prepared and in place, calculating the distances for every combination of 2 points is easy:

The distance value is saved at the points of the N*(N-1) points by using a Capture Attribute node.

The distance values allow us, to place all points in the manner that is displayed in the first image up above. These are the nodes, used for doing this:

Next, the index of the closest original point is stored at every point in the N*(N-1) points with a Capture Attribute node.

Finally, the lines are created. We start by placing the first point of every line directly on one of the original points:

To place the second point of each line, we get the index of the closest point from the point cloud based on the starting point index of each line. We use this index in order to read the position of the original point and place the second point of the current line directly on it.

The only thing left to do is, to merge all points by distance and visualize the result.

Answer 3

Blender 3.4 introduced Mesh Topology Nodes, which allow efficient sorting. This makes it easier not only to find the nearest point (BTW, there's a special node coming to find nearest element not counting self), but also multiple nearest points.

Part 1: Connect All Points

Connect each point with every other point (also with self, doesn't matter):

Part 2: Find nearest(s)

Now merge "doubles" and for each find the shortest connected edge using the new topology node "Edges of Vertex". Because you want to access this information later in the edge domain to delete "unused" edges, create a mapping simply by positioning the points on the XYZ = edge's index, then for each edge you can check if a point was moved to its index as XYZ:

Above I also repeat it for the 2nd and 3rd nearest and it should be clear how to continue adding more nearest. You could make the number of nearest elements dynamic, by repeating the quadratic "Instance on Points" self on self trick in order to produce more points for the "map":

This time I used anonymous capture attributes to show that you can. I also added a check for min/max length because Urfbs asked for it.

Part 3: Display the result

Here's the result as well as the missing part of the node tree to accomplish it - just in case the .blend file is unavailable: