Curve.Contains Method too slow

v6
v5

(Przemysław Doliwa) #1

I’d like to check if points are in curve but existing implementation is too slow for me any ideas for workarounds here? For 4k pts and 100 crvs it takes ~1sec on a quite decent machine ~70% of time it checks if point is in or out and i have to live update screen during the change of parameters influencing size of crv for eg. - so it gives me one frame per sec while 4k pts is rather small amount in my case…

AD 1
I’ve tested a couple of times and its init takes a lot of time. I’ve limited points to compare for Contains by bbox (i’m testing min max of bbox for that) and i had hope i’ll get huge improvement on same 4k pts but i see only little probably i should go and divide bbox with grid and go deeper.


#2

In curve or on curve? I read “in” curve, but what is meant with that?

// Rolf


(Przemysław Doliwa) #3

@RIL In curve Rolf. That means that certain point from list is inside boundary of curve - in other words this curve contains certain point :smiley:


#4

OK. I guess I’m just not used to work with inclusion of coplanar curve points (only point inclusion in 3D space).

Not knowing what “existing implementation” represents (a component, or your code?), I would try - If the curves are convex - to calc the area centroid (cp) and use a line intersection form cp crossing the curve (ip) - through your point (pt) - and check if the point (pt) or the intersection point (ip) is closer or equal distance to cp. if so, then pt is inside.

If the curve is not convex, then your point must be located either closer to the cp than the intersection point index 0, or between intersection point (index) 1 and 2, or between (index) 3 and 4, etc.

Using Parallel.For should do this fairly quickly. How are you currently calculating the inclusion?

// Rolf


(Tom) #5

what kind of curves are you talking about? Nurbs, Polylines, Circles…2d, 3d?What is the average controlpoint count?


(Przemysław Doliwa) #6

@RIL I’ll consider this :slight_smile: Thanks :slight_smile: Rolf i use:

foreach pt in pts
if ptx and y is in bbox
crv.Contains(pt);

@TomTom User picks own crv there’s no limitation besides it has to be closed - but this is a good idea to inform user crv should be less or equal to deg 3 and should have smallest possible cp amount - i wonder if that have such big impact when calculating points with Contains.


#7

Ah, I didn’t realize you were talking about curve points. And only now I see the “Curve.Contains” on the subject line.

I blame my lack of sleep. :slight_smile:

// Rolf


(Przemysław Doliwa) #8

@RIL Rolf i have set of points and crv on top and i want to pick points in this crv - i wonder if using control polygon wouldn’t be even faster. Hmm maybe i could get it through http://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Curve_CreateControlPointCurve.htm

But if crv will have concave i’ll miss some of them hmm … but i could try to make hull on control polygon …

I need to rethink how to make less iterations for Contains method to get better performance or somehow make own substitute of it.


#9

The strategy I mentioned should work, but to know if it’s faster than the Curve.Contains one would have to test it. I mentioned how to test for concave closed curves. They’d have to be projected to a plane to become coplanar of course, but it should work.

// Rolf


(qythium) #11

I believe the Curve.Contains method would already include some sort of fast rejection criteria based on the bounding box or convex hull, which is why your testing of pt in bbox doesn’t affect performance.

You could try constructing some sort of spatial search structure like the built in RTree for both your curve internal region and the points, and test for overlaps between the two trees. The initial construction might be slow but you would most likely see a speedup for live updating if one of the structures does not have to be recalculated between iterations.


#12

I’m not fully clear over what you base the selection on. Are you testing a point for inclusion inside all the “hull” of all curves, or can the user pick one curve and expect to get all the points inside only that curve?

It would be interesting to see an example of what you have.

If you want all curves to form an “common area” where the outer most curve segements form the boundary for the point inclusion test, I can think of different more or less creative methods to solve the problem.

But any strategy would of course have to be tested to see if is is any faster than any other.

// Rolf


(Przemysław Doliwa) #13

@RIL Rolf i shouldn’t disclose it but here you are it has to solve sort of clustering process:



#14

As I understand it points should be selected based on inclusion in one (1) curve, and as soon as one point is part of (or inside) one curve, or area, it no longer has to be tested for in other curves(areas)? Is that correct?

Anyway, I tested my idea in code, but the CurveCurve intersection method doesn’t return an array of intersecting points like some of the other methods do, so my strategy doesn’t work with this intersection method in code (see code far below, but the “res” will only contain maximum two points if an intersection occurs).

