Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to figure out a generic way of determining a series of points on a Bézier curve where all the points are the same distance from their neighboring points. By distance I mean direct distance between the points not distance along the curve. See the image below

alt text

I've written a program that will solve this in an iterative fashion, but I'm wondering if there is a direct solution I could use.

My program starts by defining a circle of some initial radius (R) centered on the start point of the curve. It then intersects this circle with the curve to find the second point , which is R distance away from the start point). It then continues along the curve in this way finding points until it reaches the end of the curve. In most cases the distance between the last intersection point and the end point of the curve will not equal to R. The program then uses that difference to calculate a new value of R to try, and repeats the process.

share|improve this question
1  
Surely your routine will encounter an incommensurate Bézier (that is, given a particular Bézier curve and a distance, there will be a section of the curve that no longer has a point at the given distance). How would you want that handled? Otherwise, the use of crossing circles is indeed the most straightforward approach. –  J. M. Dec 30 '10 at 6:16
    
@J.M.: I guess that would fall under "reaching the end of the curve". –  Rahul Dec 30 '10 at 7:00
    
After re-reading (prompted by @Rahul's comment)... so you're actually looking for the distance for the Bézier to be commensurate? –  J. M. Dec 30 '10 at 7:05
    
Yes for a given bezier curve I'm looking for the distance that would hit the end of the curve. Or in other words I want to find the X number of points on the curve that include the start point and end point and where all the points are the same direct distance from their neighbors. –  Eric Anastas Dec 30 '10 at 20:27
1  
This is an interesting question. I'm curious what prompted it. –  I. J. Kennedy Feb 5 '11 at 20:29
show 1 more comment

1 Answer

up vote 1 down vote accepted

So you want the algorithm to "evenly divide" some given Bézier curve into a sequence of n points, such that traveling along the Bézier curve you hit each point in the same order, and such that the direct Euclidean distance from each point to the next point (the chord distance, not the arc distance along the Bézier curve) is the same?

I suspect that you might converge on the desired points a little faster if you pick n "t" values along the curve, and nudge all of them on every iteration -- rather than trying to fix one and going on to the next, and then throwing them all away and starting over every time you pick a new R value.

Say, for example, you want to divide the curve up into n = 100 points. The first point is going to stay fixed at $t_0$=0 and the last point is going to stay fixed at $t_{100}$=1. I'd probably start out at equally spaced t values, $t_0=0; t_1=1/100; t_2=2/100; ...; t_{99}=99/100; t_{100} = 1.$

At each iteration, calculate the distances between neighboring points, then nudge 98 of the t values (being careful not to cross them) to make the distances more equal, sooner or later converging on practically equal distances.

Off the top of my head, I seem to recall 2 methods for nudging those intermediate t values. Let me call the easier-to-understand method "the Babylonian method", and the faster-converging method "the false-position method". (Is there a better name for these techniques?)

the Babylonian method

Nudge each point closer to halfway between its neighbors.

$d_{7,8}$ = distance( B($t_7$), B($t_8$) )

$r_8$ = (1/2) ( $d_{8,9} - d_{7,8}$ ) / ( $d_{7,8} + d_{8,9}$ )

Because distances are always positive, the ratio values $r$ are always in the range of -1/2 to +1/2 -- zero if $B(t_8)$ has equal distances from $B(t_7)$ and $B(t_9)$, -1/2 if $t_8$ needs to move "halfway" back to $t_7$, +1/2 if $t_8$ needs to be moved "halfway" to $t_9$.

If $r_8$ is positive, $newt_8 = t_8 + r_8(t_9 - t_8)$

If $r_8$ is negative, $newt_8 = t_8 + r_8(t_8 - t_7)$

the false position method

Each iteration, calculate the accumulated straight-lines distance from the start point to the current location of each point B($t_0$) ... B($t_{100}$).

Nudge each point closer to its "proper" fraction of the distance along that entire accumulated distance.

For example, say (after a few iterations) we find that the accumulated distance from the start point $B(t_0)$ to point $B(t_8)$ is $c_8$ = 6.9, while the accumulated distance to the next point $B(t_9)$ is $c_9$ = 11.5, and the accumulated straight-lines distance from the start to the end is $c_{100}$ = 101.4. We need to make $t_8$ larger and $t_9$ smaller.

Using the false position method to estimate new values for all 98 "t" values, we get

error8L = 8/100 - $c_8 / c_{100}$

error8R = $c_9 / c_{100}$ - 8/100

If error8R is zero, it may help to push t8 all the way to t9. If error8L and error8R are both positive and approximately equal, it may help to push t8 halfway to t9.

$r_8$ = error8L / ( error8R + error8L )

The r value is the proportion of the distance to travel from t8 to t9 -- zero if t8 doesn't need to change this iteration, +1 if t8 needs to be moved all the way to t9.

$newt_8$ = $t_8$ + $r_8$($t_9$ - $t_8$).

If the r value along the segment from the current point to the next point is negative, we need to re-calculate a positive r value along the segment from the previous point to the current point, as we do for $t_9$ in this example:

error9L = 9/100 - $c_8 / c_{100}$

error9R = $c_9 / c_{100}$ - 9/100

$r_9$ = error9R / ( error9R + error9L )

$newt_9$ = $t_9$ - $r_9$($t_9$ - $t_8$).

One way to ensure we never cross the points is to clip each r value (whether in the forward or backward direction) to some maximum value slightly less than 1/2.

In our example, we need to slide $t_8$ a fraction we estimate as $r_8$ = 0.26 of the way "forward" from $t_8$ to $t_9$, while we need to slide $t_9$ a fraction we estimate as $r_9$ = 0.51 (perhaps clipped to 0.499) of the way "backward" from $t_9$ to $t_8$.

Alas, I've pulled these progressive refinement methods out of some dim memories. Perhaps something to do with building sine/cosine tables in one-degree increments?

I hope some kind commenter will remind me of the actual name of these methods, if (as is likely) I've mis-remembered the name or some crucial detail.

share|improve this answer
    
Thanks a lot! That does make a lot more sense then what I was trying. –  Eric Anastas Feb 28 '13 at 20:43
    
that helped.. can you please tell the way to find the coordinates of these equidistant points in the curve?? –  Kenpachi Mar 1 '13 at 9:27
    
@Kenpachi: The Babylonian method gives you a bunch of "t" values. The x,y coordinates on the curve at any t is given by plugging that t value into the Bezier function B(t). For example, if we want the x coordinate at t=0.1 of a typical cubic Bezier curve with control points P0, P1, P2, P3, we calculate B_x(0.1) = (1-0.1)^3*P0_x + 3*(1-0.1)^2*(0.1)*P1_x + 3*(1-0.1)*(0.1)^2*P2_x + (0.1)^3*P3_x. –  David Cary Mar 2 '13 at 1:03
    
thanks David :D –  Kenpachi Mar 2 '13 at 12:43
    
@DavidCary since I have used 2 control points to draw the curve with a start point and end point, and i dont see the use of those 4 values to calculate the equidistant points, how shall i do it..ive posted ques .. pls help math.stackexchange.com/questions/321293/… –  Kenpachi Mar 5 '13 at 10:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.