javascript - Calculate evenly distributed points along a curve - Stack Overflow

admin管理员组

文章数量:1415476

I'm using this equation to calculate a series of points along a quadratic curve:

// Returns a point on a quadratic bezier curve with Robert Penner's optimization of the standard equation
result.x = sx + t * (2 * (1 - t) * (cx - sx) + t * (ex - sx));
result.y = sy + t * (2 * (1 - t) * (cy - sy) + t * (ey - sy));

Sadly the points are unevenly distributed, as you can see in the dashed-line rendering below. The points are denser in the middle of the curve, and are further spaced apart near the edges. How can I calculate a evenly distributed set of points along a quadratic bezier curve?

Please note that I'm using this for rendering a dashed line, so a slow solution in MATLAB or something will not do. I need a fast solution that will fit inside a renderer. This is not for research or a one-off calculation!

Edit: I'm not asking how to acplish the above. The above is MY RENDERING! I already know how to estimate the length of a bezier, calculate the number of points, etc, etc. What I need is a better bezier point interpolation algorithm since the one I have calculates points unevenly distributed along the curve!

I'm using this equation to calculate a series of points along a quadratic curve:

// Returns a point on a quadratic bezier curve with Robert Penner's optimization of the standard equation
result.x = sx + t * (2 * (1 - t) * (cx - sx) + t * (ex - sx));
result.y = sy + t * (2 * (1 - t) * (cy - sy) + t * (ey - sy));

Sadly the points are unevenly distributed, as you can see in the dashed-line rendering below. The points are denser in the middle of the curve, and are further spaced apart near the edges. How can I calculate a evenly distributed set of points along a quadratic bezier curve?

Please note that I'm using this for rendering a dashed line, so a slow solution in MATLAB or something will not do. I need a fast solution that will fit inside a renderer. This is not for research or a one-off calculation!

Edit: I'm not asking how to acplish the above. The above is MY RENDERING! I already know how to estimate the length of a bezier, calculate the number of points, etc, etc. What I need is a better bezier point interpolation algorithm since the one I have calculates points unevenly distributed along the curve!

• javascript
• geometry
• bezier
• curve

Share Improve this question Follow edited Apr 5, 2017 at 13:47 Robin Rodricks asked Apr 4, 2017 at 14:54 Robin RodricksRobin Rodricks 114k147147 gold badges414414 silver badges617617 bronze badges 2

• Similar to this (stackoverflow./questions/18244305/…) but I want something much simpler and code in JS. – Robin Rodricks Commented Apr 4, 2017 at 14:55
• github./MadLittleMods/svg-curve-lib , gamedev.stackexchange./questions/5373/… ....when looking for an answer for this look up even speed movement along a path, or something like that, thats how I usually find the answer – PAEz Commented Mar 9, 2018 at 6:36

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 4

You want to generate equidistant (by arc length) subdivision of quadratic Bezier curves.

So you need subdivision procedure and function for calculation of curve length.

Find length of the whole curve (L), estimate desired number of segments (N), then generate subdivision points, adjusting t parameters to get Bezier segments with length about L/N

Example: you find L=100 and want N=4 segments. Get t=1/2, subdivide curve by two parts and get length of the first part. If length > 50, diminish t and subdivide curve again. Repeat (use binary search) until length value bees near 50. Remember t value and do the same procedure to get segments with length=25 for the first and for the second halves of the curve.

This approach uses the THREE.js library, which is not in the OP's question, but may be useful if only to look at how they approach it:

  var curve = new THREE.QuadraticBezierCurve(
    new THREE.Vector2( -10, 0 ),
    new THREE.Vector2( 20, 15 ),
    new THREE.Vector2( 10, 0 )
);

  var points = curve.getSpacedPoints(numPoints);

I happened to explore this question for a project. I think the answer above by "MBo" is mostly right, though putationally expensive

The parameter t based approach is easier to pute but would not yield even distances. If the curve has a sharp turn there the points will be more dense (e.g. the curve C in the picture).

Point to be noted that the parameter t which runs from 0 to 1, is not the fraction of length covered. In fact it is expensive to pute a point on curve from a given fraction of length, because there is no closed formula. So it'll be iterative approximation.

However given a t value you can split the original curve into two, and calculate their lengths. So the solution is to repeatedly split by t, calculate length and adjust t until t reaches the target fraction f of length.

You can write the approximation method and call it for every f from 0, 0.01, 0.02 and so on for 100 uniformly spaced points. But I think the runtime would be too high.

This is what I ended up doing in my case. It is an approximate solution, but efficient. Recursively split a curve at t = 0.5, then split left and right halves. Until each segment length is less than say 5 (pixel). When the segments are shorter than 5 pixels, it is fair to assume they are straight line segments.

Now you can interpolate for every fraction of length say f (not to confuse with t). Because every split point has an f value (length upto that point divided by total length). Suppose a query fraction f falls between two f values f1 and f2 of two consecutive split points.

f1 => (x1, y1) // known

f' => ??

f2 => (x2, y2) // known

where f1 <= f <= f2

Apply simple linear interpolation to find the coordinate at f. It's an O(1) operation. You can write a loop to emit points at a fixed intervals of f values by scanning the split points.

---

P.S. I checked THREE.js source on github. The method curve.getSpacedPoints uses uniform t-values. So it's not really "uniformly" spaced.

本文标签： javascriptCalculate evenly distributed points along a curveStack Overflow