TL;DR Check out a better answer here: Algorithm for deriving control points of a bezier curve from points along that curve?
First, use the excellent search function on stackoverflow to find all questions that are similar to your problem. Like this: https://stackoverflow.com/search?q=fit+points+to+bezier+curve
Now I didn't see that until I had written a great wall of text. So I'm gonna share it, with the caveat that ultimately, there may be a simpler (and tested) solution among the search results.
A quadratic Bezier curve is defined by four control points. The mathematical notation (from wikipedia) is:
B(t) = (1-t)^3*P0 + 3(1-t)^2*t*P1 + 3(1-t)*t^2*P2 + t^3*P3
The line is guaranteed to go through the end points P0 and P3, but not P1 and P2. The equation should hold for every pixel on the curve. Each pixel has an x
and a y
coordinate. Select a pixel you know is on the curve - that's B(t). This translates to two equations, one for each coordinate. The unknowns are t
, P1-x
, P1-y
, P2-x
and P2-y
since the control points have two coordinates each; a total of 5. If you only pick one point on the curve, you get 2 equations with 5 unknowns. But if we add a point, we get another t
and end up with 4 equations and 6 unknowns. Add 2 more to get 8 equations and 8 unknowns. Since it's a linear equation system it can be solved using Gauss elimination. Stack overflow has answered questions about Gauss elimination so I suggest you implement one of those solutions, this one for example: Logic error for Gauss elimination
There are a number of pitfalls you need to watch out for:
- Either use integers or floating-point numbers, consequently. Since the solution is going to be in integers (integer pixel values for the control points) it might be possible to use integers.
- Don't assume that the pixels fit exactly to the curve, they may be up to 0.5 pixels away in either direction. This affects the accuracy of the answer. You can either do research to make sure it's within acceptable limits for your purposes, or you can do the calculation multiple times with randomly chosen points and select the points that fit the best.
- If you do use a floating-point algorithm, beware of rounding errors. Floating-point 0.5 for example may not be stored exactly which could lead to
2*0.5 == 1
being false and other crazy stuff.
- Take care to select good points. Ideally you'd want the pixels you pick evenly spaced on the curve. Check if it makes a difference if the pixels are clumped together instead of spaced out.
Update: it's actually not a linear equation system so my approach won't work. Check out the answer linked at the top instead.