Как избежать наложений во время смещения в средней точке? (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,