Points in a Triangle Numpy

Question

Im trying to build a program which can increase the number of points on a triangle(there are millions of triangles whose resolution are to be increased). this is the code i came up so far. with the help from hpaulj and aerobiomat in q2 and q1There is a lot of performance improvement.

array([[[405.84, 805.62, 345.14],
        [406.78, 805.73, 314.15],
        [407.57, 805.83, 314.19]],

       [[407.57, 805.83, 314.19],
        [406.78, 805.73, 314.15],
        [407.9 , 805.19, 309.75]],

       [[407.9 , 805.19, 309.75],
        [406.78, 805.73, 314.15],
        [407.11, 805.09, 309.7 ]]])

def normal(triangles):
    return np.cross(triangles[:,1] - triangles[:,0], 
                    triangles[:,2] - triangles[:,0], axis=1)

def area(triangles):
    return np.linalg.norm(normal(triangles), axis=1) / 2

def plane(triangles):
    n = normal(triangles)
    u = n / np.linalg.norm(n, axis=1, keepdims=True)
    d = -np.einsum('ij,ij->i', triangles[:, 0], u)
    return np.hstack((u, d[:, None]))

def mincoords(triangles):
    return np.array(np.amin(Vertex_combined[:,:,:],axis=1))

def maxcoords(triangles):
    return np.array(np.amax(Vertex_combined[:,:,:],axis=1))

normals=normal(Vertex_combined)
areas=area(Vertex_combined)
planes=plane(Vertex_combined)
mins=mincoords(Vertex_combined)
maxs=maxcoords(Vertex_combined)

alist=[np.mgrid[mins[i,0]:maxs[i,0]:0.5,mins[i,1]:maxs[i,1]:0.5] for i in range(len(mins)-1)]

blist =[x.reshape(2, -1).T for x in alist]

temp=[-np.round_(((planes[i][0]*np.array(blist[i])[:,0]+planes[i][1]*np.array(blist[i])[:,1]+planes[i][3])/planes[i][2]),2) for i in range(len(planes)-1)]

points=[np.hstack((np.array(blist[i]),np.atleast_2d(temp[i]).swapaxes(0,1))) for i in range(len(temp)-1)]

validpoints=[]

it is pretty efficient till this point

ABC be a triangle and D is a point we need to determine if it lies inside the triangle. sum of area(ADC,BDC,ADB)= area of ABC then D lies inside the triangle.

Is there a way to imporve efficiency in this step. to improve the speed of algo further with out using double for loops..

for i in range(len(points)-1):
    for j in range(len(points[i])-1):
        A=np.array([Vertex_combined[i][0],Vertex_combined[i][1],points[i][j]])
        B=np.array([Vertex_combined[i][1],Vertex_combined[i][2],points[i][j]])
        C=np.array([Vertex_combined[i][0],Vertex_combined[i][2],points[i][j]])
        x=[A,B,C]
        x=np.array(x)
        areas_temp=area(x)
        if round(areas_temp.sum(),2)==round(areas[i],2):validpoints.append(points[i][j])
validpoints= np.reshape(validpoints,newshape=(-1,3))

Points in a Triangle Numpy

0 Answers