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

Question

我需要生成一条包含 25 个线段的随机路径，该路径永远不会在 1000x1000 区域中的两个位置之间交叉。有什么好的算法可以做到这一点？

我最初的想法是使用空间划分方法生成一个随机多边形，然后删除一侧，从而产生良好的结果。

结果如下：

这种方法的缺点是起点总是相当接近终点（因为它们最初是通过线连接的）。

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

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

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 时间复杂度，但它应该能够生成各种路径。

就实现数据结构而言，双向链表似乎是直接的候选者。