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は、移動したい点の 2 つの隣接点の間の距離の 2乗です。(D>0)?を避けるために必要ですFloating Point Exception。