相关疑难解决方法(0)

我正在用Python创建一个游戏(带有pygame),这需要我为每个新游戏生成随机但漂亮的"海洋".经过长时间的搜索,我决定采用一种算法,该算法涉及padlib.py中定义的Bezier曲线.我现在需要弄清楚padlib生成的曲线何时与线段相交.

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

一点点搜索让我沿着这条路走:Bezier Curve - > Kochanek-Bartels Spline - > Cubic Hermite spline

在最后一页,我发现了这个功能:

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

其中p(t)实际上是一个点(二维向量),h _ij(t)函数是三次多项式,p ₀,p ₁,m ₀和m ₁是我可以从padlib代码得到的点.

现在,我可以看到我的问题的解决方案是p(t)= u + v*t ₁,其中u和v是我的线段的结尾.

然而,制定分析解决方案超出了我的范围.这里有人知道现有的解决方案吗？或者可以帮我解决方程式？

我有一个由4个点指定的贝塞尔曲线.我需要知道一个点是否位于贝塞尔曲线的左侧或右侧.你能给我一个算法吗？

编辑:我确信我生成贝塞尔曲线的方式不会形成循环.

后来编辑我意识到我的初始问题可以在不使用相对位置的情况下解决.当我发布这个问题时,我认为存在相对位置的数学公式,类似于检查点是否在圆的内部.看来这是不可能的.所以我会接受能够提出时间效率解决方案的答案.

我有一个随机的2D图像和稀疏的像素分散.
给定图像上的一个点,我需要找到距离背景颜色最近的像素的距离(黑色).
最快的方法是什么？

我能想出的唯一方法是为像素构建一个kd树.但我真的想避免这种昂贵的预处理.而且,似乎一棵kd树给了我超过我需要的东西.我只需要与某种东西的距离,我不关心这是什么东西.