Python convex hull with scipy.spatial.Delaunay, how to eleminate points inside the hull?

adrienlucca.wordpress.com picture adrienlucca.wordpress.com · Feb 12, 2014 · Viewed 12.5k times · Source

I have a list of 3D points in a np.array called pointsList, values are float :

[[1., 2., 10.],
 [2., 0., 1.],
 [3., 6., 9.],
 [1., 1., 1.],
 [2., 2., 2.],
 [10., 0., 10.],
 [0., 10., 5.],
... etc.

This code makes a Delaunay triangulation of the cloud of points:

import numpy as np
import scipy.spatial 

tri = scipy.spatial.Delaunay(pointsList) 
# Delaunay triangulation

indices = tri.simplices
# indices of vertices

vertices = points[indices]
# the vertices for each tetrahedron

However, before that triangulation step, I'd like to remove from my list all the points that are inside of the convex hull

A solution would be to create a new np.array named shortlist, and store them there.

But what function in scipy (or any other solution), will do that?

How can I program this operation?

Thank you

Answer

embert picture embert · Feb 12, 2014

The convex hull is a subgraph of the Delaunay triangulation.

So you might just use scipy.spatial.ConvexHull(), e. g.

from scipy.spatial import ConvexHull
cv = ConvexHull(pointList)

hull_points = cv.vertices
# the vertices of the convex hull

set(range(len(pointList))).difference(ch.vertices)
# the vertices inside the convex hull

Comparison scipy.spatial.Delaunay and scipy.spatial.ConvexHull (2D)

enter image description here