[R] Greedy triangulation

[Dan Bebber]

Thanks, but no, the Delaunay is different.

I have written the following, which interested persons might want to check 
for accuracy and streamlining:

#GREEDY TRIANGULATION
#
#Pick all lines that are shortest and don't overlap, starting with shortest.
#
greedy<-function(xy){   #input is a matrix with 2 columns (x,y)
require(spatstat)   #need the crossing.psp function
w<-owin(range(xy[,1]),range(xy[,2]))    #set the window for crossing.psp
dists<-dist(xy) #calculate Euclidean distances for each line
ind<-which(lower.tri(dists),arr.ind=T)  #matrix with 2 columns (start point, 
end point)
x1<-xy[ind[,1],1]   #x of start point
y1<-xy[ind[,1],2]   #y of start point
x2<-xy[ind[,2],1]   #x of end point
y2<-xy[ind[,2],2]   #y of end point
dat<-data.frame(strt=ind[,1],fin=ind[,2],
x1=x1,y1=y1,x2=x2,y2=y2,len=as.vector(dists))#put all data for lines 
together
dat<-dat[order(dists),] #order data by line length, shortest first
inc<-dat[1,]    #include the shortest line in the triangulation
dat<-dat[-1,]   #keep remaining lines
while(nrow(dat)>0){ #while lines remain to be tested, do the following...
A<-psp(inc$x1,inc$y1,inc$x2,inc$y2,w) #create the psp object for the lines 
already included
B<-psp(dat$x1[1],dat$y1[1],dat$x2[1],dat$y2[1],w) #create the psp object for 
the next line to be tested
cross<-crossing.psp(A,B) #check for crossing of the test line over the lines 
already included
p.match<-sum(cross$x%in%c(inc$x1,inc$x2)) #check if the crossing occurs 
because same points are included
if(cross$n-p.match==0){inc[nrow(inc)+1,]<-dat[1,]} #if the only crossing are 
due to shared points, include the line
dat<-dat[-1,]}  #remove the line from the untested lines
return(inc)} #when all lines have been tested, return all included lines
#
#Plot the greedy triangulation
#
plot.greedy<-function(xy,gr,...){
plot(xy,asp=1,xlab="x",ylab="y",...)
segments(gr$x1,gr$y1,gr$x2,gr$y2)}
#
#Test it
#
xy<-matrix(runif(40,0,1),nc=2)
gr<-greedy(xy)
plot.greedy(xy,gr,main="Greedy Triangulation")
#END

----- Original Message ----- 
From: "Greg Snow" <Greg.Snow at intermountainmail.org>
To: "Dan Bebber" <dan.bebber at plants.ox.ac.uk>; <r-help at stat.math.ethz.ch>
Sent: Thursday, September 14, 2006 4:32 PM
Subject: RE: [R] Greedy triangulation


Does the deldir package do what you want?


-- 
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.snow at intermountainmail.org
(801) 408-8111