Numpy unique triangles in mesh

Question

I have a mesh of triangles stored in numpy. Some triangles are duplicates and I want to remove them. An example of my numpy array:

# Some points
a=(-2,-2,0)
b=(1,-2,0)
c=(1, 1,0)
d=(-2,1,0)
e=(-2,-2,1)
f=(1,-2,1)
g=(1,1,1)
h=(-2,1,1)

# Some triangles
t1=(a,b,c)
t2=(c,d,a)
t3=(e,f,g)
t4=(g,h,e)

# The numpy array with duplicated t1 and t3
points=numpy.array([t1,t2,t3,t4,t1,t3])

I tried using intersect1d and unique but could not figure out a way to remove all triangles which occure more than once. What am I missing?

You have `a == c` and `e == g`, so for all your triangles, the first and last point are the same, making them just lines. — Feodoran, Aug 24 '18 at 15:22
Ah that was a mistake in my example coordinates. They are meant to be real triangles. I edited the coordinates to reflect this. Thx for pointing this out. — Nard, Aug 24 '18 at 17:10
Does the order of the vertices matter? For example, in some code I wrote before the normal to the triangle was represented by using the right hand rule around the triangle. Does that matter here or you don't care about the order of the vertices? — user545424, Aug 24 '18 at 17:15
In `points`, the triangles 'loose' their identity. We can only identify duplicates by checking for matching values of the (3,3) elements. A list of those triangles will contain pointers to `t1`, `t2` etc., each with a unique `id`. And since they are tuples you can use `set`. What exactly is that makes one triangle a duplicate of another? — hpaulj, Aug 24 '18 at 18:30

score 1 · Accepted Answer · edited Sep 08 '20 at 18:52

This exact problem was the first motivator that lead me to create the numpy_indexed package:

import numpy_indexed as npi
npi.unique(triangles)

It has grown to cover a lot more things since then. But also, since then numpy has added an axis argument to unique

np.unique(triangles, axis=0)

Should accomplish the same thing, with basically the same underlying operations being performed. npi.unique also has an axis argument, but its 0 by default.

xdze2 · Answer 2 · 2018-08-24T18:04:12.113

A solution is to build a set of the triangles, and to do that the points of each triangle have to be sorted first:

# Some points
a=(-2,-2,0)
b=(1,-2,0)
c=(1, 1,0)
d=(-2,1,0)
e=(-2,-2,1)
f=(1,-2,1)
g=(1,1,1)
h=(-2,1,1)

# Some triangles
t1=(a,b,c)
t2=(c,d,a)
t3=(e,f,g)
t4=(g,h,e)

# The numpy array with duplicated t1 and t3
triangles = [t1,t2,t3,t4,t1,t3]

set( tuple(sorted(points)) for points in triangles )

gives:

{((-2, -2, 0), (-2, 1, 0), (1, 1, 0)),
 ((-2, -2, 0), (1, -2, 0), (1, 1, 0)),
 ((-2, -2, 1), (-2, 1, 1), (1, 1, 1)),
 ((-2, -2, 1), (1, -2, 1), (1, 1, 1))}

user545424 · Answer 3 · 2018-08-24T17:34:32.640

Supposing the order of the vertices doesn't matter you can first sort the vertices and then remove duplicate triangles by using a similar technique as here: Removing duplicate columns and rows from a NumPy 2D array

def unique_triangles(points):
    points = np.sort(points,axis=1)
    unique_points = np.unique(points.flatten().view([('',points.dtype)]*points.shape[1]*points.shape[2]))
    return unique_points.view(points.dtype).reshape((-1,points.shape[1],points.shape[2]))

Example:

>>> unique_triangles(points)
array([[[-2, -2,  0],
        [ 1, -2,  0],
        [ 1,  1,  0]],

       [[-2, -2,  1],
        [ 1, -2,  1],
        [ 1,  1,  1]],

       [[ 1,  1,  0],
        [-2,  1,  0],
        [-2, -2,  0]],

       [[ 1,  1,  1],
        [-2,  1,  1],
        [-2, -2,  1]]])

Numpy unique triangles in mesh

3 Answers3