random - 什么是生成随机路径的好算法？

Question

我需要生成一个包含 25 个段的随机路径，这些段永远不会在 1000x1000 区域中的两个位置之间交叉。什么是执行此操作的好算法？

我最初的想法是使用 space partitioning method 生成一个随机多边形，它产生了不错的结果。然后取下一侧。

结果如下所示:


这种方法的缺点是起点总是非常接近终点(因为它们最初是由一条线连接的)。

另一个缺点是因为它们是多边形，所以整体形状会产生某种形式或扭曲的圆形。有很多类型的路径永远不会生成，比如螺旋。

有人知道可以帮助我生成这些路径的算法吗？

Answer 1

这是一个想法(免责声明:在我的脑海里，没有经过测试、验证或任何东西......):

绘制随机坐标并“尝试”按照您绘制的顺序连接线 - 所以你有 P1(x1, y1) 然后是 P2(x2, y2) 并连接它们，然后是 P3(x3, y3) 并且只要没有交点被创建(你必须每次都测试)，你继续绘制和连接。最终，将生成一个交点 - 然后您尝试将最后一个点(Pn-1:在新创建的点之前)连接到形成相交线的两个点中较早的点(我们称这些点为 Pi 和 Pi+j。如果这是有效的(意思是，它不跨越任何其他线)你断开那条线(Pi+j 不再出现在 Pi 之后)，你将 Pi 与 Pn-1 连接并从 Pi+j 恢复(现在变成 Pn-1点顺序条款)。如果将 Pn-1 连接到 Pi 无效，您可以执行相同的操作，但使用新发现的交叉点。

最终，您将解决交叉点并连接到最新点 - Pn，您可以正常恢复。

这个算法的明显缺点是它具有非常危险的 Big-O 时间复杂度，但它应该能够生成各种路径。

在实现数据结构方面，双向链表似乎是一个直接的候选者。