node package manager

convex-hull

convex-hull

This module is a wrapper over various convex hull modules which exposes a simple interface for computing convex hulls of point sets in any dimension.

Example

var ch = require('convex-hull')
 
var points = [
  [0,0],
  [1,0],
  [0,1],
  [0.15,0.15],
  [0.5, 0.5]
]
 
 
//Picture: 
// 
// [0,1] * 
//       |\ 
//       | \ 
//       |  \ 
//       |   \ 
//       |    \ 
//       |     \ 
//       |      \ 
//       |       * [0.5,0.5] 
//       |        \ 
//       |         \ 
//       |          \ 
//       |           \ 
//       |            \ 
//       |    *        \ 
//       | [0.15,0.15]  \ 
// [0,0] *---------------* [1,0] 
// 
 
console.log(ch(points))

Output:

[[0, 1], [1, 2], [2, 0]]

Install

npm install convex-hull

If you want to use it in a webpage, use browserify.

API

require('convex-hull')(points)

Computes the convex hull of points

  • points is an array of points encoded as d length arrays

Returns A polytope encoding the convex hull of the point set.

Time complexity The procedure takes O(n^floor(d/2) + n log(n)) time.

Note This module is a wrapper over incremental-convex-hull and monotone-convex-hull for convenience. It will select an optimal algorithm for whichever dimension is appropriate.

Credits

(c) 2014 Mikola Lysenko. MIT License

Use this within your firewall

Combine open-source packages with your private code and publish to a private registry behind the firewall. npm ♥ enterprise developers

how? learn more

Collaborators list

Stats

Try it out

Keywords

convex, hull, any, dimension

Dependencies (3)

affine-hull, incremental-convex-hull, monotone-convex-hull-2d

Dependents (10)

ambisonics, plotly.js, convexed, weighted-delaunay, full-convex-hull, marching-simplex-table, mikolalysenko-hoarders, craftml, turf-convex, @turf/convex