Finding "lowest" point in a hollow on curve

I have some polycurves on which I want to find the lowest point in each hollow (I have many curves, pictured only some made up examples). I don’t want the lowest point on curve as a whole (which would be the curve ends), only in the hollow as seen from the vector & plane pictured (which is not aligned with the world plane normal direction).


(I could rotate-transform the curves and the guiding vector to align them all with the World Z, but I would prefer not to in this case). Anyway, most important to find the “lowest point” of the hollow without the rest of the curve (outside the hollow) getting involved.

What’s the super-smartest solution to this? :slight_smile:

// Rolf

What about the other lowest points on those curves? Looks to me like there could be as many as 6 in that curve in the middle.

Yes. This is why I have a vector in the illustration, and looking for the lowest point “as seen from the vector & plane pictured”. The Plane may be misleading. Only the direction matters (the plane is located above all the curves so the same vector direction applies for all curves).

“First hit” if it were a ray intersection from above, would be another perhaps simpler way of saying it. Edit: But ray-intersections would be slow since I would like to find the lowest point within say, 0.1 mm, and thus I would have to send an awful lots of rays against each curve to hit such a point. So I hope for a smarter way.

// Rolf

Is every polyline coplanar - all vertex points of one polyine lies in one plane?
If so, is your Vector coincident with such plane?

Yes, yes, … the last bit, the vector, hm, I must check this.

Edit: Yes, it is coplanar. Everything is coplanar.

// Rolf

One more question - are all polylines NON-Self-Intersecting?

I’m not sure of that, but if that can be tested I can skip them. I can do without the few which possibly would be self intersecting. I couldn’t find any command to test for this though, but if you know of any trick to check this I can filter such curves out.

// Rolf

curve self-intersection

What about projecting the curve to a plane, and iterating over the projected and non projected curve / polyline at the same time to figure out the distance (or faster: distance squared) between the two curves, and only returning the highest value?

Highest value (or longest distance for a line aligned with the pictured vector) would also have to be non-self-interstecting on its way up to the projected curve (or plane, which I have on top). That is one possibility. although I suspect that all the intersections that would be needed would be quite slow.

I’m fiddling with some code trying this out though. But hopefully there’s some smarter way that would have a better chance of being faster.

// Rolf

Would this be of use to you?

Hm, interesting. But I suspect that “Farthest point” would suffer from the same basic problem as any intersecting approach will suffer from - namely hitting parts of the curve which isin’t “facing” towards the vector I had in the picture. Farthest point in my example would always tend to be the endpoints of the curves, and that is exactly the problem I want to avoid.

However, for other cases this looks interesting. Sometime I really need the farthest point, although not in this case.

// Rolf

My rough approach would be:

  1. transform everything in XY plane in such way your vector is -Y
  2. now you will work (compare) only with Y coordinates of your polyline vertex points
  3. sort points from left to right (from lowest to highest, default comparer fro points)
  4. my first point on the left is at the begining my Max-Distance-Point
  5. scam from left to right and “analyze” relation btw points
    … something like that
    You will maybe have to sort points based on Y coords as well,and at thse same time keep track of relation btw original polyline index and sorted-point index.
    I will try later to do something…

Here are some example curves and their original orientation (actual curves from the data set). I have zillions of them to process.

Forum Deepest Hollow Point On (106.4 KB)

// Rolf

I’m not 100% clear on the question… would the following be correct? - of all the “hollows” (concavities defined from the vector’s point of view), you want to retrieve the closest one, and get the farthest point from the vector?

Also curious to understand what this is for, might help understand the problem. Looks like a topography, and the vector might be the sun angle?

perhaps this sequence:

  1. move a point away from the curve along the vector direction (an inverse vector, so to speak); you can move it far away, to approximate an infinite distance (i.e., sun rays, projections, conversion of a topo map, projection of meterorite fragments on topography, etc). Your curves look like a CT scan, so this may be hyrdology, and orebody, or parhaps slices of a forest
  2. pull that point to the curve, or try closest point on curve
  3. that should give you the lowest point
  4. you may have to write some filters, checking tangency at lowest point, or comparing distances of lowest point from the vector, and kick out some curves that don’t respond well to the filters, for manual editing
  5. failing that, brute force: using anemone, and for each curve, write a loop that projects a series of planes perpendicular to the vector that you want; and then check for curve intersection between those projected planes and your curve. You will need to write a filter for open ended curves, ignoring the first and/or second intersections if open ended
  6. of course, with a nod to Peter, C# will be best but also should be doable in native grasshopper components. Might be a bit slow, so what faster than doing them by end

Here’s my attempt of filtering out all non visible lines.

Forum Deepest Hollow Point On (145.9 KB)

Possible alteration should be that you’re not looking for the furthest point, but for a local minima.

1 Like

Just some quick typing while I wait for the McNeel dev meeting to start… (16.8 KB) (17.2 KB)

1 Like

Thank you all for your suggestions.

The solution which was closest to mine was markz, which had some problems (didn’t work at all when I opened it) but after some fixing here and there I got it working.

I found it interesting that you had tried basically the same approach as me, which I had implemented in C# but I just didn’t get valid intersection results (However, now looking at David Ruttens take on Intersections.LineLine with his examination of the parameters a & b I might get the C# version working, which probably would be pretty fast.

The final solution will probably be determined by speed. David Rutten’s solution is very fast. Very fast and very smart approach.

I will also try to combine these solutions with a “loop hole filter”. The curves can have loop holes. Perhaps a solution for this would be to assign “width” to the rays (by using parallel pairs of rays with distance = “width”) which would cause intersections when hityting the bottom of a “loop holes” with an entrance width less than the distance between the ray pairs.

I’ll do some more experimenting and be back with the final fastest and most “hole resilient” solution.

// Rolf

In the meantime, David Rutten’s take is cool (white balls are valid minima without any intersections for the vector in the white circle)

I’m still working on handling all “special cases” that show up once I run the algorithms on sharp data.

I encountered a problem with the case below (bundles of open & closed curves in the same plane). Since testing for intersections requires shooting against the right curves (I have zillions of them), I want them bundled together (pictured, a bundle of six curves to the left, and a bundle five curves to the right).

I have these curve-bundles in tree branches, like so (sometimes single curves, sometimes bundles like the curves above):


I would like to pick the “uppermost” of these curves, when there are more than one in the bundle (branch).

So I thought I could sum up all the Z values of each segment.From.Z value, then divide the sum by the segment count, and I would have a “height average” value for each curve, by which I could sort each branch and finally pick the one curve with highest such average. That would be the curve to finally probe for a concave minima.

I’ve tried to collect the average values and input them into the Sort component, but it seems I only get arbitrary results. What am I doing wrong? The code I thought would fix the sorting.

  private void RunScript(DataTree<Polyline> P, ref object A)
    var tree = P;
    var result_tree = new DataTree<double>();
    for (var i = 0; i < tree.Branches.Count; i++)
      var branch = tree.Branches[i];
      var path = new GH_Path(i);
      for (var j = 0; j < branch.Count; j++)
        var pline = branch[j];
        var n = pline.Count;
        // Sum(Z)/Cnt
        var z_sum = 0.0;
        for (var k = 0; k < n; k++)
          z_sum += pline.SegmentAt(k).From.Z;
        double z_avr = z_sum / n;
        result_tree.Add(z_avr, path);
    A = result_tree;

But for some reason this code produces astronomical numbers, why?
And, the sort component doesn’t do anything useful with it either, why? Not my day today. (597.8 KB)

// Rolf