Dear list useRs, I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 for say, N points. At each of these points is drawn a circle (later on, an ellipse) of random size, as in:> N <- 100 > > positions <- matrix(rnorm(2 * N, mean = 0 , sd= 0.5), nrow=N) > sizes<-rnorm(N, mean = 0 , sd= 1) > plot(positions,type="p",cex=sizes)My problem is to avoid collisions (overlap, really) between the points. I would like some random pattern, but with a minimum exclusion distance. In looking up "Numerical recipes in C", I found out about some Sobol quasi-random sequences, which one can call from the gsl package,> library(gsl) > > g <- qrng_alloc(type="sobol",dim=2) > qrng_get(g,n= N) ->xy > > plot((xy),t="p",cex=0.5)but this does not look very random: I clearly see some pattern (diagonals, etc...), and even the non-overlapping condition is not impressive. One (painful) way I can foresee is to check the distance between each symbol and the others, and move the overlapping ones in a recursive manner. Before delving into this, I wanted to check I'm not overlooking something in the rgl quasi-random sequences, or missing a more obvious way to generate such patterns. Perhaps solving an electrostatic problem with a potential both attractive at long distances and repulsive at short distances is a better way? I have a vague recollection of hearing that somewhere to position points evenly on a sphere. Thanks for any comment / suggestion, Baptiste _____________________________ Baptiste Augui? Physics Department University of Exeter Stocker Road, Exeter, Devon, EX4 4QL, UK Phone: +44 1392 264187 http://newton.ex.ac.uk/research/emag http://projects.ex.ac.uk/atto
baptiste Augui? wrote:> Dear list useRs, > > I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 > for say, N points. At each of these points is drawn a circle (later > on, an ellipse) of random size, as in: > >The quasi-random sequences are useful for integration, but they're not random in the sense of being unpredictable. Here's an idea for a sequence that might work for you: divide the square into an n x n grid of smaller squares. Randomly select a smaller square, then uniformly select a point within it. (Or just permute the list of all n^2 squares, and proceed through the permuted list.) This won't guarantee a separation, but it will tend to lead to one. If you want a guarantee, then only select from squares with even coordinates. Once you've selected all the squares in the grid, go to a 2n x 2n grid, and repeat. (If you are doing the "even coordinates" modification, you'll have had to select non-uniformly for this to work.) Duncan Murdoch> >> N <- 100 >> >> positions <- matrix(rnorm(2 * N, mean = 0 , sd= 0.5), nrow=N) >> sizes<-rnorm(N, mean = 0 , sd= 1) >> plot(positions,type="p",cex=sizes) >> > > > My problem is to avoid collisions (overlap, really) between the > points. I would like some random pattern, but with a minimum > exclusion distance. In looking up "Numerical recipes in C", I found > out about some Sobol quasi-random sequences, which one can call from > the gsl package, > > > >> library(gsl) >> >> g <- qrng_alloc(type="sobol",dim=2) >> qrng_get(g,n= N) ->xy >> >> plot((xy),t="p",cex=0.5) >> > > but this does not look very random: I clearly see some pattern > (diagonals, etc...), and even the non-overlapping condition is not > impressive. > > One (painful) way I can foresee is to check the distance between each > symbol and the others, and move the overlapping ones in a recursive > manner. Before delving into this, I wanted to check I'm not > overlooking something in the rgl quasi-random sequences, or missing a > more obvious way to generate such patterns. Perhaps solving an > electrostatic problem with a potential both attractive at long > distances and repulsive at short distances is a better way? I have a > vague recollection of hearing that somewhere to position points > evenly on a sphere. > > > Thanks for any comment / suggestion, > > Baptiste > > > _____________________________ > > Baptiste Augui? > > Physics Department > University of Exeter > Stocker Road, > Exeter, Devon, > EX4 4QL, UK > > Phone: +44 1392 264187 > > http://newton.ex.ac.uk/research/emag > http://projects.ex.ac.uk/atto > > ______________________________________________ > R-help at r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >
On Sat, 26 Apr 2008, baptiste Augui? wrote:> Dear list useRs, > > I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 > for say, N points. At each of these points is drawn a circle (later > on, an ellipse) of random size, as in: > > >> N <- 100 >> >> positions <- matrix(rnorm(2 * N, mean = 0 , sd= 0.5), nrow=N) >> sizes<-rnorm(N, mean = 0 , sd= 1) >> plot(positions,type="p",cex=sizes) > > > My problem is to avoid collisions (overlap, really) between the > points. I would like some random pattern, but with a minimum > exclusion distance. In looking up "Numerical recipes in C", I found > out about some Sobol quasi-random sequences, which one can call from > the gsl package,That is a hard-core point process, e.g. a special case of a Strauss process. You will find ways to simulate such a process (there are several processes, and several ways for most) in the various spatial packages, including 'spatial' itself. I think you have misunderstood the point of quasi-random sequences (which, given the exposition in the edition of NR I have, would be easy to do).>> library(gsl) >> >> g <- qrng_alloc(type="sobol",dim=2) >> qrng_get(g,n= N) ->xy >> >> plot((xy),t="p",cex=0.5) > > but this does not look very random: I clearly see some pattern > (diagonals, etc...), and even the non-overlapping condition is not > impressive. > > One (painful) way I can foresee is to check the distance between each > symbol and the others, and move the overlapping ones in a recursive > manner. Before delving into this, I wanted to check I'm not > overlooking something in the rgl quasi-random sequences, or missing a > more obvious way to generate such patterns. Perhaps solving an > electrostatic problem with a potential both attractive at long > distances and repulsive at short distances is a better way? I have a > vague recollection of hearing that somewhere to position points > evenly on a sphere. > > > Thanks for any comment / suggestion, > > Baptiste > > > _____________________________ > > Baptiste Augui? > > Physics Department > University of Exeter > Stocker Road, > Exeter, Devon, > EX4 4QL, UK > > Phone: +44 1392 264187 > > http://newton.ex.ac.uk/research/emag > http://projects.ex.ac.uk/atto > > ______________________________________________ > R-help at r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >-- Brian D. Ripley, ripley at stats.ox.ac.uk Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/ University of Oxford, Tel: +44 1865 272861 (self) 1 South Parks Road, +44 1865 272866 (PA) Oxford OX1 3TG, UK Fax: +44 1865 272595
You seem to have ambiguous requirements. First, you want equidistribution for a packing structure, which would suggest closest packing or quasirandom sequences, as you have tried. But then you are disturbed by the packing structure, because it gives a perceivable pattern, so you wish to randomize it, but under some unspecified condition of equidistribution (your "electrostatic repulsion" algorithm). You obviously have some constraints on selection you have not quantified yet. E.g., circles of unspecified radii cannot overlap. You should also realize that any distribution of centers under such constraints will always exhibit structure due to the constraints. Is your problem simply to give an appearance of randomness to the casual observer, or something more definite? You also need to say something about the packing density involved. On the face of it, you with At 06:22 AM 4/26/2008, baptiste Augui? wrote:>Dear list useRs, > >I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 >for say, N points. At each of these points is drawn a circle (later >on, an ellipse) of random size, as in: > > > > N <- 100 > > > > positions <- matrix(rnorm(2 * N, mean = 0 , sd= 0.5), nrow=N) > > sizes<-rnorm(N, mean = 0 , sd= 1) > > plot(positions,type="p",cex=sizes) > > >My problem is to avoid collisions (overlap, really) between the >points. I would like some random pattern, but with a minimum >exclusion distance. In looking up "Numerical recipes in C", I found >out about some Sobol quasi-random sequences, which one can call from >the gsl package, > > > > library(gsl) > > > > g <- qrng_alloc(type="sobol",dim=2) > > qrng_get(g,n= N) ->xy > > > > plot((xy),t="p",cex=0.5) > >but this does not look very random: I clearly see some pattern >(diagonals, etc...), and even the non-overlapping condition is not >impressive. > >One (painful) way I can foresee is to check the distance between each >symbol and the others, and move the overlapping ones in a recursive >manner. Before delving into this, I wanted to check I'm not >overlooking something in the rgl quasi-random sequences, or missing a >more obvious way to generate such patterns. Perhaps solving an >electrostatic problem with a potential both attractive at long >distances and repulsive at short distances is a better way? I have a >vague recollection of hearing that somewhere to position points >evenly on a sphere. > > >Thanks for any comment / suggestion, > >Baptiste > > >_____________________________ > >Baptiste Augui? > >Physics Department >University of Exeter >Stocker Road, >Exeter, Devon, >EX4 4QL, UK > >Phone: +44 1392 264187 > >http://newton.ex.ac.uk/research/emag >http://projects.ex.ac.uk/atto > >______________________________________________ >R-help at r-project.org mailing list >https://stat.ethz.ch/mailman/listinfo/r-help >PLEASE do read the posting guide http://www.R-project.org/posting-guide.html >and provide commented, minimal, self-contained, reproducible code.===============================================================Robert A. LaBudde, PhD, PAS, Dpl. ACAFS e-mail: ral at lcfltd.com Least Cost Formulations, Ltd. URL: http://lcfltd.com/ 824 Timberlake Drive Tel: 757-467-0954 Virginia Beach, VA 23464-3239 Fax: 757-467-2947 "Vere scire est per causas scire" ================================================================
baptiste Augui? <ba208 <at> exeter.ac.uk> writes:> > Dear list useRs,You might be interested to apply the Hammersley or Halton point sets that are often used in numerical integration or Differential Evolution. These pseudo-random distributions are both uniform and irregular, but have a kind of minimum resolution There is an implementation of Halton Sequences in the often overlooked 'sfsmisc' package, see the 'QUnif()' function there. The help includes a visualization example dispaying the behavior I think you were looking for. Hans Werner> I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 > for say, N points. At each of these points is drawn a circle (later > on, an ellipse) of random size, [...] > > My problem is to avoid collisions (overlap, really) between the > points. I would like some random pattern, but with a minimum > exclusion distance. In looking up "Numerical recipes in C", I found > out about some Sobol quasi-random sequences, which one can call from > the gsl package, > [...] > but this does not look very random: I clearly see some pattern > (diagonals, etc...), and even the non-overlapping condition is not > impressive. > > One (painful) way I can foresee is to check the distance between each > symbol and the others, and move the overlapping ones in a recursive > manner. Before delving into this, I wanted to check I'm not > overlooking something in the rgl quasi-random sequences, or missing a > more obvious way to generate such patterns. Perhaps solving an > electrostatic problem with a potential both attractive at long > distances and repulsive at short distances is a better way? I have a > vague recollection of hearing that somewhere to position points > evenly on a sphere. > > Thanks for any comment / suggestion, > > Baptiste >
You might want to shuffle coordinates independently to get rid of the diagonals. Otherwise what quasi-random sequence guarantee are upper boundaries on the coverage errors, but not anything nice-looking and irregular. Sobol' sequences, even though they are theoretically superior to some others (e.g., Halton sequences more popular among economists), are especially nasty in producing bands and bricks on the low dimensional plots. Among statisticians, Art Owen from Stanford is almost the only one interested in this sort of stuff (referred to as quasi-Monte Carlo, in his field(s)). You might have better luck on a physics list with a question like yours. On Sat, Apr 26, 2008 at 5:22 AM, baptiste Augui? <ba208 at exeter.ac.uk> wrote: > Dear list useRs, > > I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 > for say, N points. At each of these points is drawn a circle (later > on, an ellipse) of random size, as in: > > > > N <- 100 > > > > positions <- matrix(rnorm(2 * N, mean = 0 , sd= 0.5), nrow=N) > > sizes<-rnorm(N, mean = 0 , sd= 1) > > plot(positions,type="p",cex=sizes) > > > My problem is to avoid collisions (overlap, really) between the > points. I would like some random pattern, but with a minimum > exclusion distance. In looking up "Numerical recipes in C", I found > out about some Sobol quasi-random sequences, which one can call from > the gsl package, > > > > library(gsl) > > > > g <- qrng_alloc(type="sobol",dim=2) > > qrng_get(g,n= N) ->xy > > > > plot((xy),t="p",cex=0.5) > > but this does not look very random: I clearly see some pattern > (diagonals, etc...), and even the non-overlapping condition is not > impressive. > > One (painful) way I can foresee is to check the distance between each > symbol and the others, and move the overlapping ones in a recursive > manner. Before delving into this, I wanted to check I'm not > overlooking something in the rgl quasi-random sequences, or missing a > more obvious way to generate such patterns. Perhaps solving an > electrostatic problem with a potential both attractive at long > distances and repulsive at short distances is a better way? I have a > vague recollection of hearing that somewhere to position points > evenly on a sphere. > -- Stas Kolenikov, also found at http://stas.kolenikov.name Small print: I don't check Gmail account regularly.
Baptiste Augui? writes:> I have to generate a random set of coordinates (x,y) in [-1 ; 1]^2 > for say, N points. > [...] > My problem is to avoid collisions (overlap, really) between the > points. I would like some random pattern, but with a minimum > exclusion distance.As Brian Ripley has mentioned, there are several algorithms available in the contributed packages for spatial statistics, particularly 'spatial', 'splancs' and 'spatstat'. For example in the 'spatstat' package you could try the following algorithms which generate random point patterns that respect a 'hard core' (i.e. no points ever come closer than the specified distance): rSSI Simple Sequential Inhibition (places points randomly one-at-a-time) rMaternI rMaternII Matern Inhibition processes (places points randomly, then deletes offending points) rstrat Stratified random sampling (divides region into squares, then places N points in each square; use N=1) The following algorithms generate point patterns with a `soft core' (tendency to avoid placing points close together): rStrauss Strauss point process (inhibition parameter gamma controls 'softness' of core) rmh Metropolis-Hastings simulation algorithm (various choices of model) You can also generate a regular grid of points (randomly shifted) and then randomly perturb each point: library(spatstat) W <- owin(c(-1,1),c(-1,1)) X <- rstrat(W, nx=10, ny=10, k=1) X <- rshift(X, group=factor(seq(X$n)), radius=0.05, edge="torus") plot(X) Adrian Baddeley