3

在我的 Cocoa 爱好项目(在 OSX 上)中,我有一个确定了一些观点的观点。像这样的东西:

NSPoint pt1 = NSMakePoint(20,100);
NSPoint pt2 = NSMakePoint(100,30);

我想在这两点之间创建一条蜿蜒的线(永远不会交叉)。当然,要点可能会有所不同。我很熟悉,NSBezierPath但我不是图形高手。

对此有两种变体。给定NSBezierPath *p ...和设置[p moveToPoint:pt1]

  1. [p lineToPoint:ptx]在我创建锯齿状曲折线的地方使用
  2. [p curveToPoint:ptx controlPoint1:cpt1 controlPoint2:cpt2]与平滑的曲折线一起使用。

第二种情况似乎更困难,因为还必须计算合理的控制点。

最后,我希望能够调整线条蜿蜒的量。如果我将一个变量设置为 1,那么和int numOfIntermediatePoints之间会有一条平滑曲线。如果我设置为 10,则线路中的移动会更多。我不希望最后的中间点离终点很远(在行尾留下很大的变化)。pt1pt2numberOfIntermediatePoints

我已经研究过使用 Perlin 噪声,但似乎很难将线引导到终点。似乎计算一个NSPoint项目数组(可能还有一个控制点数组,对于情况二)然后循环它们以创建线是有意义的。

最好的方法是什么?


更新

按照 Tommy 的建议,我将Raymond Hill 的 Javascript-Voronoi库移植到了 Obj-C。你可以在这里找到它:https ://github.com/ccheaton/objcvoronoi


另一个更新

还有一个更新——我使用了 Dijkstra 的算法,发现它对于我想要实现的目标来说太过分了。我最终实现了它的简化变体,允许我为随机线指定引导节点。在这张图中,线的起点在左中,线的终点在右中,在 (xMax * 0.33, 0) 和 (xMax * 0.66, yMax) 处有引导点。

寻路示例


最终更新

为了让它稍微不那么锯齿,我添加了一个可选的松弛算法。现在性能不是很好,但这对我的使用无关紧要。

应用于小区站点的松弛算法

4

1 回答 1

3

有很多方法浮现在脑海中。

在代码方面,您可以直接从互联网上提取,您可以拉下一个随机迷宫生成器和一个迷宫求解器,然后根据需要生成一个带有入口和出口点的迷宫并获取解决方案。

在我进行的过程中,你可以尝试一种递归方法——从一条直线从头到尾开始,然后对于你拥有的每条直线:

  • 想象一下,您将通过在中心点将其分成两部分并将其移动到某处;所以...
    • 正常工作
    • 弄清楚在你的线与预先存在的线重叠之前你可以沿着法线移动想象的中心切割点多远(我认为最简单的方法是二进制搜索,而不是任何分析)
    • 如果两个极端靠得太近,则返回
    • 否则选择两个极端之间的随机位置,断线并递归

对于其他有趣的想法,您可以在起点和终点之间放置大量随机点,计算 Voronoi 图,然后 (i) 从起点步行到其边界上的任何位置;(ii) 根据到终点边界的最短路径沿着单元边界(例如,使用 Dijkstra 算法);然后 (iii) 到终点。然后,您可以遍历 (ii) 添加的每个顶点到顶点的链接,并找到从潜在集中消除所有当前选定链接的最短路径,并重复几次以使路径更有趣。

从大致相同的思想流派来看,在点之间扔一堆随机障碍物并运行 A* 式探路者可能会产生一些有趣的东西。

于 2012-03-09T21:43:24.147 回答