相关疑难解决方法(0)

我正在寻找什么

我在飞机上有300或更少相等半径的圆盘.在时间0,每个盘都在一个位置.在时间1,每个盘处于可能不同的位置.我希望为每个光盘生成一个介于0和1之间的2D路径,这样光盘就不会相交,路径相对有效(短),如果可能的话,曲率也很低.(例如,直线比波浪线更好)

• 较低的计算时间通常比解决方案的准确性更重要.(例如,一个小交叉点是可以的,我不一定需要一个最佳结果)
• 但是,光盘不应相互传送,突然停止或减速,或突然改变方向 - "越平滑"越好.唯一的例外是时间0和1.
• 路径可以采样形式或分段线性(或更好)表示 - 我并不担心通过样条线获得真正平滑的路径.(如果我需要,我可以估算一下.)

我试过的

你可以看到我最好的尝试演示(通过Javascript + WebGL).请注意,由于涉及的计算,它将在旧计算机上缓慢加载.它似乎适用于Windows下的Firefox/Chrome/IE11.

在这个演示中,我将每个光盘表示为3D中的"弹性带"(也就是说,每个光盘每次都有一个位置)并运行一个简单的游戏式物理引擎来解决约束并将每个时间点视为一个上一次/下次弹簧的质量.(在这种情况下,'时间'只是第三个维度.)

这实际上适用于小N(<20),但在常见的测试用例中(例如,从以圆圈排列的光盘开始,将每个光盘移动到圆圈上的相反点),这无法生成令人信服的路径,因为约束和弹性在整个弹簧中缓慢传播.(例如,如果我将时间切割成100个离散级别,弹性带中的张力仅在每个模拟周期中传播一个级别)这使得良好的解决方案需要许多(> 10000)次迭代,这对于我的应用来说是非常慢的.它也无法合理地解决许多N> 40个案例,但这可能仅仅是因为我无法运行足够的迭代.

还有什么我试过的

我最初的尝试是一个爬山者,从直线路径开始,逐渐变异.比目前最佳解决方案更好的测量解决方案取代了目前最好的解决方案 交叉量(即完全重叠测量比仅仅放牧更糟糕)和路径长度(较短路径更好)导致更好的测量结果.

这产生了一些令人惊讶的好结果,但不可靠的是,很可能经常陷入局部极小.N> 20时速度极慢.我尝试应用一些技术(模拟退火,遗传算法方法等)试图绕过局部最小问题,但我从来没有取得太大成功.

我在想什么

我正在优化"弹性带"模型,以便张力和约束在时间维度上传播得更快.在许多情况下,这将节省大量所需的迭代,但是在高度受限的情况下(例如,许多光盘试图穿过相同的位置)仍然需要无法维持的迭代量.我不是如何解决约束或更快地传播弹簧的专家(我已经尝试阅读一些关于非拉伸布料模拟的论文,但我还没弄清楚它们是否适用),所以我会感兴趣,如果有一个很好的方法来解决这个问题.

桌上的想法

• Spektre实施了一种非常快速的RTS风格的单位运动算法,效果非常好.它快速而优雅,但是它受到RTS运动风格问题的影响:突然改变方向,单位可以突然停止以解决碰撞.此外,单位并非全部同时到达目的地,这实际上是一个突然停止.这可能是一个很好的启发式方法,可以制作可行的非平滑路径,之后可以及时重新采样路径,并且可以运行"平滑"算法(非常类似于我的演示中使用的算法).
• Ashkan Kzme建议问题可能与网络流量有关.看起来最小成本流问题可以起作用,只要空间和时间可以合理的方式进行,并且可以保持运行时间.这里的优点是它是一组研究得很好的问题,但突然的速度变化仍然是一个问题,并且可能需要某种"平滑"的后续步骤.我目前遇到的绊脚石是决定时空的网络表示,这不会导致光盘彼此传送.
• Jay Kominek发布了一个答案,该答案使用非线性优化器来优化二次贝塞尔曲线,并得到一些有希望的结果.

我有一组金属滑动件,它们以下列方式约束在x和y轴上:

我需要最大化由相同滑块约束的所有部件之间的水平距离以及滑动件和滑块本身之间的垂直距离.怎么解决这个问题？

任何能够解决这个问题的建议和建议都将不胜感激.

我首先看了一些非常强大的库,比如cassowary和jsLPSolver但是我在理解核心算法以及如何检查约束的可行性以及如何对可能的解决方案进行排序方面遇到了一些麻烦.

如何在JavaScript中实现一个(简单的)存根,用于二维几何约束求解器,解决上述问题？

编辑:

我有以下输入数据:

maxW = 300, maxH = 320

这些部分定义如下(不是强制性的,每个解决方案都被接受):

slidingPiece = [pX, pY, width, height, anchorPoint, loopDistance];

我将尝试解释"最大化"下的含义.

水平间距:

a0-b1,b1-b2,b2-b4,b4-b5和b5-maxX将是相同的,即max X除以最大垂直交叉片数+ 1(5).然后由可用的剩余空间确定b1-b3和b3-b5.

垂直间距:

b1-a3,a3-a4和a0-b5是相同的.理想地,a0-b3,b3-b4,a2-b2,b4-a3和b2-a4也将是相同的值.最大化a1-b4和b3-a2与最大化b3-b4相同.这同样适用于a2-b2和b4-a3:距离b2-b4将是最大负值.

因此,我需要最大化每个滑动件之间的距离以及他最近或低于Y约束的距离.

该问题的二维几何表示显示水平间距取决于锚的垂直距离(由于锚定件的垂直交叉),而这又取决于件本身的水平位置.比如说,b2比上面略短.在这种情况下,b1和b2不再相交,并且将成为相同的x值,即max X除以4.

在一些其他情况下,例如b2在上面的部分中要长得多 - 并且将穿过锚a2,然后它应该间隔为a1.这就是原因,因为会有一组解决方案,一些是可行的,另一些则不是,因为例如,全局最大Y约束将被打破.