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
First, obtain the convex hull for your point cloud. Then loop over all of the edges of the convex hull in counter-clockwise order. For each of the edges, check whether your target point lies to the "left" of that edge. When doing this, treat the edges as vectors pointing counter-clockwise around the convex hull.
An intuitve definition is to pound nails at every point in the set S and then stretch a rubber band around the outside of these nails - the resulting image of the rubber band forms a polygonal shape called the Convex Hull.
scipy. spatial can compute triangulations, Voronoi diagrams, and convex hulls of a set of points, by leveraging the Qhull library. Moreover, it contains KDTree implementations for nearest-neighbor point queries, and utilities for distance computations in various metrics.
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With