[R] Delaunay Graph, once again

[Rolf Turner]

You are almost surely being bitten by the issue about which you 
previously made inquiries to me, concerning the delaunayn() function 
from the "geometry" package.  (NOTE: ***PACKAGE***!!!  Not "library".  A 
library is a *collection* of packages.) The delaunayn()
function also uses the qhull algorithm.  By default it treats some 
triples of *collinear* points as triangles.  This is probably causing 
the discrepancy between the results.

Ergo it would seem best to use deldir() unless you *really want* 
collinear triples to be considered as triangles --- and I can't see why 
you would.

Your code for calculating the adjacency list is correct. (Except for the 
fact that you put in unnecessary semi-colons --- this is R, not C --- 
and for the fact that a comment runs over into the next line, causing an 
error to be thrown when one tries to copy and paste your code.)

Try a toy example:

require(deldir)
set.seed(42)
x <- runif(6)
y <- runif(6)
dxy <- deldir(x,y)
ind <- dxy$dirsgs[,5:6]
adj <- matrix(0, length(x), length(y))
for (i in 1:nrow(ind)){
    adj[ind[i,1], ind[i,2]] <- 1
    adj[ind[i,2], ind[i,1]] <- 1
}
adj
      [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    1    0    1    0    1
[2,]    1    0    1    1    1    0
[3,]    0    1    0    0    1    1
[4,]    1    1    0    0    1    1
[5,]    0    1    1    1    0    1
[6,]    1    0    1    1    1    0
ind
    ind1 ind2
1     2    1
2     3    2
3     4    1
4     4    2
5     5    2
6     5    3
7     5    4
8     6    1
9     6    3
10    6    4
11    6    5

This looks right.

I'm not a Matlab user so I can't check what Matlab would give, but I'm 
pretty sure the results would be the same in this toy example where 
there are no collinear triples.

cheers,

Rolf Turner

On 21/06/14 03:17, Raphael Päbst wrote:
> Hello again,
> After playing around with my current problem for some time, I have
> once again returned to Delaunay Graphs and after banging my head
> against the problem for some time I fear that I can't see the issue
> clearly anymore and want to ask for some outside comments, to maybe
> shake my thoughts loose again.
>
> So, let me explain my project and then my problem:
>   I have a set of points, given as x- and y-coordinates and want to
> create the adjacency matrix of the corresponding Delaunay Graph. I
> have already removed duplicates in my set of points and to calculate
> the matrix, I have hit upon the following procedure, which might not
> be the most efficient, but I'm aiming for correct results and
> simplicty first, before I can think about efficiency.
>
> # x a vector of length n, containing the x-coordinates of my n points
> #y: the same for the y-coordinates
> library(deldir)
> del <- deldir(x, y) # calculating the tesselation
> dels <- del$delsgs[,5:6] # giving me a data.frame with 2 columns,
> containing the indices of points connected by an edge in the Delaunay
> Graph
>
> adj <- matrix(0, length(x), length(y)) # creating the empty adjacency matrix
>
> for (i in 1:nrow(dels)){ # going through the rows of dels
> adj[dels[i,1], dels[i,2]] <- 1; # since the points in a row of dels
> are connected, the matrix at that point is set to 1
> adj[dels[i,2], dels[i,1]] <- 1; # and this makes it symmetric
> }
>
> Now as I see it this should give me the adjacency matrix, right?
>
> So let's come to my problem: The program I'm writing is a translation
> of some Matlab-Code and so the results of both versions should be the
> same, if at all possible. My adjacency matrix created in the above
> mentioned manner however is not the same as the one created with
> Matlab. The Matlab-Version uses algorithms based on Qhull, while I use
> deldir as a library, could this account for the difference or have I
> fundamentally misunderstood some part of the whole plan?
>
> I hope the information is helpful and would very much appreciate any
> pointers and thoughts on the matter.