贝塞尔曲线与线段之间的交点 [英] Intersection between bezier curve and a line segment

问题描述

我正在用Python编写游戏（用pygame），这要求我为每个新游戏生成随机但漂亮的海洋。经过漫长的搜索后，我决定使用一种算法，该算法涉及 padlib.py 。我现在需要确定padlib生成的曲线何时与线段相交。

蛮力方法是使用由padlib生成的一组近似线段找到答案。不过，我怀疑可以通过分析找到更好的答案。我只有几十个样条线段 - 搜索它们应该比数千条线段快。

一点搜索让我走上了这条路：Bezier Curve - > Kochanek-Bartels Spline - > Cubic Hermite spline

$ b 在最后一页，我找到了这个函数： （t）= h（t）p p b
$ b

（t）m 0 + h ₀₁ （ （t）

>

其中 p （t）实际上是一个点（2维向量），h （t）函数是三次多项式，p

/ b> ₀ 和 m ₁ 是我可以从padlib代码获得的点。

<现在，我可以e我的问题的解决方案是（t）= u + v * t ₁ b> u 和 v 是我的线段的结尾。

然而，制定解析解决方案已经超出了我的想象。有没有人知道现有的解决方案？或者可以帮助我解决方程式？

解决方案

作为一个粗略的轮廓，旋转和翻译系统，在X轴上。现在y坐标是参数t的三次函数。找到'零'（分析公式可以在好的数学文本或维基百科中找到）。现在评估对应于这些零点的x坐标，并根据您的线段进行测试。

I am writing a game in Python (with pygame) that requires me to generate random but nice-looking "sea" for each new game. After a long search I settled on an algorithm that involves Bezier curves as defined in padlib.py. I now need to figure out when the curves generated by padlib intersect a line segment.

The brute force method would be to just use the set of approximating line segments produced by padlib to find the answer. However, I suspect that a better answer can be found analytically. I only have a few dozen spline segments - searching them should be faster than thousand of line segments.

A little search took me down this road: Bezier Curve -> Kochanek-Bartels Spline -> Cubic Hermite spline

On the last page, I found this function:

p(t) = h₀₀(t)p₀ + h₁₀(t)m₀ + h₀₁(t)p₁ + h₁₁(t)m₁

where p(t) is a actually a point (2-dimensional vector), h_ij(t) functions are cubic polynomials, p₀, p₁, m₀ and m₁ are points I can get from padlib code.

Now, I can see that the solution to my problem is p(t) = u + v * t₁, where u and v are the end of my line segment.

However, working out the analytical solution is beyond me. Does anyone here know of an existing solution? Or can help me with solving the equations?

解决方案

As a rough outline, rotate and translate the system so that the line segment lies on the X axis. Now the y coordinate is a cubic function of the parameter t. Find the 'zeros' (the analytic formulae will be found in good math texts or wikipedia). Now evaluate the x coordinates corresponding to those zero points and test against your line segment.

这篇关于贝塞尔曲线与线段之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！