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

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

10 голосов
/ 25 ноября 2010

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

Информация, которую я буду иметь для 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» соответственно. "

РЕДАКТИРОВАТЬ 2: Дальнейшее объяснение точки "е" (и s, если присутствует).

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

Ответы [ 3 ]

11 голосов
/ 25 ноября 2010

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

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

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

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

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

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

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

Что дает:

alt text

Теперь, чтобы найти минимальное расстояние до точки (скажем, {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 вместо функций mathematica.

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}]]

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

alt text

(*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}]

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

alt text

2 голосов
/ 25 ноября 2010

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

1 голос
/ 17 февраля 2011

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

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

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

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

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

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

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

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

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

С уважением,

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

...