2

Given a traced line or curve (say a mouse tracing app in which you can draw any uninterrupted line or curve), I would like to place points of equi-distance on that line or curve (the number of points placed can be varied). What's the best way to go about doing this?

Boon
  • 40,656
  • 60
  • 209
  • 315

1 Answers1

0

I recommend using a Centripetal Catmull-Rom spline.

http://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline

Catmull-rom curve with no cusps and no self-intersections

This lets you use the original "points" that the user either clicks or that you pick up during various mouse move events. You still need to add just two points on the end that control the initial and final directions of the line.

The reason to use Centripetal Catmull-Rom instead of the regular one is to avoid self-intersections and cusps, which are undesirable loops on the line itself.

The original Catmull-Rom parameterizes the distance along the curve as t. Since any segment of the curve uses the point preceeding the segment, and the point following the segment, the coordinate for any point between the middle two points can be interpolated by just passing a parameter t into the equation ranging from 0 to 1, with 0 equating to P1, and 1 being P2, where the four control points are P0, P1, P2, and P3.

The modified versions of the Catmull-Rom play with the positioning between the control points. It still uses the same 4 control points, and still takes in a t value that you can use to get your answer, but t no longer ranges from 0 to 1 extending between P1 and P2. Instead, the value you use for t will depend on the euclidean distances.

enter image description here

So, as an example of the Centriptal case, lets say I have 4 control points, and the segment distances are 4, 9 and 16. I will actually be using the square root of the distances, so the t values of the control points will be:

     UNIFORM                  CHORDAL               CENTRIPETAL                     
T0 = 0                          0                        0
T1 = 1                          4                   Sqrt(4) = 2
T2 = 2                          4 + 9 = 13          2 + Sqrt(9) = 5
T3 = 3                          13 + 16 = 29        5 + Sqrt(16) = 9

And then to interpolate between P1 and P2, I would pick a t value evenly spaced between T1 and T 2, which in the Centripetal case is 2 and 5.

enter image description here

Community
  • 1
  • 1
Ted
  • 3,212
  • 25
  • 20
  • This is time-parameterized, not distance-parameterized, though? – Oliver Charlesworth Feb 23 '14 at 17:24
  • In these splines, it takes the original spatial points, and would enable you to plot evenly spaced points between them along a smooth curve. The time is just a mechanism to represent progress along the spline. In the centripetal case the shape is controlled by incorporating the root of the Euclidean distances between control points, to figure out how much the spline should flex in response to local changes. It doesn't involve temporal time at all. – Ted Feb 23 '14 at 17:54
  • Will this algorithm work if there is loop in the traced curve? – Boon Feb 23 '14 at 19:02
  • Yes. As long as there are enough control points to define the loop shape, it will not prevent the natural spline from crossing itself. But in cases like a switchback, it prevents the spline from producing loops where the control data points themselves do not loop. – Ted Feb 23 '14 at 19:34