Find closest point, on closest curve c#

Rhino Developer
1

Hi. Bit stuck here.

I need to find the closest point on the closest curve to a given point (last point known)

The only way I can do it now is to select all curves in the document then iterate through them to measure all the closest points and find the smallest one. its slow as buggery… worse is that the routine can be called into an existing model that may contain many hundreds of curves which would really drag it down.

is there a built in routine to find the closest object (irrespective of geometry) then iterate backwards through those to determine if its a curve or not?

Or any other method that would be efficient?

Thanks.

(NOTE: no command line selection on this, so no get routines… this will be in the middle of an active routine so input curves will be unknowns at the time its called.

2

Hi
I would use RTree class for this.

  1. Find BoundingBoxes (BB) for each object (curve)
  2. Populate RTree with these BB
  3. Call RTree.Search method on theses set with parameter BounidingBox which I would set to be bounding box between my testing pint and a point on lets say first object in the list of objects to test
  4. by calling Search method event will fire for every intersection of testing bounding box with BBoxes and callback method will be called for every event fired
  5. So you create your calback method where you can shrink testing bounding box by using some logic (origin of scale is your testing point), lets say by scale 0.5 size, and than search again (e.cancel has to be set to true in callback methot to stop testing other BB)
  6. If there is no intersection of BB and testing boxes than you should go back and enalrge testing box with scale factor 1.25 of actual size and RTree.Search againn
  7. You stop when scale change becomes small (you have to decide what it will be)
  8. You have to remember last boundong for which fire event occurs and than by using Rtree.Search with different callback method where you test for closest point of each object
  9. There is code for testing MashMash Collison where I use RTree for it,
    see my post at this topic
    Intersection.MeshMeshFast faster method?

If you need any further help let me know
Regards
Radovan

1 Like
3

Can it be speeded up by using this method and code given below?

http://developer.rhino3d.com/api/RhinoCommonWin/html/M_Rhino_Geometry_Curve_ClosestPoint_1.htm

double minDist = double.MaxValue;
Point3d closestPoint = Point3d.Unset;
double t;
Curve closest = null;
foreach(var curve in curves)
{
    if (curve.ClosestPoint(pt, out t, minDist)
    {
        Point3d at = curve.PointAt(t);
        double dist = at.DistanceTo(target);
        if (dist < minDist) 
        {
            minDist = dist; // minDist will be used in the next call to ClosestPoint
            closestPoint = at;
            closest = curve;
        }
    }
}
1 Like
4

Ill give that swing today… never measured performance diff between a regular for loop and a for each. Otherwise similar to how im doing it now but more legibly :wink:

5

It is not about the foreach vs for loop, they should be comparable in speed (actually, a for-loop is the faster of the two). It is about re-using the minDist parameter in the .ClosestPoint method with the shortest distance you have already found. If you already do that, then there should be no measurable change in performance.

6

Yeap, im pretty much there but in a for loop. the issue is that as user moves a block instance contain a reference point across a surface containing a perhaps only a few curves to many hundreds of curves the routine needs to repeat continuously always looking for the next closest curve as that will change as the object moves over a surface… then show the user the distance to that curve and implement a warning system if distance is less than x.xxmm. Runs ok with only a few curves but slows DRAMATICALLY once you pop a few dozen curves out there.

recoding today to do an initial for for loop to find all the curves and then isolate the top 20 closest ones, and if a curve “rating” 15 or below gets triggered then rerun the routine to find next 20 closest curves to keep the perpetually running for loop shorter…

Not sure im able to describe it any better than that, guess i was hoping that rhino had a built in high speed compiled version of “closest” object to a given point which i could extract all curves in a given radius. If that makes sense?

7

I guess you could speed things up by converting each curve to a coarse polyline and only testing point-to-point distances (create a Vector3d between the points and test for LengthSquared, that saves you a sqrt operation). This may miss the actual shortest distance, but as it is supposed to be a real-time guide to the user this might be less important?

To speed up even further, the points that represent each curve can be entered into an RTree to speed up searching.

1 Like
8

I mean this, I tested it on >100 curves with real-time responsiveness:

ObjRef[] cRefs;
Result res = RhinoGet.GetMultipleObjects("crvs", false, ObjectType.Curve, out cRefs);
if (res != Result.Success) return res;


double dist = 1.0;

Curve[] curves = cRefs.Select(r => r.Curve()).ToArray();
PolylineCurve[] polylines =
    curves.Select(c => c.ToPolyline(20, 0, RhinoMath.ToRadians(10), 0.1, 0, 0, 0, dist, true)).ToArray();
            

RTree tree = new RTree();
for (int i = 0; i < polylines.Length; ++i)
{
    var pl = polylines[i];
    for (int j = 0; j < pl.PointCount; ++j)
    {
        tree.Insert(pl.Point(j), i);
    }
}


GetPoint gp = new GetPoint();
gp.SetCommandPrompt("Select point");
gp.DynamicDraw += (o, a) =>
{
    BoundingBox bb = new BoundingBox(a.CurrentPoint, a.CurrentPoint);
    bb.Inflate(2*dist);

    HashSet<int> closeIds = new HashSet<int>();
    tree.Search(bb, (to, ta) =>
    {
        closeIds.Add(ta.Id);
    });

    if (!closeIds.Any())
        return;

    foreach(var i in closeIds)
    {
        Curve closest = curves[i];
        double t;
        if (closest.ClosestPoint(a.CurrentPoint, out t, dist))
            a.Display.DrawLine(a.CurrentPoint, closest.PointAt(t), Color.Red);
    }
};
gp.Get();

            
    foreach (var pl in polylines) doc.Objects.AddCurve(pl);
return Result.Success;
9

ha. Gave me an idea. All the curves are circle, so I only need a centre point, i can do a closets loop once i approach a point… may be lossy of user moves quickly and actually moves the block INSIDE an existing curve… but the user routine would have crashed anyway in that case so simply reporting no distance [quote=“menno, post:8, topic:45170”]
ObjRef[] cRefs;
Result res = RhinoGet.GetMultipleObjects(“crvs”, false, ObjectType.Curve, out cRefs);
if (res != Result.Success) return res;

double dist = 1.0;

Curve[] curves = cRefs.Select(r => r.Curve()).ToArray();
PolylineCurve[] polylines =
curves.Select(c => c.ToPolyline(20, 0, RhinoMath.ToRadians(10), 0.1, 0, 0, 0, dist, true)).ToArray();

RTree tree = new RTree();
for (int i = 0; i < polylines.Length; ++i)
{
var pl = polylines[i];
for (int j = 0; j < pl.PointCount; ++j)
{
tree.Insert(pl.Point(j), i);
}
}

GetPoint gp = new GetPoint();
gp.SetCommandPrompt(“Select point”);
gp.DynamicDraw += (o, a) =>
{
BoundingBox bb = new BoundingBox(a.CurrentPoint, a.CurrentPoint);
bb.Inflate(dist);

HashSet&lt;int&gt; closeIds = new HashSet&lt;int&gt;();
tree.Search(bb, (to, ta) =&gt;
{
    closeIds.Add(ta.Id);
});

if (!closeIds.Any())
    return;

foreach(var i in closeIds)
{
    Curve closest = curves[i];
    double t;
    if (closest.ClosestPoint(a.CurrentPoint, out t, dist))
        a.Display.DrawLine(a.CurrentPoint, closest.PointAt(t), Color.Red);
}

};
gp.Get();

foreach (var pl in polylines) doc.Objects.AddCurve(pl);

return Result.Success;
[/quote]

works damn well! my slowdown must be in some other part of my code then… back to the drawing board… Many thanks

10

Hi
If you want this code to run even more faster then =>

  1. instead of constructing Polyline is better to create Bounding Boxes for each curve and populate RTree with it:

var boundingBoxes = curves.Select((objR, index) => new { index, objR }).ToDictionary(x => x.index, y => y.objR.GetBoundingBox(true));
RTree tree = new RTree();
for (int i = 0; i < boundingBoxes.Count; i++)
{ tree.Insert(boundingBoxes[i], i); }

  1. instead of searching Tree with boundingbox (bb) around CurrentPoint is better to perform search with Sphere parameter:
    Sphere sphere = new Sphere(a.CurrentPoint, dist * 1.01);
    HashSet closeIds = new HashSet();
    tree.Search(sphere, (to, ta) => { closeIds.Add(ta.Id); } );

This will speed up code aprox 10 times but it does not have any impact on behaviuor with ineractive usage. I use this kind of code for collision detection while placing gemstomnes on surface and I guess this is something that you are doing as well.
But perfomance/speed becomes important when you try to use collison detection for examle if you want to write code which will do automaatic pave setting of predefined gemstones on selected surface. Such problem is usually solved with many iterations (i do not know other technical solution) and here speed does metter.
R

1 Like
11

Sorry for bumping this topic but i thought it will be the most relevant place to ask for this. Does Curve.ClosestPoint with maximumDistance parameter use internally RTree? @stevebaer @dale

I’d like to know that to eventually not wrap it in RTree if it has already that inside or it is just naive implementation - however, docs are saying: Past this distance, the search is given up and false is returned. what makes me wonder.

12

@D-W,

No.

The only thing Rhino has that is close to what is described above is Curve.ClosestPoints. Perhaps this is of some use.

– Dale

13

Hi @dale

Thanks for this info. It just realized that making rtree for single test point doesnt make sense :sweat: I guess more sense would have here just checking in bbox inflated by maxDist value. Anyway many thanks :wink:

[EDIT] It’s weird but even with many many curves tested against one tree of points it turns out that original API method is quicker - not much but still quicker :wink: