Нахождение точек перегиба вдоль произвольной оси

Question

Я пытаюсь найти точки перегиба относительно заданной оси (зеленая линия) с помощью ряда (синих) точек, которые образуют путь.Как видно из диаграммы ниже, есть две точки перегиба (розовые линии) или места, где путь меняет направление относительно оси задачи.

Сложность в том, что направление оси может измениться, поэтому она должна работать в любом направлении.Моя первая попытка взять 2 последовательных точки вдоль пути, получить направление между ними, а затем сравнить его с направлением оси.

Пропуская несколько скучных шагов (например, запись предыдущих точек), псевдокод выглядит следующим образомэто:

foreach point cur_point in path:
    direction = prev_point - cur_point
    (normalize direction)
    relative_direction = dir_towards_axis - direction
    (normalize relative direction)
    if the sign of either x or y has changed between relative_direction and prev_relative_direction
        # we have found an inflection point

К сожалению, это не работает.Есть какие-нибудь указатели, где я иду не так?

Answer 1

Чтобы найти необходимые точки, вы можете обнаружить изменение знака перекрестное произведение между осью и текущим направлением кривой (тест на ориентацию / сдвиг).

 axis_direction = axis_end - axis_start = B - A
 ....
 direction = cur_point - prev_point
 cross =  cross_product(direction, axis_direction) = 
          direction.x * axis_direction.y - direction.y * axis_direction.x

Примечание: ЕслиВаша кривая непрерывна и аналитична, может существовать замкнутая формула

Answer 2

Посмотрите на https://pomax.github.io/bezierinfo/#aligning - идея состоит в том, чтобы выровнять базовую линию по оси x или y, переместив каждую точку на {-p1.x, -p1.y}, а затем вращая все координаты, которые определяют вашу кривую (при условии, что ваша кривая инвариантна к аффинным преобразованиям! ), так что ваша последняя координата лежит на оси (для которой вы используете функцию atan2, чтобы найти угол поворота, на который идут практически все языки программирования).

После выравнивания по оси вы можете выполнить любой анализ «по оси», который вам необходим.