Определение принадлежности точки к кривой Безье

← →
CyberStorm (2004-04-19 07:28) [0]

Подскажите возможные алгоритмы определения принадлежности точки к кривой Безье или определение минимального расстояния от точки до кривой.
В настоящий момент использую аппроксимацию кривой до набора прямых с последующим расчетом расстояния от точки до прямых и выборкой минимального, может быть есть другой более быстродействующий способ без перебора аппроксимирующих отрезков?

← →
MBo © (2004-04-19 07:41) [1]

Да, возможно без перебора, только придется решать уравнение 5-го порядка.
Выписываешь квадрат расстояния от точки до точки кривой с параметром t, берешь производную для нахождения минимума квадрата - здесь уравнение 5-й степени. Один реальный корень можно найти численными методами (он обязательно существует), делишь полином на (t минус корень), остается 4-я степень - такое можно аналитически решить.
Альтернатива - найти собственные значения характеристической матрицы.

Отдельно проверяешь концы кривых (t=0,t=1).

← →
CyberStorm (2004-04-19 09:24) [2]

Хм :) попробую ваш вариант, хотя и не люблю уравнения высоких порядков :(

Правда только что нашел еще одно оптимизационное решение :) - после аппроксимации, проверять не все отрезки, а только те в описывающий прямоугольник которых попадает точка, при этом заведомо лишние отрезки отпадут автоматически...
MBo интересно, что будет быстрее - вариант с решением уравнений пятого порядка или отбрасывание заведомо ненужных отрезков?

>что будет быстрее
Не проверял. В Graphics Gems используется аппроксимационный способ, но мне больше нравится с уравнением.

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