Finding a point on a Bézier curve when given the distance from the start point?

Question

I created a 4 point Bézier curve, and a distance. Starting at the start point, how do I find the x,y coordinates of a point which is that distance away from the start point?

I've looked at the other examples, and from what I can tell, they approximate the values by dividing the curve into several thousand points, then finding the nearest point. This will not work for me. For what I'm doing, I'd like to be accurate to only two decimal places. Below is a simple form of what I have to create my Bézier curve. (The y values are arbitrary, the x values are always 352 pixels apart). If it matters, I'm working in Java.

path.moveTo(0, 400);
path.curveTo(352, 480, 704, 590, 1056, 550);

So assuming my start point is 0,400, how do I find the coordinates of a point that is 35 distance form that start point(along the curve)? (Ideally something not processor intensive. This may end up having to run 200 times per second)

Answer 1

For anyone that happens to find my question, I solved my own problem. To find the total distance of your curve, break it into 1000 or so pieces(still fairly accurate), find the distance between each point, then add them all together. (you should be using the parametric formula)

Now find the percent of the way along your curve. = distance/totalLengthOfCurve

Use this percent as your new t value for x and y, and now you have your new x and y positions.

IMPORTANT: This is an odd case, but make to to use the absolute value if your t value will ever be greater than 1. When you cube it, that value would be negative...=bad things happen.

Ugly, but relevant code shown below.

Breaking the curve into 1000 pieces

    for (double t = 0.00; t < 1.001; t= t + .001) {
         double xValue = Math.pow((1-t), 3) * point1x + 3 * Math.pow((1-t), 2) * t * point2x + 3 * (1-t) * Math.pow(t, 2) * point3x + Math.pow(t, 3) * point4x;
         double yValue = Math.pow((1-t), 3) * point1y + 3 * Math.pow((1-t), 2) * t * point2y + 3 * (1-t) * Math.pow(t, 2) * point3y + Math.pow(t, 3) * point4y;

**Now is when you calculate the distance between each point. Id suggest putting the above values calculated into an array and looping through.

Calculating the x and y positions

    xPos = Math.abs(Math.pow((1 - percenttraveled), 3)) * point1x + 3 * Math.pow((1 - percenttraveled), 2) * percenttraveled * point2x + 3 * Math.abs((1 - percenttraveled)) * Math.pow(percenttraveled, 2) * point3x + Math.abs(Math.pow(percenttraveled, 3)) * point4x;
    yPos = Math.abs(Math.pow((1 - percenttraveled), 3)) * point1y + 3 * Math.pow((1 - percenttraveled), 2) * percenttraveled * point2y + 3 * Math.abs((1 - percenttraveled)) * Math.pow(percenttraveled, 2) * point3y + Math.abs(Math.pow(percenttraveled, 3)) * point4y;

Answer 2

The javagraphics library has the MeasuredShape (https://javagraphics.java.net/doc/com/bric/geom/MeasuredShape.html) class which provides the getPoint method to do just this. It also has some very handy methods for getting subpaths and tangent angles. As far as I can tell, they are implementing the path logic "correctly," not resorting to breaking up the paths.

I have used this part of the library on a project that requires this sort of geometric calculation and it seems to be work perfectly.