| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Определение принадлежности точки к кривой Безье [D5, D6, D7, WinXP]
CyberStorm © (2004-04-19 07:28:00)Подскажите возможные алгоритмы определения принадлежности точки к кривой Безье или определение минимального расстояния от точки до кривой.
В настоящий момент использую аппроксимацию кривой до набора прямых с последующим расчетом расстояния от точки до прямых и выборкой минимального, может быть есть другой более быстродействующий способ без перебора аппроксимирующих отрезков?
MBo (2004-04-19 09:31:00) [1]>что будет быстрее
Не проверял. В Graphics Gems используется аппроксимационный способ, но мне больше нравится с уравнением.
CyberStorm (2004-04-19 09:24:00) [2]Хм :) попробую ваш вариант, хотя и не люблю уравнения высоких порядков :(
Правда только что нашел еще одно оптимизационное решение :) - после аппроксимации, проверять не все отрезки, а только те в описывающий прямоугольник которых попадает точка, при этом заведомо лишние отрезки отпадут автоматически...
MBo интересно, что будет быстрее - вариант с решением уравнений пятого порядка или отбрасывание заведомо ненужных отрезков?
MBo (2004-04-19 07:41:00) [3]Да, возможно без перебора, только придется решать уравнение 5-го порядка.
Выписываешь квадрат расстояния от точки до точки кривой с параметром t, берешь производную для нахождения минимума квадрата - здесь уравнение 5-й степени. Один реальный корень можно найти численными методами (он обязательно существует), делишь полином на (t минус корень), остается 4-я степень - такое можно аналитически решить.
Альтернатива - найти собственные значения характеристической матрицы.
Отдельно проверяешь концы кривых (t=0,t=1).
| |
