[R] Delaunay Graph, once again

[Raphael Päbst]

I have the same suspicion, unfortunately I am no Matlab-User either
and only have a adjacency-matrix created by the corresponding matlab
functions to compare with my own output. So, even though I don't see
any use for collinear triples either, is there a way to get them with
deldir as well?

All the best!

Raphael

On 6/21/14, Rolf Turner <r.turner at auckland.ac.nz> wrote:
>
> 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.
>
>