9

I want to fit a bezier curve with known end points (p0 and p3) to noisy 2d data. This seems like an easier problem than traditional 4-point bezier curve fitting but still too hard for me to figure out.

Can someone point me to existing code or an algorithm to find the best values for the control points p1 and p2?

Bezier curve fitting

edit: The points that I'm trying to fit with a bezier curve comes from curves drawn with a mouse (imagine drawing something with a brush in Paint, there could be hundreds of recorded points in one long stroke). The anchor points p0 and p3 are created in advance but the control points p1 and p2 should be calculated so that the bezier fits the shape of the curve sketched out with the mouse.

filip
  • 589
  • 1
  • 7
  • 18

1 Answers1

4

I stumbled on a paper called "Approximation of data using cubic Bezier curve least square fitting" by "M.Khan" which describes an algorithm to calculate the exact thing I'm looking for.

Implementation in javascript was easy. It works quite good and is fast but the resulting bezier curves are not perfect. Could be a bug in my code but I suspect that better curves could be obtained by iteratively adjusting the matching points on the bezier curve to better fit the data bezier curve creation.

edit: It turns out you can use newton-raphson to optimize each individual t-value for the bezier curve. After doing that the curve fits great, atleast for curves with only few points that don't self intersect but I have to do some more testing. Newton step optimization of bezier t-values

filip
  • 589
  • 1
  • 7
  • 18
  • Why not just use a catmull-rom spline instead? Still a cubic polybezier, but *through* points, instead of "sort of around them". – Mike 'Pomax' Kamermans Feb 22 '17 at 21:11
  • The idea was to use this in a vector drawing software that relies on bezier curves so splines wouldn't work in this case. – filip Feb 23 '17 at 06:59
  • except they would in this case: Catmull Rom spines are equivalent to cubic poly-Bezier (each CR section is a hermite spline that can be represented either CR spline or as cubic Bezier curve, similar to how you can represent a Bezier either as maths function or as sequence of interpolations. Same thing, different, equivalent, representations), so once you have your CR-spline, converting its coordinates to those for a sequence of explicit cubic Beziers [is trivial](http://pomax.github.io/bezierinfo/#catmullconv) (scroll to the end of the section for just the conversion rules) – Mike 'Pomax' Kamermans Feb 23 '17 at 17:18
  • I wasn't aware of the relationship between catmull rom splines and bezier curves, thank you for bringing this to my attention! Unfortunately, the specifics of my application requires a single cubic bezier curve to be used, not a sequence of beziers. – filip Feb 24 '17 at 07:10
  • Is there any reason why you would believe a single Bezier can even fit your data? Because while arbitrary order Beziers might work, deciding on a single cubic Bezier and then trying to fit it to your data, rather than looking at your data and then deciding what curve to use for the fitting, is literally doing things backwards. A single cubic Beziers is almost never the right curve for this job. Your original post shows a data cluster, your second post shows "drawing". What are you **really** trying to do here? Please update your post with what your noisy 2D data represents and how you get it. – Mike 'Pomax' Kamermans Feb 25 '17 at 20:08
  • I updated my question and my own answer with some more information. – filip Feb 25 '17 at 21:47
  • That does not explain why you can only use a single Bezier curve. Curves drawn with a mouse (or a finger) can be trivially traced with poly-Beziers in any application that I can think of. So why the single curve constraint? – Mike 'Pomax' Kamermans Feb 25 '17 at 22:11
  • In my work as a UX designer I draw a lot of bezier curves. Correct placement of anchor points p0 and p3 is a hard learned skill which is crucial for good bezier curves. This is not true for control points p1 and p2 so I'm experimenting with replacing them with a mouse movement. – filip Feb 26 '17 at 09:00
  • mouse movement is reliable enough to not generate the data you showed in your post, though. Normal mouse movement gives you a pretty well connected virtually zero noise dataset that you can run something like [ramer-douglas-peucker](https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm) on to remove all the superfluouse coordinates, and then use the remaining points to reliably build a curve. – Mike 'Pomax' Kamermans Feb 26 '17 at 18:54
  • 2
    I just managed to run the first test and it works better than I expected. See http://imgur.com/ii5DUQu for quick test using click+mousemove. I will look into the point reduction algorithm to see if it helps. – filip Feb 26 '17 at 19:13
  • 1
    @filip I got a 404 when I tried viewing the "Approximation of data using cubic Bezier curve least square fitting" pdf you linked above. I was interested in reading more about it. Do you have an alternate link? – Tony Aug 09 '18 at 07:54
  • 2
    did some googling and found it here: http://freesourcecode.net/matlabprojects/68721/cubic-bezier-least-square-fitting-in-matlab. Click "Download source code" and you will find the pdf among some matlab files – filip Aug 09 '18 at 08:06
  • 1
    @filip Is there any chance you'd be willing to share your implementation from the imgur link? I'm trying to do something similar with an animation curve but am not having any luck translating the code from the matlabprojects link. Thanks for any help! – andyV Jul 03 '20 at 03:53
  • @andyV https://stackoverflow.com/questions/6299019/how-can-i-fit-a-b%C3%A9zier-curve-to-a-set-of-data – Vlad Apr 12 '21 at 13:29