[R] Delaunay Graph, once again
Rolf Turner
r.turner at auckland.ac.nz
Sat Jun 21 01:18:12 CEST 2014
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.
More information about the R-help
mailing list