Hausdorff distance

Do rhino have a implementation of the hausdorff distance between surfaces to surface or curve to curve?

At the moment I am writing it in python script but is also contend with a c++ answer :slight_smile:

I don’t think so. How would to implement it? Sampling of points on the surface or curves, or would you use the parametric nature of the NURBS?

This thread over on the Grasshopper forum has a couple of different approaches for “curve to curve”. I attached Giulio’s definition which demonstrates how to use the Curve.ClosestPoints() method in Python, C# and VB. Hope that helps…

141127_ClosestPointOnCrv.ghx (82.3 KB)

Thanks for the reply and the code.

I think points is not a good idea sound slow. Think that there are some method that use the parametric nature of NURBS to calculate it, maybe it will only be a approximation .

It is a quite different problem doing Hausdorff distance that closestpointOnCrv since it explode in time consuming.

if we think of a method that uses point the if closestpointOnCrv runes in O(N^2) time, Hausdorff distance would run in O(N^3) time.

If you go the points way, it is possible to use RTree datastructures. These facilitate searching greatly, as indicated in this paper http://delab.csd.auth.gr/papers/SIGMOD00cmtv.pdf

I have implemented the closest pair query on two meshes/pointclouds using this approach, finding the one point on each mesh for which the distance is smallest. This performs much better than O(N2). It sounds like Hausdorff distance is a similar problem, only finding the pair of points whose distance is largest, rather than smallest.

The linked script seems unavailable both on this website and on the older website. Do you still have it?

Afraid not, that’s a long time ago. Here’s a quick new implementation:

220131_CurveClosestPoints_00.gh (7.4 KB)

1 Like

Oh, that easy. Didn’t realize that from that thread.

1 Like