R help - Nov 2013 - overlaying 2D grid on randomly distributed points

Hi, I have a cloud of randomly distributed points in 2-dimensional space and
want to set up a grid, with a given grid-cell size, that minimizes the distance
between my points and the grid nodes. Does anyone know of an R function or
toolbox that somehow addresses this problem? This is a problem of optimizing the
location of the grid, not a problem of deciding what should be the grid-cell
size, because size is already given. Thank you.
Gon?alo

Gonçalo,

Interesting question.  You can use the optim() function to optimize a
function over two dimensions.  Here's an example.

# some clumpy "cloud" data
myx <- c(0.3 + rnorm(50, 0, 0.05), 0.7 + rnorm(50, 0, 0.05))
myy <- c(0.45 + rnorm(50, 0, 0.05), 0.65 + rnorm(50, 0, 0.05))

# size of the fixed square grid
mygrid <- 0.2

# function to calculate the mean distance to the grid nodes
# the first argument, par, is the starting coordinates of the grid
calcd <- function(par, x=myx, y=myy, grid=mygrid) {
 dx <- abs((x - par[1]) %% grid)
dy <- abs((y - par[2]) %% grid)
 dx <- ifelse(dx > grid/2, grid - dx, dx)
dy <- ifelse(dy > grid/2, grid - dy, dy)
 mean(sqrt(dx^2 + dy^2))
}

# find starting coordinates that minimize the mean distance
opt <- optim(cbind(x0=mygrid/2, y0=mygrid/2), calcd)
opt$par

# look at results
library(MASS)
eqscplot(myx, myy)
abline(v=seq(from=opt$par[1], to=max(myx), by=mygrid))
abline(h=seq(from=opt$par[2], to=max(myy), by=mygrid))

Jean



On Thu, Nov 21, 2013 at 6:47 AM, Gonçalo Ferraz <gferraz29@gmail.com>
wrote:
> Hi, I have a cloud of randomly distributed points in 2-dimensional space
> and want to set up a grid, with a given grid-cell size, that minimizes the
> distance between my points and the grid nodes. Does anyone know of an R
> function or toolbox that somehow addresses this problem? This is a problem
> of optimizing the location of the grid, not a problem of deciding what
> should be the grid-cell size, because size is already given. Thank you.
> Gonçalo
> ______________________________________________
> R-help@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.
>
	[[alternative HTML version deleted]]

How about this?

require(FNN)


#FOR DEMONSTRATION PURPOSES, GENERATE 2D DATA
set.seed(3242)
X <- matrix(runif(50),ncol=2)
plot(X,pch=16,cex=1.5, asp=1)

#PLOT GRID
grid <- as.matrix(expand.grid(seq(0,1,by=.1),seq(0,1,by=.1)) )
abline(v=unique(grid[,1]),col="#FF000030")
abline(h=unique(grid[,2]),col="#FF000030")

#FIND NEAREST GRID POINT
nearestn <- get.knnx(data=grid,query=X,k=1,algorithm="kd_tree")

#PLOT LINE BETWEEN DATA AND GRID POINT
for(i in 1:nrow(X)){
  lines(rbind(X[i,], grid[nearestn$nn.index[i],]), col="red",lwd=2)
}

### IDEA: WRITE FUNCTION THAT OUTPUTS THE SUM OF SQUARED DISTANCES, THEN
MINIMIZE IT



#FUNCTION THAT RETURNS SUM OF SQUARED DISTANCES FOR A GIVEN GRID
one.grid <- function(X,grid){
  nearestn <- get.knnx(data=grid,query=X,k=1,algorithm="kd_tree")
  dists <- rowSums((grid[nearestn$nn.index,] - X)^2)
  return(sum(dists))
}

#FUNCTION THAT CREATES A GRID BASED ON THE OFFSET FROM LOWER-MOST AND
LEFT-MOST POINT
define.grid <- function(X, offset, grid.size){
  colmins <- apply(X,2,min)
  colmaxs <- apply(X,2,max)

  grid <- expand.grid(seq(colmins[1] - offset[1] ,colmaxs[1] + grid.size
,by=grid.size), seq(colmins[2] - offset[2], colmaxs[2] + grid.size,
by=grid.size))
  return(grid)
}

#FUNCTION THAT RETURNS THE OPTIMAL GRID (FOUND BY GRID SEARCH, NO PUN
INTENDED)
find.grid <- function(X,grid.size=1){
  out <- optim(c(grid.size/2,grid.size/2), fn = function(par){ one.grid(X,
define.grid(X,par, grid.size)) }, lower=c(0,0), upper=c(grid.size,
grid.size), method="L-BFGS-B")
  best.grid <- define.grid(X,out$par,grid.size)
  return(best.grid)
}


#PLOT OPTIMAL GRID
plot(X,pch=16,cex=1.5, asp=1)
bg <- find.grid(X,.1)
abline(v=unique(bg[,1]),col="#2491B230")
abline(h=unique(bg[,2]),col="#2491B230")
nearestn <- get.knnx(data=bg,query=X,k=1,algorithm="kd_tree")
for(i in 1:nrow(X)){
  lines(rbind(X[i,], bg[nearestn$nn.index[i],]), col="#2491B2",lwd=2)
}


-tgs



Thomas G. Stewart <http://www.bios.unc.edu/~tgs>


On Thu, Nov 21, 2013 at 7:47 AM, Gonçalo Ferraz <gferraz29@gmail.com>
wrote:
> Hi, I have a cloud of randomly distributed points in 2-dimensional space
> and want to set up a grid, with a given grid-cell size, that minimizes the
> distance between my points and the grid nodes. Does anyone know of an R
> function or toolbox that somehow addresses this problem? This is a problem
> of optimizing the location of the grid, not a problem of deciding what
> should be the grid-cell size, because size is already given. Thank you.
> Gonçalo
> ______________________________________________
> R-help@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.
>
	[[alternative HTML version deleted]]