检测平行线中的"扭结"到贝塞尔曲线

Question

我希望有人可以帮我找出一种计算成本低廉的方法,用于检测平行于Bezier曲线绘制的线中的扭结,如此处所示

我想要做的是能够确定扭结的交叉点,该段与交叉点之前的起始点和具有扭结之后的结束点的第一个段.这样我就可以简单地删除任何不必要的段并调整第一段和最后一段以在交叉点处相遇.

如果我使用的是错误的条款,请道歉.但据我所知,我定位这些段的方式是通过确定贝塞尔曲线(黄色)的段的单位向量并将其乘以偏移量并找到法向量来创建两个新的起点和终点对于偏移段(白色).

数学不是我的强项,所以我希望有人可以给我一个正确的方向.

编辑:图像实际上已经被HTML调整大小,所以如果你很难看到我在说什么,这里是直接链接:http://i.stack.imgur.com/xtils.png

Answer 1

作为第一个近似值,计算曲率半径您的贝塞尔曲线.如果偏移量大于或等于曲率半径,则应查找扭结.

具体而言,对于具有控制点的三次贝塞尔曲线P0, P1, P2, P3:

B(t) = P0 * (1-t)^3 + P1 * 3*t*(1-t)^2 + P2 * 3*t^2*(1-t) + P3 * t^3
-> B'(t)  = (P1-P0) * 3*(1-t)^2 + (P2-P1) * 6*t*(1-t) + (P3-P2) * 3*t^2 
-> B''(t) = (P2+P0-2*P1) * 6*(1-t) + (P3+P1-2*P2) * 6*t

let:  cross2d(p, q) = p.x*q.y - p.y*q.x
then, radius of curvature = |B'(t)|^3 / cross2d(B'(t), B''(t))

我已经以符号形式留下了曲率半径; 标志应指示曲线的一侧,您可以预期扭结.

注意:您可以具有零曲率半径或无限曲率半径; 它可能是更好的比较|B'(t)|^3与signed_offset * cross2d(B'(t), B''(t))替代.