我需要生成一个包含 25 个段的随机路径,该路径永远不会在 1000x1000 区域中的两个位置之间交叉。什么是一个好的算法来做到这一点?
我最初的想法是使用空间分割方法生成一个随机多边形,然后删除一侧。
这种方法的缺点是起点总是非常接近终点(因为它们最初是由一条线连接的)。
另一个缺点是由于它们是多边形,因此整体形状会生成某种形式或扭曲的圆形。有很多类型的路径永远不会生成,比如螺旋。
有人知道可以帮助我生成这些路径的算法吗?
我需要生成一个包含 25 个段的随机路径,该路径永远不会在 1000x1000 区域中的两个位置之间交叉。什么是一个好的算法来做到这一点?
我最初的想法是使用空间分割方法生成一个随机多边形,然后删除一侧。
这种方法的缺点是起点总是非常接近终点(因为它们最初是由一条线连接的)。
另一个缺点是由于它们是多边形,因此整体形状会生成某种形式或扭曲的圆形。有很多类型的路径永远不会生成,比如螺旋。
有人知道可以帮助我生成这些路径的算法吗?
这是一个想法(免责声明:在我脑海中,未经测试,验证或任何东西......):
绘制随机坐标并“尝试”按照您绘制的顺序连接线 - 所以您有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 时间复杂度,但它应该能够生成各种路径。
在实现数据结构方面,双向链表似乎是一个直接的候选者。
对点集进行三角剖分然后在边缘上行走是一种解决方案,可以避免基于多边形的行走所具有的“类圆形”路径的问题。
您可能不希望随机点集的点靠得太近,因为它可能导致路径看起来像是在某些点与自身相交。出于这个原因,使用类似泊松盘采样方法来生成点集是可取的——这种点集的三角剖分将提供一条随机路径,其长度或多或少相等,线段角度约为 60 ° 并且没有明显的交叉点。
有了 Delaunay 三角剖分库,算法如下所示:
要初始化,
lastVisitedVertex
)然后循环:
lastVisitedVertex
= 选定边的另一个顶点三角泊松圆盘点集上的随机路径
[
这是一个使用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;
}