8

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)

Peter O.
  • 32,158
  • 14
  • 82
  • 96
Brandon
  • 1,058
  • 1
  • 18
  • 42

2 Answers2

6

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;
Brandon
  • 1,058
  • 1
  • 18
  • 42
  • 4
    for anyone also reading the comments, the described method isn't actually mathematically sound, since distance along the curve increases linearly along the curve, whereas the `t` values increase polynomially. It's actually easier to construct a LUT by running through `t` values, and for each x/y pair found simply recording their distance in a `{t,x,y,d}` quadruple. Finding x/y for d is then a matter of running through the list (sorted on `d`) until d_n <= d <= d_n+1, and interpolating x and y for those two records. – Mike 'Pomax' Kamermans May 15 '14 at 22:47
  • You can get a very good bezier-curve estimation with 30-40 points using [De Casteljau's algorithm](http://antigrain.com/research/adaptive_bezier/#toc0003), which is very easy to understand and implement. 1000 points is **way** too much. – BlueRaja - Danny Pflughoeft Jun 03 '15 at 02:11
1

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.

Yona Appletree
  • 8,801
  • 6
  • 35
  • 52