距離で弾いて散らす
乱数をそのまま撒くと、点は均等に並ばない。たまたま固まったり、ぽっかり空いたりして、塊と穴ができる。
「すでにある点から距離 r 以内には置かない」という制約をかける。候補をランダムに作り、既存点に近すぎたら捨て、残ったものだけ採用する。
棄却サンプリング。近すぎる候補を捨てて残りだけ採る手口。距離 r の制約を満たす配置はブルーノイズになる。一様にばらけているのに格子のような規則性を持たず、周波数で見ると低い成分が抜けて高い成分だけが残る。網膜の錐体細胞の並びやサンプリングのジッタに使われ、規則的な格子が生むモアレや偽の縞を避けられる。
最小の棄却サンプリングは、毎フレーム何度もランダム位置に置こうとして、既存点に近すぎたら描かずに捨てる。fits が全点と総当たりで距離を測り、r * r より近い点が一つでもあれば false を返す。
fits が false を返した候補は continue で捨て、点を打たない。隙間が埋まると、投げた候補のほとんどが既存点に当たって弾かれ、後半は空振りが続いて新しい点が増えなくなる。r を小さくすると点が密に詰まり、大きくすると早く頭打ちになる。
候補を画面全体でなく入った点のまわりだけから投げると、空振りが減る。各点の周囲、半径 r〜2r の輪に候補を tries 回投げる。一つでも入れば置いて、その新しい点も候補源 active に積む。tries 回投げても一つも入らなければ、その点の周りはもう埋まったと見て候補源から外す。active が尽きると面全体が埋まり切っている。
poisson disk サンプリングの Bridson 法（2007 年）。入った点を次の候補源にして輪へ投げ直す。候補を盤面全体に撒く素朴な棄却と違い、すでに置いた点の隣だけを攻めるので、点の総数に比例した時間で埋まる。各点を r/√2 幅のマスに登録しておくと、近すぎ判定が周囲数マスだけで済む。マス幅をこの値に取ると 1 マスに点は高々一つしか入らず、距離 r 以内の点は中心から ±2 マスの範囲に必ず収まる。
Bridson 法は、盤面を r/√2 幅のマスに切り、点を落ちたマスに登録する。輪へ投げた候補は fits が周囲 5×5 マスだけを見て近すぎを判定する。種点をいくつか撒いて、そこから輪を広げていく。新しい点が既存の点の輪に落ちて、空白が外側へ押し出されながら詰まっていく。
種点から輪が広がり、面が一様に詰まったところで active が尽きて打ち止めになる。素朴な棄却で後半に増えていた空振りが、輪へ投げるぶん減って、点の数に比例した手間で全面が埋まる。r を小さくすると点が密になり、マスの数も増える。tries を減らすと縁が早く諦められて隙間が残り、増やすとぎりぎりまで詰める。