getConvexHull {contoureR} | R Documentation |
Returns the sequence of indexes within the supplied numeric vectors x
and y
, that describe the convex
hull containing those points. This is a (slightly modified) implementation of the Andrews Monotone Chain, which is
a well known algorithm that is able to solve the convex hull with O(nlogn)
complexity.
Typical computation time on a Macbook Air, 1.7Ghz I7, 8Gb Ram, using random points in the range [0,1]:
100K points 0.03 Seconds
1M points 0.3 seconds, and
10M points3.3 seconds.
getConvexHull(x, y, includeColinear = FALSE)
x |
numeric vector of x values |
y |
numeric vector of y values of same length as x |
includeColinear |
keep or discard the points that lie ON the hull, default is to discard (ie dont keep colinear points), as this is the true definition of the convex hull. |
Returns a vector of integers that represent the '1-based' indexes of the points relative to the
x
and y
input arguments. The resulting vector represents the closed list, meaning that the
first index and the last index in the series will be the same.
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
#Generate the Convex Hull of a Series of Points set.seed(1) x = runif(100) y = runif(100) ch = getConvexHull(x,y) #To demonstrate, Lets view the hull library(ggplot2) df = data.frame(x,y) ggplot(data=df,aes(x,y)) + geom_path(data=df[ch,]) + geom_point()