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

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

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

Answer 2

对点集进行三角剖分然后在边缘上行走是一种解决方案，可以避免基于多边形的行走所具有的“类圆形”路径的问题。

您可能不希望随机点集的点靠得太近，因为它可能导致路径看起来像是在某些点与自身相交。出于这个原因，使用类似泊松盘采样方法来生成点集是可取的——这种点集的三角剖分将提供一条随机路径，其长度或多或少相等，线段角度约为 60 ° 并且没有明显的交叉点。

算法

有了 Delaunay 三角剖分库，算法如下所示：

要初始化，

• 生成点集
• 三角点集
• 从三角剖分中选择一个随机顶点（lastVisitedVertex）

然后循环：

• 选择一条连接到最后访问的顶点的随机边，仅当连接到该边的其他顶点尚未被访问时（此边是下一段）
• 将我们刚刚来自的顶点标记为已访问
• lastVisitedVertex= 选定边的另一个顶点
• 再次循环，或者如果路径长度超过我们想要的长度（即> 25）则退出

插图

三角泊松圆盘点集上的随机路径

[

三角化随机点集上的随机路径

代码

这是一个使用Tinfour库进行三角测量的 Java 示例。在使用三角剖分库时，我建议您选择一个可以轻松访问给定顶点的连接边以及构成给定边的顶点的库。

在这个例子中，我选择一个随机边（而不是顶点）作为起点。

ArrayList<Vertex> randomPath(List<Vertex> randomPoints, int pathLength) {

    IncrementalTin tin = new IncrementalTin(10);

    tin.add(randomPoints, null); // insert point set; points are triangulated upon insertion

    HashSet<Vertex> visitedVertices = new HashSet<>();
    ArrayList<Vertex> pathVertices = new ArrayList<>();

    IQuadEdge lastEdge = tin.getStartingEdge(); // get random edge

    int n = 0;
    while (n <= pathLength) {

        List<IQuadEdge> list = new ArrayList<>();
        lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array
        IQuadEdge nextEdge;
        int attempts = 0;
        do {
            nextEdge = list.get(random.nextInt(list.size())); // randomly select connected edge
            if (attempts++ > list.size() * 4) {
                return pathVertices; // path ended prematurely (no possible edges to take)
            }
        } while (visitedVertices.contains(nextEdge.getB()) || nextEdge.getB() == null);

        lastEdge = nextEdge.getDual(); // A and B flip around, so A is next vertex
        pathVertices.add(lastEdge.getB()); // add the point we just came from to path
        visitedVertices.add(lastEdge.getB()); // add the point we just came from to visited vertices
        n++;
    }
    return pathVertices;
}