返回贝塞尔曲线上等弧长的点列表的函数
某个地方必须有人解决这个问题。我可以找到许多很棒的网站来解释这个问题以及如何解决它。虽然我确信它们写得很好并且对数学高手来说很有意义，但那不是我。虽然我可能以一种模糊的方式理解，但我不明白如何将数学转化为我可以使用的函数。
所以我恳求你，如果你有一个可以用任何语言（当然甚至是 fortran 或 6502 汇编器）执行此操作的函数 - 请帮助我。
- 更喜欢分析解决方案而不是迭代解决方案
编辑：旨在指定它是我正在尝试使用的三次贝塞尔曲线。
Someone somewhere has had to solve this problem. I can find many a great website explaining this problem and how to solve it. While I'm sure they are well written and make sense to math whizzes, that isn't me. And while I might understand in a vague sort of way, I do not understand how to turn that math into a function that I can use.
So I beg of you, if you have a function that can do this, in any language, (sure even fortran or heck 6502 assembler) - please help me out.
- prefer an analytical to iterative solution
EDIT: Meant to specify that its a cubic bezier I'm trying to work with.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您要求的是弧长函数的反函数。因此，给定曲线 B，您需要一个在 0 和 1 之间返回的函数 Linv(len)，使得 0 和 t 之间的曲线的弧长为 len。
如果你有这个功能，你的问题就很容易解决了。设 B(0) 为第一个点。要找到下一个点，您只需计算 B(Linv(w))，其中 w 是您引用的“等弧长”。要得到下一点，只需评估 B(Linv(2*w)) 等等，直到 Linv(n*w) 变得大于 1。
我最近不得不处理这个问题。我想出了或遇到了一些解决方案，但没有一个令我满意（但也许它们适合您）。
现在，这有点复杂，所以让我先给你源代码的链接：
http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/raw_files/new/src/share/classes/sun/java2d/pisces/Dasher.java。您想要的是 LengthIterator 类。您不必查看文件的任何其他部分。在另一个文件中定义了许多方法。要找到它们，只需剪掉从 /raw_files/ 到 URL 末尾的所有内容。这就是你如何使用它。初始化曲线上的对象。然后，要获取从曲线开头开始弧长为 L 的点的参数，只需调用 next(L) （要获取实际点，只需使用 deCasteljau 的算法或 zneak 的建议在此参数处评估曲线）。与上次位置相比，每次后续调用 next(x) 都会使您沿着曲线移动 x 的距离。当你用完曲线时，next 返回负数。
代码说明：因此，我需要使 B(0) 到 B(t) 具有长度 LEN 的值（其中 LEN 已知）。我只是简单地拉平了曲线。因此，只需递归地细分曲线，直到每条曲线足够接近一条线（您可以通过比较控制多边形的长度与连接端点的线的长度来测试这一点）。您可以将此子曲线的长度计算为 (controlPolyLength + endPointsSegmentLen)/2。将所有这些长度添加到累加器中，并在累加器值 >= LEN 时停止递归。现在，调用最后一个子曲线 C 并令 [t0, t1] 为其定义域。你知道你想要的 t 是 t0 <= t < t1，并且您知道从 B(0) 到 B(t0) 的长度 - 将此值称为 L0t0。因此，现在您需要找到 C(0) 到 C(t) 的长度为 LEN-L0t0 的点。这正是我们开始时遇到的问题，但规模较小。我们可以使用递归，但这会非常慢，所以我们只使用 C 是一条非常平坦的曲线这一事实。我们假设 C 是一条线，并使用 P=C(0)+((LEN-L0t0)/length(C))*(C(1)-C(0)) 计算 t 处的点。该点实际上并不位于曲线上，因为它位于直线 C(0)->C(1) 上，但它非常接近我们想要的点。因此，我们只需求解 Bx(t)=Px 和 By(t)=Py。这只是求三次根，有闭源解，但我只是用了牛顿法。现在我们有了想要的 t，我们可以计算 C(t)，这就是实际的点。
我应该提到，几个月前，我浏览了一篇论文，其中有另一种解决方案，找到了曲线自然参数化的近似值。作者在这里发布了一个链接：贝塞尔曲线上的等距点
What you're asking for is the inverse of the arc length function. So, given a curve B, you want a function Linv(len) that returns a t between 0 and 1 such that the arc length of the curve between 0 and t is len.
If you had this function your problem is really easy to solve. Let B(0) be the first point. To find the next point, you'd simply compute B(Linv(w)) where w is the "equal arclength" that you refer to. To get the next point, just evaluate B(Linv(2*w)) and so on, until Linv(n*w) becomes greater than 1.
I've had to deal with this problem recently. I've come up with, or come across a few solutions, none of which are satisfactory to me (but maybe they will be for you).
Now, this is a bit complicated, so let me just give you the link to the source code first:
http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/raw_files/new/src/share/classes/sun/java2d/pisces/Dasher.java. What you want is in the LengthIterator class. You shouldn't have to look at any other parts of the file. There are a bunch of methods that are defined in another file. To get to them just cut out everything from /raw_files/ to the end of the URL. This is how you use it. Initialize the object on a curve. Then to get the parameter of a point with arc length L from the beginning of the curve just call next(L) (to get the actual point just evaluate your curve at this parameter, using deCasteljau's algorithm, or zneak's suggestion). Every subsequent call of next(x) moves you a distance of x along the curve compared to your last position. next returns a negative number when you run out of curve.
Explanation of code: so, I needed a t value such that B(0) to B(t) would have length LEN (where LEN is known). I simply flattened the curve. So, just subdivide the curve recursively until each curve is close enough to a line (you can test for this by comparing the length of the control polygon to the length of the line joining the end points). You can compute the length of this sub-curve as (controlPolyLength + endPointsSegmentLen)/2. Add all these lengths to an accumulator, and stop the recursion when the accumulator value is >= LEN. Now, call the last subcurve C and let [t0, t1] be its domain. You know that the t you want is t0 <= t < t1, and you know the length from B(0) to B(t0) - call this value L0t0. So, now you need to find a t such that C(0) to C(t) has length LEN-L0t0. This is exactly the problem we started with, but on a smaller scale. We could use recursion, but that would be horribly slow, so instead we just use the fact that C is a very flat curve. We pretend C is a line, and compute the point at t using P=C(0)+((LEN-L0t0)/length(C))*(C(1)-C(0)). This point doesn't actually lie on the curve because it is on the line C(0)->C(1), but it's very close to the point we want. So, we just solve Bx(t)=Px and By(t)=Py. This is just finding cubic roots, which has a closed source solution, but I just used Newton's method. Now we have the t we want, and we can just compute C(t), which is the actual point.
I should mention that a few months ago I skimmed through a paper that had another solution to this that found an approximation to the natural parameterization of the curve. The author has posted a link to it here: Equidistant points across Bezier curves