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

Я хочу определить, когда точка (позиция мыши) включена или близка к кривой, определенной рядом контрольных точек B-Spline.

Информация, которую я буду иметь для B-Spline, - это список из n контрольных точек (в координатах x, y). Список контрольных точек может быть любой длины ( >= 4) и определять B-сплайн, состоящий из (n-1)/3 кубических кривых Безье. Кривые Безье все кубические. Я хочу установить параметр k (в пикселях) расстояния, определенного как "близкое" к кривой. Если позиция мыши находится в пределах k пикселей кривой, тогда мне нужно вернуть true, в противном случае false.

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

Я обнаружил, что следующие вопросы, похоже, дают некоторую помощь, но не отвечают на мой точный вопрос. В частности, первая ссылка, по-видимому, является решением только для 4 контрольных точек и не учитывает коэффициент близости, который я хочу определить.

Позиция точки относительно кривой Безье

Пересечение между кривой Безье и сегментом линии

EDIT: Пример кривой:

 e, 63.068, 127.26   
    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

Описание формата: "Каждому ребру присваивается атрибут pos, который состоит из списка местоположений 3n + 1. Это контрольные точки B-сплайна: точки p0, p1, p2, p3 являются первыми безье сплайн, p3, p4, p5, p6 - второй и т.д. Точки представлены двумя целыми числами, разделенными запятой, представляющими координаты X и Y места, указанного в точках (1/72 дюйма). атрибуту, списку контрольных точек может предшествовать начальная точка ps и/или конечная точка pe. Они имеют обычное позиционное представление с префиксом" s "или" e ", соответственно."

EDIT2: Дальнейшее объяснение точки "e" (и s, если присутствует).

В атрибуте pos списку контрольных точек может предшествовать старт точка ps и/или конечная точка pe. Они имеют обычное позиционное представление с префикс "s "или" e", соответственно. Начальная точка присутствует, если есть стрелка в точке p0. В этом случае стрелка находится от p0 до ps, где ps действительно находится на границе node s. Длина и направление стрелки задаются вектором (ps -p0). Если здесь не является стрелкой, p0 находится на границе node s. Точно так же точка pe обозначает стрелка на другом конце края, соединяющаяся с последней точкой сплайна.

Ответ 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).
другие подходы могут быть возможны и, возможно, менее дорогостоящими.

Привет,

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