Arc length parametrization example interpolation understanding

Processing Coding Questions
4

Where did you get the value of 80 for the number of points? I am not sure how 80 is relevant to this discussion…

Have a look at this simple demo. As you can see, float t = i / float(steps); defines a fraction of the length of the curve to draw the point at. Drawing points as incremental fractions along the curve guarantees the equidistant feature as advertised by the function (or at best, an approximation in a worse case scenario)

The algorithm above is based on this simple concept.

This would be my interpretation after reviewing this code:

Initially there is a table built where the curve’s length is calculated per index and stored assuming there are 100 segments. I see this as an implicit statement and it should be considered as hidden implementation. This is a way to build a model where one has a curve represented with 100 segments. I would guess 100 is a good number for most practical cases and if you try hard, you can find situations/conditions were 100 might not be enough to create an adequate model. The key point is that you have a model and you do the interpolation using this model instead of calculating infinitesimal segments on any curve. If we think about science, natural phenomena are represented by models and models are accepted only if they are valid within practical ranges.

The second part of this algorithm is described by the following lines:

  float fraction = (float) i / (howMany - 1);
  float wantedLength = fraction * curveLength;
  
  // move through the look up table until we find greater length
  while (wantedLength > arcLengths[arcLengthIndex] && arcLengthIndex < arcLengths.length) {
    arcLengthIndex++;
  }

This is tricky. What happens if you have less than 100, exactly 100 or more than 100 for npoints? Well, if you choose 100, I will assume that the calculation will be based on the actual calculated segments. If you choose npoints to be less than 100, then the interpolation is based on about these npoints. The algorithm above will choose the closest points that aligns to the right segments. Think this way: for given npoints, the algorithm will choose the best npoints out of 100 from the initial model to perform the calculation. This is not an issue because each point selected is not a coordinate but a length. The index arcLengthIndex will pick the length of the curve from the table built from the initial model.

Now, if you have npoints that is larger than 100, that should not be a problem. Let’s say you have npoints=200 meaning than there are two points that the function above will return the same arcLengthIndex. The third part of the code will do a mapping based on a fraction:

float mappedIndex = map(wantedLength, prevLength, nextLength, prevIndex, nextIndex);

As you see, wantedLength is a length based on npoints, which should be a value between prevLength, nextLength. The mappIndex will be a linear interpolation between prevIndex, nextIndex and proportional to the fraction of wantedLength within the range of [ prevLength, nextLength]. For example, if wantedLength is half way withing the range, then mappindex will return exactly the half value between prevIndex, nextIndex. Finally, mapIndex is normalized to a value between 0 and 1 using the following operation: float parameter = mappedIndex / SEGMENT_COUNT;. This is to say that mappedIndex is a value between 0 and 100 and you divide by 100 to get a value between 0 and 1.

The above explanation also applies when npoints is 100 or less than 100.

The final step invokes resultPoints[i] = pointAtParameter(parameter); to calculate the actual point as a coordinate.

I would like to add the following posts that are relevant (check the first one for sure):

I hope this helps.

Kf

2 Likes