Форум: "Media";
Текущий архив: 2004.07.04;
Скачать: [xml.tar.bz2];
ВнизОпределение принадлежности точки к кривой Безье Найти похожие ветки
← →
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 интересно, что будет быстрее - вариант с решением уравнений пятого порядка или отбрасывание заведомо ненужных отрезков?
← →
MBo © (2004-04-19 09:31) [3]>что будет быстрее
Не проверял. В Graphics Gems используется аппроксимационный способ, но мне больше нравится с уравнением.
Страницы: 1 вся ветка
Форум: "Media";
Текущий архив: 2004.07.04;
Скачать: [xml.tar.bz2];
Память: 0.45 MB
Время: 0.03 c