tsearch {geometry}

Search for the enclosing Delaunay convex hull

Description

For t <- delaunay(cbind(x, y)), where (x, y) is a 2D set of points, tsearch(x, y, t, xi, yi) finds the index in t containing the points (xi, yi). For points outside the convex hull the index is NA.

Usage

tsearch(x, y, t, xi, yi, bary = FALSE, method = "quadtree")

Arguments

x

X-coordinates of triangulation points

y

Y-coordinates of triangulation points

t

Triangulation, e.g. produced by t <- delaunayn(cbind(x, y))

xi

X-coordinates of points to test

yi

Y-coordinates of points to test

bary

If TRUE return barycentric coordinates as well as index of triangle.

method

One of "quadtree" or "orig". The Quadtree algorithm is much faster and new from version 0.4.0. The orig option uses the tsearch algorithm adapted from Octave code. Its use is deprecated and it may be removed from a future version of the package.

Value

If bary is FALSE, the index in t containing the points (xi, yi). For points outside the convex hull the index is NA. If bary is TRUE, a list containing:

list("idx")

the index in t containing the points (xi, yi)

list("p")

a 3-column matrix containing the barycentric coordinates with respect to the enclosing triangle of each point (xi, yi).

Note

The original Octave function is Copyright (C) 2007-2012 David Bateman

Author(s)

Jean-Romain Roussel (Quadtree algorithm), David Sterratt (Octave-based implementation)

See Also

tsearchn, delaunayn