Cocoa：在两个点之间画“随机”线？

Question

在我的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]创建一个平滑的蜿蜒曲线。

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

最后，我希望能够调整线条蜿蜒的程度。如果我将变量设置为int numOfIntermediatePoints，并将其设置为1，则pt1和pt2之间会有一个平滑的曲线。如果我将numberOfIntermediatePoints设置为10，则线条中会有更多的运动。我不希望最后的中间点离最终点很远（留下了一大段线末端的变化）。

我研究了使用Perlin噪声，但似乎很难引导线条朝向其结束点。计算一个NSPoint项目数组（并可能是控制点数组，对于第二种情况），然后循环遍历它们以创建线条似乎是合理的方法。

这个问题的最佳解决方法是什么？

---

更新

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

---

另一个更新

我做了另一个更新--我尝试了Dijkstra算法，发现它对我想要实现的内容来说过于复杂。最终，我实现了一个简化版的算法，可以让我指定随机线的引导节点。在这张图片中，线的起点位于中左侧，终点位于中右侧，并且在(xMax * 0.33, 0)和(xMax * 0.66, yMax)处有引导节点。

---

最终更新

为了使其更加平滑，我添加了一个可选的松弛算法。现在性能不是很好，但对于我想要的用途并不重要。

- Clay

Answer 1

有几种方法可以考虑。

就代码而言，您可以从互联网上下载随机迷宫生成器和迷宫求解器，然后按照需要生成入口和出口点的迷宫并获取其解决方案。

在尝试中编写，您可以尝试使用递归方法 - 从起点到终点开始一条直线，然后对于每条直线：

- 想象将在中心点将线分成两部分并将其移动到某个地方；所以... - 找出线的法线 - 确定可以在线法线上移动想象中的中心切点的距离，使您的线不会与现有的线重叠（我认为最简单的方法是二进制搜索，而不是任何分析方法） - 如果两个极端太接近，那么返回 - 否则，在两个极端之间选择一个随机位置，打断线并进行递归

其他有趣的想法，您可以在起点和终点之间抛出大量随机点，计算Voronoi图，然后沿以下方式行走：(i)从起点到其边界的任何地方; (ii)沿着细胞边界按照到达终点边界的最短路径（例如，使用Dijkstra算法）;(iii) 到达终点。然后，您可以通过每个由(ii)添加的顶点链接并找到在当前选定的链接中消除潜在集合的情况下的最短路线，并重复几次以使路径更有趣。

大致相同的思想，将一堆随机障碍物放在两点之间并运行A *风格的路径查找器可能会产生一些有趣的结果。

- Tommy

---

太棒了 - 谢谢你的建议！我喜欢Voronoi的想法；明天我会试一试，看看效果如何。 - Clay

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

Dijkstra的算法有点过头了，所以我选择了一个简化的变体。我在问题中添加了一些细节，还附上了一张截图。 - Clay