funsIndDelTri {pcds}

Functions provide the indices of the Delaunay triangles where the points reside

Description

Two functions: index.delaunay.tri and indices.delaunay.tri.

index.delaunay.tri finds the index of the Delaunay triangle in which the given point, p, resides.

indices.delaunay.tri finds the indices of triangles for all the points in data set, Xp, as a vector.

Delaunay triangulation is based on Yp and DTmesh are the Delaunay triangles with default NULL. The function returns NA for a point not inside the convex hull of Yp. Number of Yp points (i.e., size of Yp) should be at least three and the points should be in general position so that Delaunay triangulation is (uniquely) defined.

If the number of Yp points is 3, then there is only one Delaunay triangle and the indices of all the points inside this triangle are all 1.

See (Okabe et al. (2000); Ceyhan (2010); Sinclair (2016)) for more on Delaunay triangulation and the corresponding algorithm.

Usage

index.delaunay.tri(p, Yp, DTmesh = NULL)

indices.delaunay.tri(Xp, Yp, DTmesh = NULL)

Arguments

p

A 2D point; the index of the Delaunay triangle in which p resides is to be determined. It is an argument for index.delaunay.tri.

Yp

A set of 2D points from which Delaunay triangulation is constructed.

DTmesh

Delaunay triangles based on Yp, default is NULL, which is computed via tri.mesh function in interp package. triangles function yields a triangulation data structure from the triangulation object created by tri.mesh.

Xp

A set of 2D points representing the set of data points for which the indices of the Delaunay triangles they reside is to be determined. It is an argument for indices.delaunay.tri.

Value

index.delaunay.tri returns the index of the Delaunay triangle in which the given point, p, resides and indices.delaunay.tri returns the vector of indices of the Delaunay triangles in which points in the data set, Xp, reside.

Author(s)

Elvan Ceyhan

References

Ceyhan E (2010). “Extension of One-Dimensional Proximity Regions to Higher Dimensions.” Computational Geometry: Theory and Applications, 43(9), 721-748.

Okabe A, Boots B, Sugihara K, Chiu SN (2000). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, New York.

Sinclair D (2016). “S-hull: a fast radial sweep-hull routine for Delaunay triangulation.” 1604.01428.

Examples

#Examples for index.delaunay.tri
nx<-20 #number of X points (target)
ny<-5 #number of Y points (nontarget)
set.seed(1)
Yp<-cbind(runif(ny),runif(ny))

Xp<-runif.multi.tri(nx,Yp)$g #data under CSR in the convex hull of Ypoints
#try also Xp<-cbind(runif(nx),runif(nx))

index.delaunay.tri(Xp[10,],Yp)

#or use
DTY<-interp::tri.mesh(Yp[,1],Yp[,2],duplicate="remove")
#Delaunay triangulation
TRY<-interp::triangles(DTY)[,1:3];
index.delaunay.tri(Xp[10,],Yp,DTY)

ind.DT<-vector()
for (i in 1:nx)
 ind.DT<-c(ind.DT,index.delaunay.tri(Xp[i,],Yp))
ind.DT

Xlim<-range(Yp[,1],Xp[,1])
Ylim<-range(Yp[,2],Xp[,2])
xd<-Xlim[2]-Xlim[1]
yd<-Ylim[2]-Ylim[1]

DTY<-interp::tri.mesh(Yp[,1],Yp[,2],duplicate="remove")
#Delaunay triangulation based on Y points

#plot of the data in the convex hull of Y points together with the Delaunay triangulation
plot(Xp,main=" ", xlab=" ", ylab=" ",xlim=Xlim+xd*c(-.05,.05),ylim=Ylim+yd*c(-.05,.05),type="n")
interp::plot.triSht(DTY, add=TRUE, do.points = TRUE,pch=16,col="blue")
points(Xp,pch=".",cex=3)
text(Xp,labels = factor(ind.DT))



#Examples for indices.delaunay.tri
#nx is number of X points (target) and ny is number of Y points (nontarget)
nx<-20; ny<-4;  #try also nx<-40; ny<-10 or nx<-1000; ny<-10;

set.seed(1)
Yp<-cbind(runif(ny),runif(ny))
Xp<-runif.multi.tri(nx,Yp)$g #data under CSR in the convex hull of Ypoints
#try also Xp<-cbind(runif(nx),runif(nx))

tr.ind<-indices.delaunay.tri(Xp,Yp)  #indices of the Delaunay triangles
tr.ind

#or use
DTY<-interp::tri.mesh(Yp[,1],Yp[,2],duplicate="remove")
#Delaunay triangulation based on Y points
tr.ind<-indices.delaunay.tri(Xp,Yp,DTY)  #indices of the Delaunay triangles
tr.ind

Xlim<-range(Yp[,1],Xp[,1])
Ylim<-range(Yp[,2],Xp[,2])
xd<-Xlim[2]-Xlim[1]
yd<-Ylim[2]-Ylim[1]

#plot of the data in the convex hull of Y points together with the Delaunay triangulation

oldpar <- par(pty = "s")
plot(Xp,main=" ", xlab=" ", ylab=" ",xlim=Xlim+xd*c(-.05,.05),ylim=Ylim+yd*c(-.05,.05),pch=".")
interp::plot.triSht(DTY, add=TRUE, do.points = TRUE,pch=16,col="blue")
text(Xp,labels = factor(tr.ind))
par(oldpar)