c++ - 如何避免中点位移期间的重叠？(2D)

Question

大家好！好吧，我正在玩随机游走。中点位移给出了一些不错的结果，但我想要一个没有行走循环的随机行走，就像这个屏幕热上的那些（黄色）：

我处理该问题的第一个想法是检查每个线段是否与所有其他线段相交，然后删除两个线段之间的步行循环并在交叉点处绑定。但是对于某些散步，它会给出一个奇怪的结果，就像那个：

其中黄色部分是一个循环，我们可以看到如果我按照我说的去做，大部分步行都会被删除。

也许另一种方法是检查，当中点发生位移时，线段是否相交。万一有交叉路口，再换一个位移。但是当细分数量增加时，它看起来会很快变得非常耗时......

所以我想知道是否有办法避免这些循环

Answer 1

所以......似乎玩随机数的幅度是避免重叠的好方法：

没有位移的路径以青色绘制。我没有与这些位移重叠：

do{
     dx = (D>0)? 0.5*sqrt((double)(rand()%D)) - sqrt((double)D)/2. : 0 ;
     dz = (D>0)? 0.5*sqrt((double)(rand()%D)) - sqrt((double)D)/2. : 0 ;
   }while(dx*dx+dz*dz>D);

其中D是我们要置换的点的两个邻居之间的平方距离。(D>0)?需要避免Floating Point Exception一些.