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

Question

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

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

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

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

Position of a point relative to a Bezier curve

Intersection between bezier curve and a line segment

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 дюйма). В атрибуте pos списку контрольных точек может предшествовать начальная точка ps и/или конечная точка pe. Они имеют обычное представление позиции с «S», или «е» префикс, соответственно «

EDIT2: Дальнейшее объяснение„ е.“Точки (и с если она присутствует)

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

Answer 1

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

Кривая Безье может быть выражена через Bernstein Basis. Здесь я буду использовать 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}} 

И это его.

HTH!

Редактировать Относительно вашего редактирования «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}] 

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

Answer 2

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

Answer 3

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

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

1. использовать deCasteljau Algo и не подразделяет свои кубики до получения в достаточно хорошую гирлянду линейных сегментов. Supplementary info«Сглаживание кривой Безье» раздел
2. Рассматривайте минимальное расстояние между своей точкой и приведенными сегментами как расстояние от вашей точки до кривой. Повторите все кривые в вашем наборе.

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

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

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

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

Отказ от ответственности:

1. не просят меня для демонстрации чисел в оценка вычислительные затраты выше, Отвечу с "Use the source-code" (примечание: реализация Java).
2. Другие подходы могут быть возможны и, возможно, менее дорогостоящими.

С уважением,

Адриан Colomitchi