Точка на кривой Безье

[Ярослав Ned]

Как установить факт принадлежности точки кривой Безье 3 порядка ?

[нг]

переношу в Computer Science

[незваный гость]

Рискну ответить: по-разному.

(1) Математик предложит решить пару уравнений, задающих покоординатное равенство, и проверить, что пересечение множеств корней и интервала [0, 1] не пусто.

(2) Более изощрённый способ — написать результант полиномов $B_x(t) - x, B_y(t) -y$, проверить, равен ли он 0, а потом уж проверять на принадлежность к вышеупомянутому интервалу.

(3) Практик всяко пойдёт другим путём. Например, после соответствующего поворота, порядок одного из уравнений станет не выше второго. Вычисляем его корни (корень), проверяем на принадлежность интервалу, и проверяем подстановкой во второе уравнение.

(4) Реального практика и это не очень волнует. Ему нужен ответ на вопрос, лежит ли точка в пределах пары пелов (пикселов) от кривой Безье. Поскольку грызуном точнее не попасть. На этот вопрос проще всего ответить, заменяя к.Б. на ломаную с нужной точностью, и проверяя на расстояние от отрезков ломаной. С точки зрения практики, быть может, самый быстрый способ.

[Ярослав Ned]

Благодарю. Вариант (4) первое что приходило самому в голову, но откидывал его, как мне казалось, из-за большого количества вычеслений. Нельзя ли про пункты (1), (2), (3) написать подробнее.

[Алексей К.]

Если вопрос не включает особых требований к скорости, можно поискать и затем проверить экстремумы функции $DD(t)=(X(t) - x_0)^2+(Y(t) -y_0)^2$. Производная --- полином 5-го порядка. Решалку (рекурсивную, например) несложно нарисовать, а может она и и имеется уже.

Добавлено спустя 4 минуты 53 секунды:

Способ (3) от незваного гостя всё же наверное приятнее.

[незваный гость]

Ярослав Ned писал(а):

Вариант (4) первое что приходило самому в голову, но откидывал его, как мне казалось, из-за большого количества вычеслений.

У него есть неизбавимое достоинство: он позволяет проверить на принадлежность к окрестности к.Б. Что же касается объёма вычислений, то не так страшен чёрт, как его малюют. Если использовать деление к.Б. пополам (собственно, алгорифм Безье), то получается довольно шустро. По меньшей мере, результаты сравнения не очевидны.

(3) Рассмотрим $B_x(t)-x, B_y(t)-y$ как полиномы по $t$. Пусть их старшие коэффициенты $a_x, a_y$ соответственно. Если $(x, y)$ лежит на к.Б., то необходимо $t$ суть корень полинома $a_y(B_x(t)-x)-a_x(B_y(t)-y)$. Ну, а это уже не хуже, чем квадратный трёхчлен.

На самом деле, этот метод может быть не так уж и плох. Просто надо рассмотреть поворот координатной системы на $\arctg\frac{a_y}{a_x}$, и рассмотреть близость точки в этих координатах. Может, удастся довести до вполне приемлемого решения.

Что же касается (1) и (2), то это, скорее, шутка на тему того, как математики решают задачи (поскольку тема была первоначально в математике). Им ничего не стоит решить кубическое уравнение, или пересечь пару множеств. См. также результант.

[VLarin]

незваный гость писал(а):

У него есть неизбавимое достоинство: он позволяет проверить на принадлежность к окрестности к.Б. Что же касается объёма вычислений, то не так страшен чёрт, как его малюют. Если использовать деление к.Б. пополам (собственно, алгорифм Безье), то получается довольно шустро. По меньшей мере, результаты сравнения не очевидны.

Пару лет назад писал контрол для построения графиков.
Нужно было реализовать две вещи -
1. Выделение кривой (как раз проверка попадания в окрестность);
2. Динамическое определение данных по графику и отображение их на графике - а-ля "Курсор данных", для чего при перемещении мышки нужно было определять ближайшую точку кривой.

График может содержать десятки кривых, каждая может содержать тысячи точек, для сглаживания использовал сплайны 3-го порядка (в форме Безье). Таким образом, необходимо "на лету" вычисление расстояний для достаточно большого числа сплайнов.
И тоже думал, что решение в лоб не пройдет, но оказалось, что не тут то было:))

Воспользовался как-раз тем, что упомянул выше Алексей К.

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

А главное - что решать уравнение 5-го порядка с большой точностью и не требуется, особенно с учетом того, что все равно нужно проверить попадание (например, в 5-10 пиксельную) окрестность. Я задавал точность что-то типа 1е-3, решалось всего за несколько итераций.

[Ярослав Ned]

Всем спасибо за помощь.