how to avoid overlaps during midpoint displacement? (2D)

Question

hell-o guys! well, I'm playing with random walks. Midpoint displacement gives some nice results, but I would like a random walk without walk loops, like the ones (in yellow) on this screen-hot :

My first idea to deal with that problem is to check for each segment if there is an intersection with all others segments, then to delete the walk loop between the both segments and bind at the interesection point. But for some walks, it would give a strange result, like that one :

where the yellow part is a loop, and we can see that a big part of the walk would be deleted if I do what I said.

Maybe another method would be to check, when the displacement of the midpoint is made, if the segments are interesecting. In case of there is an intersection, get another displacment. But it looks to become very time consuming quickly when the number of subdivisions rises...

So I would like to know if there is a way to avoid these loops

Answer 1

so... it's seems playing with the amplitudes of the random numbers is a good way to avoid overlaps :

the path without displacement is drawn in cyan. I didn't get overlaps with these displacments :

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);

where D is the squared distance between the two neibourers of the point we want to displace. The (D>0)? is needed to avoid some Floating Point Exception.