A robust quickhull implementation to find the convex hull of a set of 3d points in O(n log n)
ported from John Lloyd implementation
Additional implementation material:
 Dirk Gregorius presentation: https://archive.org/details/GDC2014Gregorius
 Convex Hull Generation with Quick Hull by Randy Gaul (lost link)
This library was incorporated into ThreeJS!. Thanks to https://github.com/Mugen87 for his work to move the primitives to ThreeJS primitives, the quickhull3d library will always be library agnostic and will operate with raw arrays.
 Key functions are well documented (including ascii graphics)
 Faster than other JavaScript implementations of convex hull
Click on the image to see a demo!
<script type="module">
import qh from 'https://cdn.jsdelivr.net/npm/quickhull3d@<version>/+esm'
const points = [
[0, 1, 0],
[1, 1, 1],
[1, 1, 1],
[0, 1, 1]
]
const faces = qh(points)
console.log(faces)
// output:
// [ [ 2, 1, 0 ], [ 3, 1, 2 ], [ 3, 0, 1 ], [ 3, 2, 0 ] ]
// 1st face:
// points[2] = [1, 1, 1]
// points[1] = [1, 1, 1]
// points[0] = [0, 1, 0]
// normal = (points[1]  points[2]) x (points[0]  points[2])
</script>
$ npm install save quickhull3d
import qh from 'quickhull3d'
params

points
{Array<Array>} an array of 3d points whose convex hull needs to be computed 
options
{Object} (optional) 
options.skipTriangulation
{Boolean} True to skip the triangulation of the faces (returning nvertex faces)
returns An array of 3 element arrays, each subarray has the indices of 3 points which form a face whose normal points outside the polyhedra
params

point
{Array} The point that we want to check that it's a convex hull. 
points
{Array<Array>} The array of 3d points whose convex hull was computed 
faces
{Array<Array>} An array of 3 element arrays, each subarray has the indices of 3 points which form a face whose normal points outside the polyhedra
returns true
if the point point
is inside the convex hull
example
import qh, { isPointInsideHull } from 'quickhull3d'
const points = [
[0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1],
[1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1]
]
const faces = qh(points)
expect(isPointInsideHull([0.5, 0.5, 0.5], points, faces)).toBe(true)
expect(isPointInsideHull([0, 0, 0.1], points, faces)).toBe(false)
import QuickHull from 'quickhull3d/dist/QuickHull'
params

points
{Array} an array of 3d points whose convex hull needs to be computed
Computes the quickhull of all the points stored in the instance
time complexity O(n log n)
params

skipTriangulation
{Boolean} (default: false) True to skip the triangulation and return nvertices faces
returns
An array of 3element arrays (or nelement arrays if skipTriangulation = true
)
which are the faces of the convex hull
import qh from 'quickhull3d'
const points = [
[0, 1, 0],
[1, 1, 1],
[1, 1, 1],
[0, 1, 1]
]
qh(points)
// output:
// [ [ 2, 0, 3 ], [ 0, 1, 3 ], [ 2, 1, 0 ], [ 2, 3, 1 ] ]
// 1st face:
// points[2] = [1, 1, 1]
// points[0] = [0, 1, 0]
// points[3] = [0, 1, 1]
// normal = (points[0]  points[2]) x (points[3]  points[2])
Using the constructor:
import { QuickHull } from 'quickhull3d'
const points = [
[0, 1, 0],
[1, 1, 1],
[1, 1, 1],
[0, 1, 1]
];
const instance = new QuickHull(points)
instance.build()
instance.collectFaces() // returns an array of 3element arrays
Specs:
MacBook Pro (Retina, Mid 2012)
2.3 GHz Intel Core i7
8 GB 1600 MHz DDR3
NVIDIA GeForce GT 650M 1024 MB
Versus convexhull
// LEGEND: program:numberOfPoints
quickhull3d:100 x 6,212 ops/sec 1.24% (92 runs sampled)
convexhull:100 x 2,507 ops/sec 1.20% (89 runs sampled)
quickhull3d:1000 x 1,171 ops/sec 0.93% (97 runs sampled)
convexhull:1000 x 361 ops/sec 1.38% (88 runs sampled)
quickhull3d:10000 x 190 ops/sec 1.33% (87 runs sampled)
convexhull:10000 x 32.04 ops/sec 2.37% (56 runs sampled)
quickhull3d:100000 x 11.90 ops/sec 6.34% (34 runs sampled)
convexhull:100000 x 2.81 ops/sec 2.17% (11 runs sampled)
quickhull3d:200000 x 5.11 ops/sec 10.05% (18 runs sampled)
convexhull:200000 x 1.23 ops/sec 3.33% (8 runs sampled)
Mauricio Poppe. Licensed under the MIT license.