什么算法确定点到贝塞尔曲线的接近程度？

Question

我希望确定一个点(鼠标位置)何时在一个B样条控制点定义的曲线上或附近.

我将为B-Spline提供的信息是n个控制点的列表(在x,y坐标中).控制点列表可以是任意长度(> = 4)并定义由(n-1)/ 3立方贝塞尔曲线组成的B样条.贝塞尔曲线都是立方的.我希望设置一个参数k,(以像素为单位)定义为"接近"曲线的距离.如果鼠标位置在曲线的k个像素内,那么我需要返回true,否则返回false.

有没有一个算法可以提供这些信息.任何解决方案都不需要精确 - 我正在努力达到1像素(或坐标)的容差.

我发现以下问题似乎提供了一些帮助,但不回答我的确切问题.特别是第一个参考似乎仅是4个控制点的解决方案,并没有考虑我希望定义的接近因素.

点相对于贝塞尔曲线的位置

贝塞尔曲线与线段之间的交点

编辑:示例曲线:

 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是第一个Bezier样条,p3 ,p4,p5,p6是第二个等.点由逗号分隔的两个整数表示,表示以点(1/72英寸)指定的位置的X和Y坐标.在pos属性中,控制点列表可以在起始点ps和/或终点pe之前.它们分别具有通常的位置表示,带有"s"或"e"前缀."

EDIT2:对"e"点的进一步说明(如果存在,则为s).

在pos属性中,控制点列表可以在起点ps和/或终点pe之前.它们具有通常的位置表示,分别带有"s"或"e"前缀.如果在p0处有箭头,则存在起点.在这种情况下,箭头从p0到ps,其中ps实际上在节点的边界上.箭头的长度和方向由矢量(ps -p0)给出.如果没有箭头,则p0位于节点的边界上.类似地,点pe在边缘的另一端指定箭头,连接到最后一个样条点.

Answer 1

你可以在分析上做这个,但需要一点点数学.

Bezier曲线可以用Bernstein Basis表示.在这里,我将使用 Mathematica,它为所涉及的数学提供了很好的支持.

所以,如果你有积分:

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

eq.贝塞尔曲线是:

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!

编辑关于编辑"包含(n？1)/ 3立方贝塞尔曲线的B样条曲线."

如果构建了分段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}]]

.(旋转!用于节省屏幕空间)

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

该图是从空间中的任何点到曲线的(最小)距离(当然曲线上的值为零):