package Ġorg . open rnd r . extra . noise Ċ Ċ import Ġorg . open rnd r . math . Pol ar Ċ import Ġorg . open rnd r . math . Vector 2 Ċ import Ġorg . open rnd r . math . clamp Ċ import Ġorg . open rnd r . shape . Rectangle Ċ import Ġkotlin . math . ceil Ċ import Ġkotlin . math . sqrt Ċ Ċ /* Ċ * ĠTODO Ġv 2 Ċ * Ġ Ġ* ĠGeneral ize Ġto Ġ 3 Ġdimensions Ċ */ Ċ Ċ internal Ġconst Ġval Ġepsilon Ġ= Ġ 0 . 0 0 0 0 0 0 1 Ċ Ċ /** Ċ Ġ* ĠCreates Ġa Ġrandom Ġpoint Ġdistribution Ġon Ġa Ġgiven Ġarea Ċ Ġ* ĠEach Ġpoint Ġgets Ġn Ġ[ tri es ] Ġat Ġgenerating Ġthe Ġnext Ġpoint Ċ Ġ* ĠBy Ġdefault Ġthe Ġpoints Ġare Ġgenerated Ġalong Ġthe Ġcircum ference Ġof Ġr Ġ+ Ġepsilon Ġto Ġthe Ġpoint Ċ Ġ* ĠThey Ġcan Ġalso Ġbe Ġgenerated Ġon Ġa Ġring Ġlike Ġin Ġthe Ġoriginal Ġalgorithm Ġfrom ĠRobert ĠB rid son Ċ Ġ* Ċ Ġ* Ġ@ param Ġwidth Ġthe Ġwidth Ġof Ġthe Ġarea Ċ Ġ* Ġ@ param Ġheight Ġthe Ġheight Ġof Ġthe Ġarea Ċ Ġ* Ġ@ param Ġr Ġthe Ġminimum Ġdistance Ġbetween Ġeach Ġpoint Ċ Ġ* Ġ@ param Ġtries Ġnumber Ġof Ġcandidates Ġper Ġpoint Ċ Ġ* Ġ@ param Ġbounds Mapper Ġa Ġcustom Ġfunction Ġto Ġcheck Ġif Ġa Ġpoint Ġis Ġwithin Ġbounds Ċ Ġ* Ġ@ param Ġrandom On Ring Ġgenerate Ġrandom Ġpoints Ġon Ġa Ġring Ġwith Ġan Ġann ulus Ġfrom Ġr Ġto Ġ 2 r Ċ Ġ* Ġ@ return Ġa Ġlist Ġof Ġpoints Ċ Ġ*/ Ċ fun Ġpo isson Disk Sampling ( ĊĠĠĠĠĠĠĠ Ġwidth : ĠDouble , ĊĠĠĠĠĠĠĠ Ġheight : ĠDouble , ĊĠĠĠĠĠĠĠ Ġr : ĠDouble , ĊĠĠĠĠĠĠĠ Ġtries : ĠInt Ġ= Ġ 3 0 , ĊĠĠĠĠĠĠĠ Ġrandom On Ring : ĠBoolean Ġ= Ġfalse , ĊĠĠĠĠĠĠĠ Ġbounds Mapper : Ġ(( w : ĠDouble , Ġh : ĠDouble , Ġv : ĠVector 2 ) Ġ-> ĠBoolean )? Ġ= Ġnull Ċ ): ĠList < Vector 2 > Ġ{ ĊĠĠĠ Ġval Ġdisk Ġ= Ġmutable ListOf < Vector 2 >() ĊĠĠĠ Ġval Ġqueue Ġ= Ġmutable ListOf < Int >() ĊĊĠĠĠ Ġval Ġr 2 Ġ= Ġr Ġ* Ġr ĊĠĠĠ Ġval Ġradius Ġ= Ġr Ġ+ Ġepsilon ĊĊĠĠĠ Ġval Ġcell Size Ġ= Ġr Ġ/ Ġsqrt ( 2 . 0 ) ĊĠĠĠ Ġval Ġrows Ġ= Ġceil ( height Ġ/ Ġcell Size ). toInt () ĊĠĠĠ Ġval Ġcols Ġ= Ġceil ( width Ġ/ Ġcell Size ). toInt () ĊĊĠĠĠ Ġval Ġgrid Ġ= ĠList ( rows Ġ* Ġcols ) Ġ{ Ġ- 1 Ġ}. to Mutable List () ĊĊĠĠĠ Ġfun Ġadd Point ( v : ĠVector 2 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġ( v . x Ġ/ Ġcell Size ). fast Floor () ĊĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġ( v . y Ġ/ Ġcell Size ). fast Floor () ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġx Ġ+ Ġy Ġ* Ġcols ĊĊĠĠĠĠĠĠĠ Ġdisk . add ( v ) ĊĊĠĠĠĠĠĠĠ Ġgrid [ index ] Ġ= Ġdisk . last Index ĊĊĠĠĠĠĠĠĠ Ġqueue . add ( disk . last Index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġadd Point ( Vector 2 ( width Ġ/ Ġ 2 . 0 , Ġheight Ġ/ Ġ 2 . 0 )) ĊĊĠĠĠ Ġval Ġbounds Rect Ġ= ĠRectangle ( 0 . 0 , Ġ 0 . 0 , Ġwidth , Ġheight ) ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġactive Index Ġ= ĠRandom . pick ( queue ) ĊĠĠĠĠĠĠĠ Ġval Ġactive Ġ= Ġdisk [ active Index ] ĊĊĠĠĠĠĠĠĠ Ġvar Ġcandidate Accepted Ġ= Ġfalse ĊĊĠĠĠĠĠĠĠ Ġcandidate Search @ Ġfor Ġ( l Ġin Ġ 0 Ġuntil Ġtries ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc Ġ= Ġif Ġ( random On Ring ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Ġ+ ĠRandom . ring 2 d ( r , Ġ 2 Ġ* Ġr ) Ġas ĠVector 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Ġ+ ĠPol ar ( Random . double 0 ( 3 6 0 . 0 ), Ġradius ). cart esian ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! bounds Rect . contains ( c )) Ġcontinue @ candidate Search ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġit 's Ġwithin Ġbounds ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġchoose Ġanother Ġcandidate Ġif Ġit 's Ġnot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( bounds Mapper Ġ!= Ġnull Ġ&& Ġ! bounds Mapper ( width , Ġheight , Ġc )) Ġcontinue @ candidate Search ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġ( c . x Ġ/ Ġcell Size ). fast Floor () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġ( c . y Ġ/ Ġcell Size ). fast Floor () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCheck Ġclosest Ġne ighbours Ġin Ġa Ġ 5 x 5 Ġgrid ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( ix Ġin Ġ(- 2 .. 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( iy Ġin Ġ(- 2 .. 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnx Ġ= Ġclamp ( x Ġ+ Ġix , Ġ 0 , Ġcols Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġny Ġ= Ġclamp ( y Ġ+ Ġiy , Ġ 0 , Ġrows Ġ- Ġ 1 ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġneighbor Idx Ġ= Ġgrid [ nx Ġ+ Ġny Ġ* Ġcols ] ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ- 1 Ġmeans Ġthe Ġgrid Ġhas Ġno Ġsample Ġat Ġthat Ġpoint ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( neighbor Idx Ġ== Ġ- 1 ) Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġneighbor Ġ= Ġdisk [ neighbor Idx ] ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġcandidate Ġis Ġwithin Ġone Ġof Ġthe Ġne ighbours Ġradius , Ġtry Ġanother Ġcandidate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( neighbor Ġ- Ġc ). squared Length Ġ<= Ġr 2 ) Ġcontinue @ candidate Search ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Point ( c ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcandidate Accepted Ġ= Ġtrue ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġno Ġcandidate Ġwas Ġaccepted , Ġremove Ġthe Ġsample Ġfrom Ġthe Ġactive Ġlist ĊĠĠĠĠĠĠĠ Ġif Ġ(! candidate Accepted ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . remove ( active Index ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġdisk Ċ }