Ближайшая точка на кубической кривой Безье к данной точке
У меня есть кривая Куба-Безье, определенная как A, B, C, D. Где A — начало, B и C — контрольные точки, а D — конец. Я понимаю, как найти позицию при любом значении t, где 0 <= т <= 1, и это понятие в целом, поскольку оно просто использует несколько вызовов функции линейной интерполяции, которые приводят к кривой. (Можно легко визуализировать здесь, в Википедии чуть ниже заголовка Кривые высшего порядка)
Сейчас я ищу, чтобы найти точку на кривой, которая ближе всего к некоторой точке в пространстве, П. Гугл привел меня к многочисленным дискуссиям, но ни один из них не заставляет нейроны в моем мозгу звучать «ооо! На самом деле, если честно, они все летают прямо над моей головой. Мои знания по математике должны быть немного более ограниченными, чем хотелось бы, и рушатся, когда упоминаются производные.
Вот некоторые из мест, куда Google привел меня:
stackoverflow.com (квадратичный)
stackoverflow.com (близко, но я этого не понимаю)
Среди прочего, включая реализацию в ActionScript, которую я не могу снова выкопать, я знаю, что нашел ее в ответе / комментарии где-то здесь …
У кого-нибудь есть знания и терпение, чтобы эта информация проникла в мой мозг? Я подумываю сделать «достаточно близкий» подход и использовать ближайшую точку на линии, и просто перебирать кривую очень маленькими шагами. Это будет медленно, и точность будет потеряна. В моей конкретной ситуации точность менее важна, чем скорость, однако я чувствую, что есть способ иметь и то, и другое …
Заранее спасибо.
Решение
Как говорит cmaster, это приводит к решению полинома пятой степени, чтобы найти минимум полинома шестой степени
Неважно, если это 2D или 3D. Функция минимизации — полином шестой степени
f(t)=0.5*dot(p(t)-X,p(t)-X) such that 0<=t<=1
где X — заданная точка, а p (t) полиномиальная кривая, и dot обозначает евклидово скалярное произведение.
Минимизация может быть достигнута путем нахождения всех корней производной
f'(t)=dot(p'(t), p(t)-X)
внутри интервала и сравнения значений функций корней и в конечных точках интервала.
Существуют также методы минимизации, в которых не используются производные, в основном предназначенные для функций, которые являются более сложными, чем полиномы. Смотрите, например, главу 5 в
Брент Р.П. (1973), Алгоритмы минимизации без производных, Энглвудские Утесы, Нью-Джерси: Прентис-Холл, ISBN 0-13-022335-2
(эта книга, тем не менее, содержит обширные разделы о производных и полиномах Тейлора). Метод или его основная идея также могут быть найдены в «Числовые рецепты» как «поиск золотого сечения».
Другие решения