Ok My 2c is going to go up to a quarter. Having discussed this a little more with a colleague, we realized that a sequential approach may not work so well, because in a finite region so many configurations would be inadmissible and and you would have to reject the whole thing, unless the density of disks is sparse. So this really is a yucky problem.
Nicholas On Fri, 28 May 2010 08:51 -0700, "Nicholas Lewin-Koh" <ni...@hailmail.net> wrote: > Hi, > I don't think the code exists, but I think that there are modifications > of the > algorithm Rolf described that may be much faster. I assume the > predetermined > set of marks is a set of distinct classes with different radii. > One thing that comes to mind is you may want to generate the marks first > and > then assign locations. So if you allocate the largest radii first, you > may be able to > sequentially eliminate whole regions of the space where the next disk > could be allocated > using a quad tree, and there by do fewer rejections of locations. There > may be some > divide and conquer type strategies that work as well. > > Thinking about this more, it seems like the most time consuming step > would be the > acceptance/rejection of new locations because of the search for adjacent > intersecting discs. > So as the plane fills up there will be more and more rejections, and the > search time will increase. > In fact for a finite area, there will be an upper bound on the number of > points depending on > the distribution of marks. Which suggest that one would want to first > generate the marks, and check that the > sum of the disks is less than the total area of your region. > > So as I am musing here, and probably getting less and less helpful, I am > thinking that > using the delaunay triangulation or the nearest neighbor graph might > help speed up the search. > I am also wondering if one could condition on the existing points more > efficiently, may > be using some sort of metropolis hastings type algorithm to ensure that > the next draw > is closer to the restricted space available. I am even guessing there > may be some percolation > model that would approximate this process and be faster to generate. > > Ok used up my 2c. Hope this helps > > Nicholas > > > > > > Date: Fri, 28 May 2010 10:00:35 +1200 > > From: Rolf Turner <r.tur...@auckland.ac.nz> > > To: Quets Jan <jan.qu...@ua.ac.be> > > Cc: "r-sig-geo@stat.math.ethz.ch" <r-sig-geo@stat.math.ethz.ch> > > Subject: Re: [R-sig-Geo] existance of a specific non-overlapping > > marked spatial model in spatstat or other R package? > > Message-ID: <b9268b92-b6f4-420c-af04-eee1da182...@auckland.ac.nz> > > Content-Type: text/plain; charset="us-ascii" > > > > > > On 28/05/2010, at 8:53 AM, Quets Jan wrote: > > > > > > > > Hi, > > > > > > I am looking for a specific non-overlapping marked spatial model for use > > > as a null model for monte carle simulations with use of the 'envelope' > > > function in spatstat. > > > > > > the specific marked spatial model should: > > > ----------------- > > > *generate a spatial random pattern with a predetermined number of points > > > (with conditions set below) > > > > > > *each point should be assigned a mark randomly out of a predetermined set > > > of marks > > > > > > *these marks represent the radia of circular discs which should be drawn > > > around these points (which act as centres) > > > > > > *no discs should overlap > > > ----------------- > > > > > > Does anybody has knowledge of a such a built in model in spatstat or > > > another R package? > > > > > > For now, I have built this model by myself, but it turns out to have a > > > very time-consuming running time, especially when used as a null model in > > > a monte carlo simulation. Also I have multiple monte carlo simulations to > > > perform. > > > > > > It will be of great help, > > > > The only way I can think of doing this is sequentially. I.e. select a > > radius, > > then repetitively select a point to add, rejecting the selected point if > > its > > circle (with the chosen radius) intersects any of the existing circles. > > If > > after ``giveup'' attempts the function has failed to find an acceptable > > point, > > it gives up (and throws an error). > > > > I cobbled together some code to effect this; it took one minute of user > > time > > to do 100 replications of choosing 100 points with non-overlapping > > circles > > in the unit square, with the radii selected uniform-randomly from > > (1:5)/100 > > and giveup=1000. > > > > I believe that it would require a lot of work and great cleverness to get > > anything substantially faster. Of course, I could be wrong --- I was > > once, > > back in 1968 when I thought I'd made a mistake and I hadn't. :-) > > > > cheers, > > > > Rolf Turner > > > > P. S. Let me know if you want my code. I suspect it's not much > > different > > from what you have built yourself. > > > > R. > > ###################################################################### > > Attention: > > This e-mail message is privileged and confidential. If you are not the > > intended recipient please delete the message and notify the sender. > > Any views or opinions presented are solely those of the author. > > > > This e-mail has been scanned and cleared by MailMarshal > > www.marshalsoftware.com > > ###################################################################### > > > > > > _______________________________________________ R-sig-Geo mailing list R-sig-Geo@stat.math.ethz.ch https://stat.ethz.ch/mailman/listinfo/r-sig-geo
