Is there any faster method to compute curve closest point?

I’m trying to compute the closest distance between a list of points and multiple curves and cull the points with distances greater than “X”.

When I increase the number of points and curves to compute, the grasshopper native component’s time elapsed is relatively slow. So, I wondered if any has a better method to compute this process.

I tried some Rhino common in Python but still not getting a smooth method.

Crv_ClosestPoint.gh (131.2 KB)

Hi Uri, great to see you Pythoning :slight_smile: Before threading I always implement these performance tips:

In this case, just dropping type hints substantially speeds things up:


Crv_ClosestPoint.gh (93.8 KB)

Try implementing the outer looping as well (i.e. don’t use the implicit cycles) and see if the speeds things up even further. Then we can look at threading.

2 Likes

Your code has some problems. Besides culling the points that are more than max distance from the curve, it is also culling the points less than max distance that are closest to the curve at parameter (t) 0.

Instead of using the (out) t parameter to cull the points, you should use the True/False return value.

This python code produces output that matches the output from the gh native components (it is also a little faster 1.1 sec. → 744 ms.).

import Rhino.Geometry as rg
import Grasshopper.Kernel.Types as gkt

# Initialize the results list
results = []

# Loop over points
for point in point_list:
    if curve.ClosestPoint(point, max)[0]:
        results.append(gkt.GH_Point(point))

This does speed things up, but not by much (744 ms. → 734 ms.).

import Rhino.Geometry as rg
import Grasshopper.Kernel.Types as gkt
import ghpythonlib.treehelpers as th

# Initialize the results list
results = []

# Loop over points
for curve in curve_list:
    culled_points = []
    for point in point_list:
        if curve.ClosestPoint(point, max)[0]:
            culled_points.append(gkt.GH_Point(point))
    results.append(culled_points)
results = th.list_to_tree(results)

Switching to C# produces the fastest results (734 ms. → 205 ms.).

DataTree<Point3d> outTree = new DataTree<Point3d>();

for (int i = 0; i < curves.Count; i++)
{
    for (int j = 0; j < points.Count; j++)
    {
        double t;
        if (curves[i].ClosestPoint(points[j], out t, max))
        {
            outTree.Add(points[j], new GH_Path(i));
        }
    }
}
results = outTree;

Crv_ClosestPoint_re.gh (93.6 KB)

-Kevin

4 Likes

The C# solution can also with hints of System.Object.

    DataTree<Point3d> outtree = new DataTree<Point3d>();
    int i = 0;
    foreach(Curve c in curves)
    {
      GH_Path path = new GH_Path(i++);
      foreach (Point3d p in points)
      {
        double t;
        if (c.ClosestPoint(p, out t, max))
        {
          outtree.Add(p, path);
        }
      }
    }
  results = outtree;

Crv_ClosestPoint_re.gh (91.8 KB)

5 Likes

Depends on what precision you need, but i always use a different approach that is magnitudes faster:

  • convert your curves to polylines with an appropriate resolution
  • create mesh strips from the lines (e.g. simple quads by moving the points up 0.01 in Z)
  • join all meshes
  • run Rhino.Geometry.Mesh.ClosestPoint

This is 100 or 1000 times faster than any curve closest point method + it does not get noticeably slower with bigger meshes… That’s because mesh CP methods build a mesh AABB acceleration structure on the first call that is saved with the mesh.

It is a bit more work, but for me the time-saving was always worth it

4 Likes

In addition to the obvious solution of dropping to a lower level language (plus compiling). In this case, the higher level logic can be improved by implementing an appropriate geometry type (i.e. your curves are actually lines) and experimenting a bit with the looping (e.g. breaking out of the inner loop when you find a hit):


230409_Crv_ClosestPoint_Anders.gh (90.0 KB)

I bet @Tao_Lin’s implementation would be super duper fast with lines :fire:

7 Likes

Yes, you are right.

Hello, I was wondering if anybody has made a Curve Closest point with a number count? Just like in Closest Points, where we can set a limit to how many points we search?

given a point P and a curve C, Curve Closest Point finds the closest point to P along the curve C:
what do you mean by second closest point? I’m having difficulties understanding how you would define that? :slight_smile:

Hi, Inno.

I’m just asking for a list of closest point to that curve, like the one in Closest Points component. The relevance to this is if I want to find maybe 2 of the closest points or 3… etc.

You mean curve closest point and i think he mean points closest to curve ,
well it could be done by sort by distance and choose n first relative points