# [SciPy-User] 3d convex hull

Ning Guo hhh.guo@gmail....
Sat Aug 27 10:12:24 CDT 2011

```On Saturday, August 27, 2011 03:53 PM, Pauli Virtanen wrote:

Thanks Pauli!
You pointed out how to calculate the normals and areas using cross
product. It's really smart and I will use this method if the Delaunay
function cannot provide results directly.

Also, the formula to calculate normal may be like this:

face_normals[:,0] = np.cross(tetra_points[:,0]-tetra_points[:,2],tetra_points[:,1]-tetra_points[:,2])  // facet 0-1-2
face_normals[:,1] = np.cross(tetra_points[:,0]-tetra_points[:,3],tetra_points[:,2]-tetra_points[:,3])  // facet 0-2-3
face_normals[:,2] = np.cross(tetra_points[:,0]-tetra_points[:,1],tetra_points[:,3]-tetra_points[:,1])  // facet 0-3-1
face_normals[:,3] = np.cross(tetra_points[:,1]-tetra_points[:,3],tetra_points[:,2]-tetra_points[:,3])  // facet 1-2-3

Regarding to the order of the vertices, I'm also not sure about their
convention. I'm trying to figure it out.

Best regards!
Ning

> Wed, 24 Aug 2011 23:56:36 +0800, Ning Guo wrote:
>> I also want to try Delaunay function. But I cannot get enough info from
>> the documentation. I want to output the Delaunay tetrahedral in 3D and
>> need the vertex indices, facet areas and normals. How can I use the
>> function in scipy.spatial? Now I have all the points with id and
>> position.
> Suppose you have 20 points in 3-D:
>
>      import numpy as np
>      import scipy.spatial
>
>      points = np.random.rand(20, 3)
>      tri = scipy.spatial.Delaunay(points)
>
> The indices of the vertices of tetrahedron number `j` are
> in `tri.vertices[j]`. The facet areas and normals can be computed
> for each tetrahedron via vector cross products:
>
>      tetra_points = tri.points[tri.vertices] # (N, 4, 3) array
>
>      face_normals = np.empty_like(tetra_points)
>      face_normals[:,0] = np.cross(tetra_points[:,0], tetra_points[:,1])
>      face_normals[:,1] = np.cross(tetra_points[:,0], tetra_points[:,2])
>      face_normals[:,2] = np.cross(tetra_points[:,0], tetra_points[:,3])
>      face_normals[:,3] = np.cross(tetra_points[:,1], tetra_points[:,2])
>
>      face_normal_lengths = np.sqrt(np.sum(face_normals**2, axis=2))
>
>      face_normals /= face_normal_lengths[:,:,np.newaxis]
>      face_areas = 0.5 * face_normal_lengths
>
> One important point I don't know at the moment is if those normals
> actually point away from the center of the tetrahedra. You'd have
> to check the Qhull documentation to check whether they have a winding
> convention that guarantees certain ordering of the vertices of
> the simplices.
>
> (Note: the above is untested code, so check it works first :)
>

--
Geotechnical Group
Department of Civil and Environmental Engineering
Hong Kong University of Science and Technology
Clear Water Bay, Kowloon, Hong Kong

```