[R] sampling from the unoform distrubuton over a convex hull

[Duncan Murdoch]

On 3/24/2007 1:43 AM, Ranjan Maitra wrote:
> Dear list,
> 
> Does anyone have a suggestion (or better still) code for sampling from the uniform distribution over the convex hull of a set of points?

Are you talking about two dimensional points, or higher dimensions?  The 
suggestion below works for any dimension, but the actual code is 
2-dimensional. I don't know if there's an equivalent of chull available 
for higher dimensions.

Suggestion:  Find a rectangular region containing the hull, and sample 
uniformly there.  Accept points that don't expand the hull of the 
original points.

For example:

rhull <- function(n,x) {
   boundary <- x[chull(x),]

   xlim <- range(boundary[,1])
   ylim <- range(boundary[,2])

   boundary <- rbind(c(NA,NA), boundary)  # add space for new test point

   result <- matrix(NA, n, 2)

   for (i in 1:n) {
     repeat {
       boundary[1,1] <- runif(1, xlim[1], xlim[2])
       boundary[1,2] <- runif(1, ylim[1], ylim[2])
       if ( !(1 %in% chull(boundary)) ) {
	  result[i,] <- boundary[1,]
         break
       }
     }
   }

   result
}

x <- matrix(rnorm(20), ncol=2)
plot(x, cex=2, col="red")
sample <- rhull(1000, x)
points(sample)

Duncan Murdoch