# [Numpy-discussion] doing zillions of 3x3 determinants fast

Dan Lenski Daniel.Lenski@seagate....
Mon Aug 25 09:59:01 CDT 2008

```On Sun, 24 Aug 2008 23:49:45 -0600, Charles R Harris wrote:

> On Sun, Aug 24, 2008 at 9:48 PM, Daniel Lenski <dlenski@gmail.com>
> wrote:
>
>> Hi all,
>> I need to take the determinants of a large number of 3x3 matrices, in
>> order to determine for each of N points, in which of M tetrahedral
>> cells they lie.  I arrange the matrices in an ndarray of shape
>> (N,M,5,3,3).
>>
>>
> If you step back a bit and describe the actual problem you have, rather
> than your current solution, it might be that there are algorithms in
> scipy to solve it.
>

Hi Charles,
I have an irregular/unstructured mesh of tetrahedral cells, and I need to
interpolate some data over this mesh, at arbitrary points within the
complete volume.

So this is basically 3D interpolation.  I've done some looking into this
already, and it seems that the only facility for 3D interpolation in
Scipy is map_coordinates, which only works on a regular grid.

So I have to roll my own interpolation!  I start by trying to figure out
in which of the tetrahedral cells each interpolation point lies.  The
standard way to do this is to check that for every three vertices of each
tetrahedron (v1,v2,v3), the point in question lies on the same side as
the fourth point (v4).  This can be checked with:

| v1x-x    v1y-y   v1z-z |     | v1x-v4x    v1y-v4y   v1z-v4z |
| v2x-x    v2y-y   v2z-z |  =  | v2x-v4x    v2y-v4y   v2z-v4z |
| v3x-x    v3y-y   v3z-z |     | v3x-v4x    v3y-v4y   v3z-v4z |

(Here's a description of a nearly identical algorithm: http://
steve.hollasch.net/cgindex/geometry/ptintet.html)

Dan

```