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
