How to extract distances from delaunay triangulation to list object in R

Question

Suppose I have coordinates of points, each with ID. How sdhould I extract distances from delaunay triangulation to list object in R?

# My data are similar to this structure
id <- c("A","B","C","D","E","F","G","H","I","J","K","L","M","N")
x_coor <- c(0.5,1,1,1.5,2,3,3,3.5,4,4.5,5,5,6,7)
y_coor <- c(5.5,3,7,6.5,5,3.5,3,1.5,1,2.5,4,5,3.5,5.5)
my.data <- data.frame(id = id, x_coor = x_coor, y_coor = y_coor)

# When I perform Delaunay triangulation, I can see the distances....
library(tripack)
my.triangles<-tri.mesh(my.data$x_coor, my.data$y_coor)
plot(my.triangles, do.points=FALSE, lwd=0.2)
points(my.data$x, my.data$y, col = "black", pch=20, cex = 1.5)
text(my.data$x, my.data$y, labels = my.data$id)

How can I extract "pairs" of points to list object like this?

# I need something like this...
my.list
[[A]]
[1] 2.55  1.58  1.41  1.58 (all distances connected to "A")
[[B]]
[1] 2.55  2.24  2.06  2.00  2.92  3.61 (all distances connected to "B")
etc.

Answer 1

Beginning at tri.mesh() we have:

my_triangles <- tri.mesh(my.data$x_coor, my.data$y_coor)
plot(my_triangles, do.points=FALSE, lwd=0.2)

From str(my_triangles) and the R documentation on ?neighbours we can proceed by extracting neighbours for each point as follows:

neiblist <- neighbours(my_triangles)

And then appending the point IDs from the original dataframe so that you almost have the list you want, except it contains neighbour IDs and not distances:

names(neiblist) <- my.data$id         #append names for later reference

Then compute a euclidean distance matrix with all the points:

euc_dist <- as.matrix(dist(cbind(x=my_triangles$x, y=my_triangles$y)))

#Append dimnames for reference

colnames(euc_dist) <- my.data$id
rownames(euc_dist) <- my.data$id

Find maximum neighbours a point could have: Needed for memory preallocation.

max_n <- max(unlist(lapply(neiblist, length)))
npoints <- length(my.data$id)                 # This is just the total number of points

Preallocate memory in which to collect results, Important for computational efficiency and speed:

dist_2neigh_mat <- matrix(nrow=npoints, ncol=max_n)    #Create results matrix

rownames(dist_2neigh_mat) <- my.data$id
colnames(dist_2neigh_mat) <- colnames(data.frame(dist=matrix(data=1:6, nrow=1)))

Get and collect distance vectors for all points.

for (i in my.data$id){
neighbors_i <- neiblist[[i]]
dist2neighbours_i <- euc_dist[,i][neighbors_i]

#Append vector with NAs to match ncol of results matrix

dist2neighbours_i <- c(dist2neighbours_i, rep(NA, 
times=(max_n-length(dist2neighbours_i))))

dist_2neigh_mat[i,] <- dist2neighbours_i   #Update results matrix with i'th distances
}

The dist_2neigh_mat contains your results. If you insist on having your results in a list exactly as stated in your question, then you just need to convert the results matrix to such a list as follows:

results_list <- as.list(data.frame(t(dist_2neigh_mat)))

You can then get rid of the NA's generated earlier for matrix integrity reasons with:

#Function to remove NA's

fun_NA <- function(x){x=x[!is.na(x)]
return(x)}

Remove NA's from results

results_list <- lapply(results_list, FUN=fun_NA)  

My thinking is that this would be very very speedy even with lots and lots of points..but someone might know differently :-)

Cheers.