# "The shortest edge trick"

*...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:

[![How could I get the distance of a point to its nearest point - Concept][3]][3]

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

[![How could I get the distance of a point to its nearest point - Concept Animation][4]][4]

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](https://blender.stackexchange.com/a/262410/145249)
- 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:

[![How could I get the distance of a point to its nearest point - Animation 1][1]][1]

[![How could I get the distance of a point to its nearest point - Animation 2][2]][2]

## Step by step to the solution

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

    [![How could I get the distance of a point to its nearest point - Step 1][5]][5]

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.

    [![How could I get the distance of a point to its nearest point - Step 2][6]][6]

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

    [![How could I get the distance of a point to its nearest point - Step 3][7]][7]

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

    [![How could I get the distance of a point to its nearest point - Step 4][8]][8]

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.

    [![How could I get the distance of a point to its nearest point - Step 5][9]][9]

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).

    [![How could I get the distance of a point to its nearest point - Step ][10]][10]

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

[![How could I get the distance of a point to its nearest point - Result][11]][11]

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

[![How could I get the distance of a point to its nearest point - Animation 3][12]][12]

Here is an overview of the node group:

[![How could I get the distance of a point to its nearest point - Node Group][13]][13]

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

[<img src="https://blend-exchange.com/embedImage.png?bid=0XVj1Vav" />](https://blend-exchange.com/b/0XVj1Vav/)

...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$.

  [1]: https://i.sstatic.net/kGjTd.gif
  [2]: https://i.sstatic.net/UWMz0.gif
  [3]: https://i.sstatic.net/b0BDt.jpg
  [4]: https://i.sstatic.net/tJmvH.gif
  [5]: https://i.sstatic.net/d0dul.jpg
  [6]: https://i.sstatic.net/vDkZT.jpg
  [7]: https://i.sstatic.net/XJyu9.jpg
  [8]: https://i.sstatic.net/GgDPV.jpg
  [9]: https://i.sstatic.net/7HEq0.jpg
  [10]: https://i.sstatic.net/zOBNa.jpg
  [11]: https://i.sstatic.net/yuvkz.jpg
  [12]: https://i.sstatic.net/1HW40.gif
  [13]: https://i.sstatic.net/u3eD2.png