10

我希望确定一个点（鼠标位置）何时在由一系列 B 样条控制点定义的曲线上或附近。

我将获得的 B 样条信息是 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 是第一个贝塞尔样条，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 表示边缘另一端的箭头，连接到最后一个样条点。

4

3 回答 3

11

您可以通过分析来执行此操作，但需要进行一些数学运算。

贝塞尔曲线可以用伯恩斯坦基来表示。在这里，我将使用 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}}

就是这样。

！

编辑关于您的编辑“由 (n−1)/3 三次贝塞尔曲线组成的 B 样条曲线”。

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

该图是从空间中的任何点到我们的曲线的（最小）距离（当然曲线上的值为零）：

替代文字

于 2010-11-25T12:38:40.383 回答
2

首先，使用您喜欢的算法将曲线渲染为位图（黑白）。然后，当您需要时，使用此问题中的信息确定离鼠标位置最近的像素。您可以修改搜索功能，使其返回距离，以便您可以轻松地将其与您的要求进行比较。这种方法为您提供了 1-2 像素容差的距离，我猜这可以。

于 2010-11-25T09:58:28.957 回答
1

定义：点到线段的距离=原点到线段上最近点的距离。

假设：计算从点到线段的距离的算法是已知的（例如，计算与通过原始点的线段法线的线段的截距。如果交点在线段之外，则选择最近的端点段）

  1. 使用 deCasteljau 算法并细分您的立方，直到获得足够好的线性段菊花链。“贝塞尔曲线展平”部分的补充信息
  2. 将您的点和结果段之间的距离的最小值视为从您的点到曲线的距离。对集合中的所有曲线重复此操作。

第 2 点的细化：不计算实际距离，但它的平方，获得最小平方距离就足够了 - 节省了 sqrt 调用/段。

计算工作量：根据经验，最大范围（即边界框）为 200-300 的三次曲线在展平至最大容差 0.5 时产生大约 64 条线段（对于肉眼来说大约足够好）。

  1. 每个 deCasteljau 步骤需要 12 次除以 2 和 12 次加法。
  2. 平坦度评估 - 8 次乘法 + 4 次加法（如果使用出租车距离来评估距离）
  3. 点到段距离的评估最多需要 12 次乘法和 11 次加法 - 但在贝塞尔展平的情况下，这将是一种罕见的情况，我预计平均需要 6 次乘法和 9 次加法。

因此，假设一个非常糟糕的情况（100 个直线段/立方），您以大约 2600 次乘法 + 2500 次加法的成本计算距离。

免责声明：

  1. 不要要求我演示上面计算工作量评估中的数字，我会回答“使用源代码”（注意：Java 实现）。
  2. 其他方法可能也是可行的，而且成本可能更低。

问候，

阿德里安·科洛米奇

于 2011-02-17T07:10:48.333 回答