Divide curve fixed segments and optimized way

Hi everyone,

I’m working on a Grasshopper definition where I must divide a curve into segments based on a predefined list of lengths (240,80, 50, and 45). However, I want to minimize the number of divisions by selecting the largest possible segments first while ensuring that the entire curve is covered efficiently. the leftover part needs to be shown in a number. I would also like to get a list out of the grasshopper fill to see how many of each line type I have.
Can anybody help me?

that is not an easy problem :slight_smile:

it first looked like a coin-change problem, but -if I have understood correctly- your curve will become an array of straight segments with common ends, which means that the very same segment could cover a different amount of curve_length based on where it’s placed

anyways, these two sentences looks like opposite to each other to my ears :slight_smile:

you might want to introduce some other variables in play, like max_distance / max_angle to define what “efficiently” means?

supplying a curve or a sketch of what you are trying to achieve would for sure benefit the conversation :slight_smile:

on a side note, I sort of remember this topic was touched a couple of times at least in this forum, maybe also in 2024

Thanks for your reply! :blush:
Yeah, you’re right—it’s kind of like the coin change problem, but with the curve adding complexity. The way I see it now is like trying to make 55 euros using the fewest coins, so I’d go with 2x20, 1x10, and 1x5.
For the curve, it’s the same idea—covering 55 cm with segments like 20 cm, 10 cm, and 5 cm, using as few divisions as possible.

I get what you mean about the same segment covering different lengths depending on where it’s placed—that’s the tricky part. Also, I realize now that minimizing divisions and efficient coverage aren’t exactly the same thing.
What I’m Thinking Now:
Maybe I should focus on minimizing the number of segments (like using the fewest coins), rather than strictly prioritizing the largest segment lengths.

it is quite simple to do what you want, at each new point test the longest line and measure its distance to the curve, if max distance is more than tolerance take a shortest curve. When distance is just less than the tolerance or it is the last one take this line.
Just one thing it will be impossible to end exactly on the end of the curve !!
But it will be more simple to do it with python or C#

this is a dirty messy sketch of Laurent’s hint using Anemone for looping

it “features” a test for “max belly distance”, which is interesting but could also lead to division loop suddenly stopping in case max dist is not respected for any available length (it’s the way the loop tells you “I can’t complete the job with these constraints” )

max belly is measured like this (similarly to ToPoly distance tolerance):

so if the loop is trying to place a given length, and that max_distance does not satisfy your requirement, it will sub-loop to the next -smaller- available length

if you are not interested in max_distance check, just put a very high number as max_dist :slight_smile:

LoopDivide_curve_set_of_distances.gh (26.8 KB)

the main logic that drives the loop is, given a Curve:
it places a sphere of radius = biggest available length centered on curve start point, and checks if the sphere intersects with the curve exactly one time, it also checks the max dist from the above explanation: if both give positive result, then it trims out the portion of curve inside the sphere, and just repeats the whole process on the remaining piece of curve
if number of sphere|curve intersections is different than one, or max_dist is not respected, it tries again on same point but with second_biggest length… than 3rd, 4th… and so on
if it can’t find a Length that satisfies just one intersection point or max_dist, it just stops there midway

1 Like

Here a C# version

In your script @inno if tolerance is too low it doesn’t work. In my script I take the last distance.
And for the last curve I stop it at the end
LoopDivide_curve_set_of_distances_LD_Csharp.gh (7.3 KB)

private void RunScript(Curve curve, List<double> distances, double maxDistance, ref object A)
  {

    double param = 0;
    double paramOut = 0;
    double tolerance = 0.01;
    //Number of divisions in ordern to measure distance between curve and line
    double nDivisions = 10;

    //First parameter
    curve.NormalizedLengthParameter(0, out param);
    //Output lines
    List<Curve> lst_lines = new List<Curve>();
    bool isOk = true;
    int count = 0;
    do
    {
      isOk = false;
      //List of params for possible curves
      List<double> lst_params = new List<double>();
      double paramOutTest;
      foreach (double distance in distances)
      {
        if (GetFirstIntersection(curve, param, distance, tolerance, out  paramOutTest))
        {
          isOk = true;
          lst_params.Add(paramOutTest);
        }
      }
      //If no param we add a line that ends at the curve end
      if (lst_params.Count == 0)
      {
        curve.NormalizedLengthParameter(1, out paramOutTest);
        lst_params.Add(paramOutTest);
      }
      //We take the first line that is OK with maxDistance between line and curve
      for (int i = 0; i < lst_params.Count; i++)
      {
        double distance = MaxDistance(curve, param, lst_params[i], nDivisions);
        paramOut = lst_params[i];
        if (distance < maxDistance) break;
      }
      if (lst_params.Count > 0)
      {
        LineCurve line = new LineCurve(curve.PointAt(param), curve.PointAt(paramOut));
        if (line.GetLength() > tolerance)
        {
          lst_lines.Add(line);
        }
        else
        {
          isOk = false;
        }

        param = paramOut;
      }
      count++;
    }
    while (count < 10000 && isOk);

    A = lst_lines;
  }

  // <Custom additional code> 


  /// <summary>
  /// Calculate distance between points on curve and a line
  /// </summary>
  /// <param name="curve"></param>
  /// <param name="param1">first param on curve</param>
  /// <param name="param2">second param on curve</param>
  /// <param name="nDivsions">number of points (-1) to test</param>
  /// <returns></returns>
  public double MaxDistance(Curve curve, double param1, double param2, double nDivsions)
  {
    nDivsions = Math.Max(2, nDivsions);
    double maxDistance = 0;
    Point3d pt1 = curve.PointAt(param1);
    Point3d pt2 = curve.PointAt(param2);
    Curve line = new LineCurve(pt1, pt2);

    for (double d = 1.0 / nDivsions; d < 1.0; d += (1.0 / nDivsions))
    {
      double param = param1 + (param2 - param1) * d;
      double t;
      Point3d pt = curve.PointAt(param);
      if (line.ClosestPoint(pt, out t))
      {
        double dist = pt.DistanceTo(line.PointAt(t));
        if (dist > maxDistance) maxDistance = dist;
      }
    }
    return maxDistance;
  }

