Нахождение точек перегиба множества точек

Question

Я работаю над тем, что может соответствовать набору кривых Безье через набор точек. Я смог сделать это, используя метод подбора кривой из Pomax . Проблема этого метода в том, что он не может соответствовать кривой Безье низкого порядка через линию, которая имеет много перегибов. Поэтому, чтобы выполнить эту работу, мне нужно иметь возможность получить кусочно-кубический c -безье, разделив кривую в ее точках перегиба, а затем запустив кривую, подходящую от go оттуда. Проблема в том, что я не уверен, как найти производную от набора точек, которые не имеют четкой функции. Я думаю, я всегда мог бы рассчитать наклон секущей линии вместо касательной, но я не уверен, что это будет работать хорошо. У кого-нибудь есть лучшие идеи о том, как найти точки перегиба множества точек?

Answer 1

Точка перегиба - это разделительная кривая, в которой обмотка кривизны идет от CW к CCW или наоборот. Поэтому сначала определите обмотку.

Предположим, что в 2D-случае ...

Если ваши точки равны { p0,p1,p2,...,p(n-1) }, то намотка на p(i) равна sign из z координата 3D cross произведение двух последовательных касательных:

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

Так что, если p(i) является инфлексом, то:

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

Проблема в том, если w(i) или w(i-1) равно нулю, такая обмотка должна быть пропущена или специально обработана.