R Graphical Manual

Browse All

Last data update: 2014.03.03

R: Get Convex Hull of Points

getConvexHull

R Documentation

Get Convex Hull of Points

Description

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.

Usage

getConvexHull(x, y, includeColinear = FALSE)

Arguments

`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.

Value

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.

References

https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Examples

#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()