But with the GrassHopper component “Curve |Line (CLX)” the intersections seems all have been picked up, but I have not enough experience of DataTree’s to traverse the tree to get the points (which should be handled in the order I handle them in the code snippet below, if you just get the individual result-arrays per intersection out of the tree):

Fig 1. Some weird forms based on Curves -> Surfaces -> Boolean -> Surface Border Curve, which then was tested for intersection for each point in the picture. Count the number of “hits” from the center along the lines, and check distances or index = modulo 2 reminder and keep all points which have shorter distance than this curve intersection point index (phew).

PointInCurve.gh (14.2 KB)

Unfortunately I couldn’t prove my claim in the code below, but someone who masters examining the unbalanced data tree can fix such inclusion tests using the CLX component. When I tried this form didn’t know the forms you used, but my form isn’t any simpler it seems…

  private void RunScript(Point3d CP, Curve Crv, List<Point3d> P, ref object F)
  {
    var boolfilter = new bool[P.Count];

    var line = new Line();
    line.From = CP;
    for (var i = 0;i < P.Count;i++)
    {
      var pt = P[i];
      line.To = pt;
      var crv = line.ToNurbsCurve();
      
      // This "res" should have been an array of hit points, 
      // but now it isn't, so my strategy failed. Otherwise
      // this would have returned all points inside the shape's
      // border curve.      
      var res = Rhino.Geometry.Intersect.Intersection.CurveCurve(Crv, crv, 0.001, 0.001);
      for (var j = 0; j < res.Count;j++)
      {
        if (j % 2 == 0.0)
        {
          var hit_pt = Point3d.Unset; // should have been = res[j];
          var dist_ct2pt = CP.DistanceTo(pt);
          var dist_crvpt = CP.DistanceTo(hit_pt);
          if (dist_ct2pt <= dist_crvpt)
          {
            boolfilter[i] = true;
          }
        }
      }
    }
    F = boolfilter;
  }

// Rolf


(qythium) #15

Turns out that if you cast the closed curve into a trimmed boundary surface (which has an explicitly defined Inside and Outside), testing for inclusion becomes instantly ~3x faster.

And then if you sacrifice a little bit of accuracy by discretizing the surface into a mesh, using MeshRay intersections ( which I assume are heavily optimized ) brings that to a 12x speed increase.

This is all with native GH components and Goo casting, you could probably bring that down by a few more factors using code and parallel optimizations :slight_smile:
optimize_pointincurve.gh (17.6 KB)


(Przemysław Doliwa) #16

@RIL @qythium Thanks so much guys i’ll dive in those concepts tommorow and will test whats best here :slight_smile:


#17

If I recall correctly the GH component CLX is rather slow, so the GH version of my strategy probably won’t do the job any faster.

// Rolf


(Przemysław Doliwa) #18

@RIL At the end of the day it won’t be in gh i just use gh for faster seeing whats going on instead of pushing stuf to conduict and making ui for params :wink: Tommorow i’ll try to write your concept down :wink:

@qythium Your attempts was promising but in case “user is mad” only Contains in curves work :wink: Look below:


But indeed mesh ray is blazing fast.


(qythium) #19

In that case you could simply add an additional step to detect self intersections, split and join the curve before meshing –


(Przemysław Doliwa) #20

@RIL @qythium I wrote code with meshray and it behaves much better ~6-7 times faster than Contains method i also compared concepts (unfortunatelly without writing CLX concept) but gh shows clearly that mesh ray gets full result much quicker than CLX intersection points.

I wonder if there is anything more i can do here - for 10k pts and 200 crvs i get result in 450-600 ms which still can’t be called live preview :smile:

AD.1 it’s very interesting that adding next curves ( now 2k ) incresed lag only 100ms


#21

What happens if you use a vertical BrepFace and rotate it from a center point or from any point inside the area, towards any of the points, and then intersect it with the curve? (the help file doesn’t say if the curve must be open or if it accepts closed curves).

CurveBrepFace returns an array of intersections which is useful in case of a concave curve.

http://developer.rhino3d.com/5/api/RhinoCommonWin/html/M_Rhino_Geometry_Intersect_Intersection_CurveBrepFace.htm

// Rolf