Какой алгоритм определяет близость точки к кривой Безье?

Ответ 1

Вы можете сделать это аналитически, но нужна небольшая математика.

Кривая Безье может быть выражена в терминах Mathematica, который обеспечивает хорошую поддержку вовлеченной математики.

Итак, если у вас есть точки:

pts = {{0, -1}, {1, 1}, {2, -1}, {3, 1}};  

. для кривой Безье:

f[t_] := Sum[pts[[i + 1]] BernsteinBasis[3, i, t], {i, 0, 3}];

Имейте в виду, что я использую базу Бернштейна для удобства, но ЛЮБОЕ параметрическое представление кривой Безье будет делать.

Что дает:

Теперь, чтобы найти минимальное расстояние до точки (например, {3, -1}, например), вы должны свести к минимуму функцию:

d[t_] := Norm[{3, -1} - f[t]];  

Для этого вам нужен алгоритм минимизации. У меня есть один удобный, так:

NMinimize[{d[t], 0 <= t <= 1}, t]  

дает:

 {1.3475, {t -> 0.771653}}  

И это все.

НТН!

Изменить Что касается вашего редактирования "B-сплайн с состоянием из (n-1)/3 кубических кривых Безье".

Если вы построили кусочное представление B-сплайна, вы должны перебирать все сегменты, чтобы найти минимумы. Если вы присоединились к частям непрерывного параметра, то этот же подход будет делать.

Изменить

Решение вашей кривой. Я игнорирую первый пункт, потому что я действительно не понимал, что это такое.

Я решил использовать его с помощью стандартных Bsplines вместо функций математики для ясности.

Clear["Global`*"];
(*first define the points *)
pts = {{
        29.124, 284.61}, {
        25.066, 258.56}, {
        20.926, 212.47}, {
        34, 176}, {
        38.706, 162.87}, {
        46.556, 149.82}, {
        54.393, 138.78}};

(*define a bspline template function *)

b[t_, p0_, p1_, p2_, p3_] :=
                  (1-t)^3 p0 + 3 (1-t)^2 t p1 + 3 (1-t) t^2 p2 + t^3 p3;

(* define two bsplines *)
b1[t_] := b[t, pts[[1]], pts[[2]], pts[[3]], pts[[4]]];
b2[t_] := b[t, pts[[4]], pts[[5]], pts[[6]], pts[[7]]];

(* Lets see the curve *)

Show[Graphics[{Red, Point[pts], Green, Line[pts]}, Axes -> True], 
 ParametricPlot[BSplineFunction[pts][t], {t, 0, 1}]]

. (Поворот! Для экономии пространства экрана)

(*Now define the distance from any point u to a point in our Bezier*)
d[u_, t_] := If[(0 <= t <= 1), Norm[u - b1[t]], Norm[u - b2[t - 1]]];

(*Define a function that find the minimum distance from any point u \
to our curve*)
h[u_] := NMinimize[{d[u, t], 0.0001 <= t <= 1.9999}, t];

(*Lets test it ! *)
Plot3D[h[{x, y}][[1]], {x, 20, 55}, {y, 130, 300}]

Этот график является (минимальным) расстоянием от любой точки пространства до нашей кривой (конечно, значение по кривой равно нулю):

Ответ 2

Сначала выведите кривую в растровое изображение (черно-белое) с вашим любимым алгоритмом. Затем, когда вам нужно, определите ближайший пиксель к позиции мыши, используя информацию из этого вопроса. Вы можете изменить функцию поиска, чтобы она возвращала расстояние, поэтому вы можете легко сравнить ее с вашими требованиями. Этот метод дает вам расстояние с точностью до 1-2 пикселей, что будет, я думаю.

Ответ 3

Определение: расстояние от точки до сегмента линии = расстояние от исходной точки до ближайшей точки, все еще находящейся на сегменте.

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

• используйте deCasteljau algo и разделите свои кубики, пока не получите достаточно длинную цепочку линейных сегментов. Дополнительная информация Разрез кривой Безье
• рассмотрим минимум расстояний между вашей точкой и приведенными сегментами как расстояние от вашей точки до кривой. Повторите все кривые в вашем наборе.

Уточнение в точке 2: не вычисляйте фактическое расстояние, но квадрат его, получая минимальное квадратное расстояние, достаточно хорош - сохраняет sqrt-вызов/сегмент.

Усилия вычисления: эмпирически кубическая кривая в максимальной степени (т.е. ограничивающая коробка) 200-300 приводит к примерно 64 отрезкам линии при сглаженном максимальном допуске 0,5 (приблизительно достаточно для невооруженным глазом).

• Каждый шаг deCasteljau требует 12 разделов на 2 и 12 дополнений.
• Оценка плоскостности - 8 умножений + 4 дополнения (при использовании расстояния TaxiCab для оценки расстояния)
• для оценки расстояния между точками требуется максимум 12 умножений и 11 дополнений - но это будет редкий случай в контексте сглаживания Безье, я ожидал бы в среднем 6 умножений и 9 дополнений.

Итак, предполагая очень плохой случай (100 прямых сегментов/кубических), вы заканчиваете поиск своего расстояния со стоимостью около 2600 умножений + 2500 дополнений на каждую кубическую.

Отказ:

• не спрашивайте меня о демонстрации чисел в оценка вычислительных усилий выше, Я отвечу "Использовать исходный код" (примечание: реализация Java).
• другие подходы могут быть возможны и, возможно, менее дорогостоящими.

Привет,

Адриан Коломиччи