triangulate an ngon

[zeffii]

here's a snlite ( a bit unstable, that's why it has an iteration limit) for now..

"""
>in verts_in v
out verts_out v
out faces_out s
"""
import sverchok
from sverchok.utils.modules.vertex_utils import np_faces_normals as normals
from sverchok.utils.modules.geom_utils import ccw_angle, pt_in_triangle

def triangulate_version_one(verts, normal=None):

    # print(verts)
    if len(verts) < 3: return [[]]
    if len(verts) == 3: return [[0, 1, 2]]

    # [ ] first we filter out any consecutive colinear verts
    # current_verts, unused_vertex_indices = filter_consecutive_colinear_verts(verts)
    # [ ] are verts coplanar ? if not -> return [[]]
    # [ ] are any edges intersecting? (verts on edges, vers on other verts) -> return [[]]
    
    normal = normals(np.array([verts]))[0] #...  # normal or get_normal(verts)
    index_list = list(range(len(verts)))
    new_index_list = []

    iterations = 0
    max_iterations = len(verts)**2
    while(len(index_list) > 3):
        if iterations > max_iterations:
            #print("ending early")
            break

        for i in range(len(list(index_list))-1):
            if i+1 >= len(index_list):
                #print('index too high')
                break
            #else:
            #    print(len(index_list), i+1)
                
            idx_1 = index_list[i+1]
            idx_0 = index_list[i]
            idx_2 = index_list[i-1]
            v0 = np.array(verts[idx_0])
            v1 = np.array(verts[idx_1])
            v2 = np.array(verts[idx_2])

            # is angle reflexive? ( not an ear )
            if ccw_angle(v1-v0, v2-v0, normal) > np.pi:
                continue
        
            for pt_i in index_list:
                
                # exclude points in this triangle from next check
                if pt_i in {idx_0, idx_1, idx_2}: continue
                
                # does it contain any other verts?
                point = verts[pt_i]
                # print('here')
                if pt_in_triangle(point, v0, v1, v2):
                    break

                new_index_list.append([idx_0, idx_1, idx_2])
                index_list.remove(idx_0)
                break

        # print(new_index_list)
        iterations += 1
        if len(index_list) == 3:
            break
    new_index_list.append(index_list)
    return new_index_list


for verts in verts_in:
    # print(verts)
    faces = triangulate_version_one(verts)
    verts_out.append(verts)
    faces_out.append(faces)