# getConvexHull: Get Convex Hull of Points In contoureR: Contouring of Non-Regular Three-Dimensional Data

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

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

 ``` 1 2 3 4 5 6 7 8 9 10 11 12``` ```#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() ```

### Example output

```Loading required package: geometry