/// <summary>
/// 
/// </summary>
/// <param name="curve"></param>
/// <param name="param"></param>
/// <param name="distance"></param>
/// <param name="tolerance"></param>
/// <param name="paramOut"></param>
/// <returns></returns>
  public bool GetFirstIntersection(Curve curve, double param, double distance, double tolerance, out double paramOut)
  {
    bool output = false;
    paramOut = double.MaxValue;

    Brep sphere = Brep.CreateFromSphere(new Sphere(curve.PointAt(param), distance));

    Curve[] overlapCurves;
    Point3d[] intersectionPoints;
    double curveParameters;
    Rhino.Geometry.Intersect.Intersection.CurveBrep(curve, sphere, tolerance, out overlapCurves, out intersectionPoints);

    if (intersectionPoints != null && intersectionPoints.Length > 0)
    {
      foreach (Point3d pt in intersectionPoints)
      {
        double t;
        if (curve.ClosestPoint(pt, out t))
        {
          if (t > param && t < paramOut)
          {
            paramOut = t;
            output = true;
          }
        }
      }
    }
    return output;
  }
2 Likes

Tips

  1. Search “Knapsack” problem (the general 1D “packing” case).
  2. Learn C#
1 Like

Hi Laurent,

Thanks for sharing your C# version! It works well, but I’m trying to refine the segmentation logic.

Right now, my script sometimes results in less optimal divisions, where I might end up with an undesirable leftover segment (≥ 5 cm). Instead of following a fixed sequence, I’d like to find the most optimal way to distribute the segments dynamically, ensuring that:

  • The largest possible panels are used efficiently.
  • The remaining segment never exceeds or equals 5 cm.
  • The divisions are balanced and smartly optimized rather than arbitrary.

Do you have any suggestions on how to improve the logic to achieve this?

Hello
optimization is not always simple and you’ll have to answer some question like
Did you manage to do better by hand ?
If yes what did you do ?
What could be compromised ? Tolerance ?
What is “smartly optimized” in Math/programation language ?
What is balanced" in Math/programation language ?

If you can answer your own question you will make progress.

But somethings are impossible

Hi,

Thanks for your response! I understand that optimization isn’t always straightforward, so I’ve tried to clarify my approach by answering your questions.

Did you manage to do better by hand?

Yes, I have manually found better ways to divide the curve compared to what my script currently produces.
For example, when dividing 170 cm, my script sometimes gives:
90-70-5 (valid but not optimal)
Better by hand: 75-75-20 (fewer different segment sizes and a more structured distribution).

What did you do differently by hand?

  • Instead of greedily choosing the longest possible segment first, I looked ahead to see how the remaining length could be divided more efficiently.
  • I avoided creating an unwanted leftover (≥ 5 cm).
  • I preferred solutions with fewer different segment sizes to create a more structured and predictable pattern.

What could be compromised?

  • Tolerance? Yes, small deviations are acceptable, but ensuring that no leftover segment is ≥ 5 cm is a hard constraint.
  • Fewer cuts vs. fewer segment types? I prioritize a structured division with symmetrical or repetitive sequences over simply reducing the number of cuts.

What does “smartly optimized” mean in this case?

  • The segmentation should predict future divisions instead of making immediate, local decisions.
  • It should choose a sequence that minimizes the variety of segment sizes while maintaining efficiency.
  • The algorithm should be able to skip certain segment options if it results in a better overall distribution.

What does “balanced” mean in this case?

  • A segmentation is balanced if it avoids unnecessary variations in segment sizes and prefers symmetry (e.g., 75-75-20 over 90-70-5).
  • It should avoid clustering too many small segments at the end.

Final Question:

Would it be possible to generate 2 or 3 different segmentation options instead of just one? This way, I could compare different solutions and choose the most suitable one.