existance of a specific non-overlapping marked spatial model in spatstat or other R package?
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"
<nikko at 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.turner at auckland.ac.nz> To: Quets Jan <Jan.Quets at ua.ac.be> Cc: "r-sig-geo at stat.math.ethz.ch" <r-sig-geo at 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-EEE1DA182F67 at 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 ######################################################################