How could I get the distance of a point to its nearest point?

Question

Say I got some points distribut on a sphere, how could I get the distance of each point to its nearest point, for example, in pic 1, there is a point A, and its nearest point is B, and what I want is the distance r_A, and for each point X, I need an r_X.

The Geometry Proximity node do provide a distance value, but for each point, the value is 0, if I use a Map Range node to invert the values, the values I got for the points is the maximum setted in Map Range node.

Could I make this in GN?

Answer 1

Since the nodes have evolved a lot over time, there are now more solutions available:

• For Blender 3.6+ ...just follow this guide
• For Blender 3.4+ check out @Patter's answer below
• For Blender 3.1+ use "The shortest edge trick"

...and if you want to get an overview of which node is available in which Blender version, follow this answer: Can't find the node! Which node is available in which Blender version?

Find Nearest Point (Blender 3.6+)

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

In this case, the node simply returns the index of the nearest element, which makes it just as easy to query its position with Sample Index:

_{(Blender 3.6+)}

"The shortest edge trick" (Blender 3.1+)

...that's what I call this technique now.

In contrast to the quadratic complexity approach, this technique offers the advantage that only a fraction of the vertices necessary for the calculation is created, since only a triangulated mesh is used as a basis.

So this approach has a clear advantage in terms of speed, especially when the number of points to be calculated is high (500+).

How does it work?

The basic idea here is to shorten all edges between the points proportionally, and thus find the closest point. This method saves a lot of calculations and complexity and is basically applicable to any shape (grid, sphere, cube, etc.):

In the case of a grid with slightly offset points, the principle of operation is simplified as follows:

If the points are now moved, the edge length changes, which always takes the shortest path due to triangulation:

The only necessary basis is therefore to always have an optimally triangulated mesh as a starting point.

Depending on the type of mesh, this can be achieved in different ways.

• In the case of a sphere you can simply use the node Convex Hull.
• If you are using a grid with the Distribute Points on Faces node, you can achieve the triangulated mesh with the example I outlined in this answer: Selectively join points using geometry nodes
• And for other shapes you can use various other tricks.

The rule is simply: if the points are connected at least once over the shortest distance by an edge, then you already have the necessary information.

What is the result?

In this concrete example, the solution applied to a sphere looks like this in the final result:

Step by step to the solution

1. First create your points with Distribute Points on Faces.

   

2. In the case of a sphere, the Convex Hull node makes it easy to obtain the required triangulated mesh without missing a point. For other shapes, it is best to create the mesh using the Triangulate (Shortest Diagonal) node.

   

3. Using the nodes Extrude Mesh, Split Edges and Separate Geometry you get the isolated edges of this mesh.

   

4. Then reduce the scale of each edge by half.

   

5. Now that the edges are reduced in proportion to their length, you can reliably find the nearest point with the node Geometry Proximity. If you then calculate the direction vector between your originally created points and the position results of Geometry Proximity, you will know in which direction the shortest vector points.

   

6. In the last step you only have to correct the length. Since you have shortened the edges by 50% before, you simply scale the direction vector by $4$, which is exactly the point you were looking for (Apart from a few minor rounding errors).

   

The final result is this (Each previously created point is here connected to the nearest point):

...and with animated Seed/Density it looks like this:

Here is an overview of the node group:

Here is the blend file (I added an additional view for debugging):

_{(Blender 3.1+)}

...and as a bonus I added the animation to the blend file too, because it's so nice to see the thing in motion (even though I won't win any beauty contests with the node tree, but it's meant as a little animation example).

Useful Hints

• This solution works best by converting a mesh into triangles with the shortest edge length! Quads are less suitable here, because they may produce false positives.
• If you do not use a sphere, it is best to create the mesh using the Triangulate (Shortest Diagonal) node.
• If you use a sphere, this works best with a sphere of the type Ico Sphere in a higher resolution.
• Remember: If you use a sphere like in this example, the calculated distance is of course also the shortest straight path between the points. The real distance on a sphere would actually be the angle between the points multiplied by the radius of the sphere. The angle is obtained with the formula: $\alpha = 2 \ast \arcsin (\frac {s}{r \ast 2})$
• If you get false positive results with this method due to closely spaced points or highly stretched triangles, simply change the scaling. For example, instead of first reducing the length with a factor of $0.5$ and then multiplying by $4$, you can reduce by a factor of $0.8$ and then multiply by $10$.

Answer 2

It is technicality possible, but I would recommend searching for a different solution. The idea is to create as many copies of an object as the number of points that are in said object (or produced on object). Then we move this copies far away, so that the distance between object copies is grater than any distance between points of one object. Then we selectively separate one vertex of each object and make it source position "geometry proximity node" the rest we use as target geometry. This will give us closest distances between points.

(I am working on a laptop so the picture quality is bad look at the pictures below)

I recommend you look at the geometry before all the delete nodes to make sure that the copies are spaced far enough. If they are not, then increase the mesh line offset.

Answer 3

For Blender version 3.4.1 I found another solution using newer nodes (which didn't exist at the time of the other answers):

• Edge Vertices
• Edges of Vertex
• Sample Index

It's several times faster than the older (still very nice) solution of @quellenform (depends on the number of points but I saw improvements of > 100x). Another advantage is that there is no problem with "false positives".

Idea:

• Find the index of the shortest edge for each vertex by Edges of Vertex sorting by the edge length (given by Edge Vertices)
• For each vertex find the other end of that shortest edge (sample the vertex indices of both ends of the shortest edge by Sample Index and then find out which is the one with another index than the current vertex).

Blend file:

It just creates cones pointing to the nearest other point (cone length = 1/2 distance).

For comparison it also contains the solution of @quellenform (Find Nearest 1) and a group making a triangulated mesh from points distributed on a surface (and that original surface) (Surface Points to Mesh).

Find Nearest 2 node group:

Simple example:

Also works with non-convex meshes:
(this is not a feature of the Find Nearest 2 node but of the helper node Surface Points to Mesh)