[Code challenge] Point at euclidian length

[RIL (Rolf)]

Hi @gankeyu,
I may have misunderstood the challange, but I find that your chord changes in length at different positions along the curve.

To demonstrate the diff along the curve I added a second segment (with the same length param) to run ahead of the t+L curve at a length(L) distance, and especially in corners it’s quite visible what I mean:

GanKeyu_CurveChordDistance.gh (15.5 KB)

Shouldn’t the length of the line segment stay constant at all time?

// Rolf

[gankeyu (Keyu Gan)]

It shouldn’t change. Although I cannot see the component, the division doesn’t need to be 1000.

The Start is curve’s parameter while Length is length, so I’m not quite sure what you want to do by adding them.

I suppose the challenge is about rapidly finding the intersection of a circle (R=L, centered at P) and the curve.

[RIL (Rolf)]

@gankeyu

The Start is curve’s parameter while Length is length, so I’m not quite sure what you want to do by adding them.

I just made an extra line to run simultaneously for comparison. Remove that, it’s irrelevant except for the comparison.

But then the problem must be that I checked the “Parametrize” on the C input on the Eval component or something…

Edit: It also hangs my Rhino every now and then. It has happened three times I had to kill Rhino.

// Rolf

[RIL (Rolf)]

Anyway, here’s my redneck algorithm, which is much less sophisticated than @gankeyu 's ditto, and much slower, but it seems to work. Edit: Quits with error message if exceeding the end of the base curve.

CurveChordDistance_SpeedTest.ghx (269.9 KB)

// Rolf

[Dani_Abalde]

@gankeyu

The algorithm is a binary search that automatically extracts monotone intervals from a curve.

Boom! I was going in the same direction, approaching it in a simple (but hard to implement) binary search, but you shot at the target!

Thanks, well done!

I converted it to a C# component here, to keep us in an faster arena (is faster to make a script in GH than to compile a plugin):
PointAtEuclidianLength-CodeChallenge.gh (23.2 KB)

The EstimateParameterTolerance() function I don’t quite understand it. I get that it serves to stop searching if the search domain is below that threshold, but I don’t know why that formula.

Do you have any idea how to automate the bias to speed up the search? No need, just out of curiosity.

I don't know if I'll ever use it, I want to explore some things, but do I have your permission to include the following function in the Peacock library that will be my Github someday?

public static double ParameterAtEuclidianLength(Curve curve, double position, double length, double tolerance = 1e-12)
{
// Created by Keyu Gan (@gankeyu)  13 Jun 2020
// https://discourse.mcneel.com/t/code-challenge-point-at-euclidian-length/104008/22
// reshaped by @Dani_Abalde

var bias = 0.5;
var msLimit = 60000;

var squareDist = length * length;
var lowerBound = position;
var upperBound = curve.Domain.T1;
var origin = curve.PointAt(position);
var sw = new System.Diagnostics.Stopwatch();
sw.Start();

var middleGround = (upperBound - lowerBound) * bias + lowerBound;
var delta = (curve.PointAt(middleGround) - origin).SquareLength - squareDist;

while(true)
{
  var groundLength = upperBound - lowerBound;
  if (!RhinoMath.IsValidDouble(groundLength) || groundLength < 1e-16 || sw.ElapsedMilliseconds > msLimit)
    break; 
  
  middleGround = groundLength * bias + lowerBound;
  delta = (curve.PointAt(middleGround) - origin).SquareLength - squareDist;

  if (delta > tolerance)
    upperBound = middleGround;
  else if (delta < -tolerance)
    lowerBound = middleGround;
  else
    break;  
}

sw.Stop();

return middleGround;
}

EDIT: The function above doesn't work as the original one (blue point), this one fails at these cases (green point):

It can be fixed with a low bias, but but this is detrimental to performance.

[gankeyu (Keyu Gan)]

I split the curve at discontinuities as the entire curve may not be monotonic. The Subdivision input is for each segment instead of the entire curve which is why the default value is only 1.

[gankeyu (Keyu Gan)]

@Dani_Abalde

do I have your permission to include the following function in the Peacock library that will be my Github someday?

No problem, as long as it’s accredited.