How to find local extremes in curve 2d?

Scripting
1

I have curve Bspline dreegre 3, how to find local extremes by rhino script or command ?

2

You need to create the hodograph curve (see ch. 6.10 in this book http://tom.cs.byu.edu/~557/text/cagd.pdf). The hodograph is the derivative of the nurbs curve.

The local minima are located at points where the first derivative is zero.

Therefore you need to intersect the hodograph curve with the plane with origin (0,0,0) and normal (0,1,0) to get the parameters at which the first derivative is equal to zero, and evaluate the original curve with the parameters you find from the intersection.

3

Cool. You can then use the tangent of the holograph (sounds better) to distinguish between local minima and maxima. In the Grasshopper forum David Rutten mentioned that to find the extremes Rhino 5 uses the Newton method. I’m not sure why it has to find it numerically when you’ve got this solution.

This code seems to work (C#):

void LocalExtremes(Curve curve, Plane plane, out List min, out List max)
{
min = new List();
max = new List();
var hodograph = GetHodograph(curve.ToNurbsCurve());

var intersections = Rhino.Geometry.Intersect.Intersection.CurvePlane(
  hodograph, plane, RhinoDocument.ModelAbsoluteTolerance);

var parameters = intersections.Select(intersection => intersection.ParameterA);

foreach(double t in parameters)
{
  var point = curve.PointAt(t);
  var tangent = hodograph.TangentAt(t);

  if (plane.DistanceTo(new Point3d(tangent)) < 0)
    min.Add(point);
  else
    max.Add(point);
}

}

NurbsCurve GetHodograph(NurbsCurve curve)
{
int n = curve.Degree;
var points = new List();

for(int i = 0;i < curve.Points.Count - 1;i++)
{
  Point3d h = n * (new Point3d(curve.Points[i + 1].Location - curve.Points[i].Location)
    / (curve.Knots[i + n] - curve.Knots[i]));
  points.Add(h);
}

var hodograph = new NurbsCurve(n, curve.IsRational, n, points.Count);

for(int i = 0;i < points.Count;i++)
  hodograph.Points.SetPoint(i, points[i]);

for(int i = 1;i < curve.Knots.Count - 1;i++)
  hodograph.Knots[i - 1] = curve.Knots[i];

return hodograph;

}

4

Hi @mutsukokono, using a command, you might try _Curvature with option _MarkCurvature=_Yes then click on the white points displayed. From the Rhino helpfile:

White points mark the maximum curvature points in a portion on the curve where the curvature starts to decrease in both directions from the points. Black points mark the minimum curvature points where the curvature circle jumps from one side of the curve to the other side. The curvature at the black points is always 0.

c.

5

I’m not sure why it has to find it numerically when you’ve got this solution.

maybe because it also needs to work for non planar curves. Also, finding the hodograph plane intersection probably uses Newton or similar numerical approximation.

6

Why wouldn’t this work with non planar curves?

I don’t think he meant that one of the built in methods used in the algorithm uses a numerical method. It wouldn’t make sense in the context. Post is here: http://www.grasshopper3d.com/forum/topics/discussion-finding-highest

7

Because you are, in effect, only calculating a partial derivative. You’d have to intersect the hodograph with all the world planes to get all the partial derivatives, and then say something about local minima.

In the end it all depends on what algorithm is faster.

8

He said in 2D. I’s safely assume that he means planar curves.

9

As I understand the extremes are assumed to be calculated in reference to a single plane. It doesn’t matter if the curve is planar or not. It will return tangent vectors parallel to the plane no matter what direction.

I also realized this method returns some points that might not be considered local minima or maxima. In an S shaped curve there could be a point in the middle that is parallel to the plane but one side of it slopes down and the other up. A way to detect these points is when the tangent vector of the hodograph is also parallel to the plane. Something like:

if (Math.Abs(plane.DistanceTo(new Point3d(tangent))) < tolerance)

10

@GregArden, isn’t there a ‘smart’ way to do this with the SDK?

11

To help with this calculation, I’ve added a new RhinoCurveExtremeParameters SDK function to the forthcoming Rhino 6 C++ SDK. When the SDK is avaiable, see rhinoSdkUtilities.h for details.

Also, I’ve added a Rhino.Geometry.Curve.ExtremeParameters function to RhinoCommon for Rhino 6, which basically calls the above SDK function.

– Dale

2 Likes
12

I’m curious to know if the implementation is very different to the above code.