getConvexHull {contoureR} 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()
```

[Package contoureR version 1.0.5 Index]