Finding inflection points of a set of points

Question

I am working on something that can fit a set of Bezier curves through a set of points. I've been able to do this using the curve fitting method from Pomax. The problem with this method is that it cannot fit a low order Bezier curve through a line that has many inflections. Therefore in order to make this work, I need to be able to get a piecewise cubic-bezier by splitting the curve at its inflection points and then running the curve fitting algo from there. The problem is that I'm not sure how to find the derivative of a set of points that have no clear function. I guess I could always calculate the slope of the secant line instead of the tangent line, but I'm not sure if that would work well. Does anybody have any better ideas on how to find the inflection points of a set of points?

Answer 1

Inflex point is dividing curve where the curvature winding goes from CW to CCW or vice versa. So first detect the winding.

Assuming 2D case...

If your points are { p0,p1,p2,...,p(n-1) } then winding at p(i) is the sign of z coordinate of 3D cross product of 2 consequent tangents:

w(i)  = cross (
              ( p(i).x-p(i-1).x , p(i).y-p(i-1).y , 0)
              ( p(i+1).x-p(i).x , p(i+1).y-p(i).y , 0)
              ).z

So if p(i) is inflex then:

w(i)*w(i-1) < 0

The problem is if w(i) or w(i-1) is zero such winding must be skipped or specially handled.