@staticmethod<EOL><INDENT>def tesselate_triangle_paths(paths):<DEDENT>
<EOL>A = np.array([<NUM_LIT:0.0>,              <NUM_LIT:0.0>])<EOL>B = np.array([<NUM_LIT:1.0>/np.sqrt(<NUM_LIT>), <NUM_LIT:0.0>])<EOL>C = np.array([<NUM_LIT:0.0>,              <NUM_LIT:1.0>/np.sqrt(<NUM_LIT>)])<EOL>(a21,b21,c21) = [np.reshape(x,(<NUM_LIT:2>,<NUM_LIT:1>)) for x in (A,B,C)]<EOL>paths = [path if len(path) == <NUM_LIT:3> else np.vstack([path, [<NUM_LIT:1> - np.sum(path,<NUM_LIT:0>)]])<EOL>for path in paths]<EOL>bccoords = np.hstack([[[<NUM_LIT:1>,<NUM_LIT:0>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:1>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:0>,<NUM_LIT:1>]], np.hstack(paths)]) <EOL>bccoords0 = np.array(bccoords)<EOL>coords = a21*bccoords[<NUM_LIT:0>] + b21*bccoords[<NUM_LIT:1>] + c21*bccoords[<NUM_LIT:2>] <EOL>coords0 = np.array(coords)<EOL>(coords, bccoords) = [x.T for x in (coords, bccoords)]<EOL>(pidcs,k) = ([],<NUM_LIT:3>) <EOL>for path in paths:<EOL><INDENT>qq = np.shape(path)[<NUM_LIT:1>]<EOL>pidcs.append(k + np.arange(qq))<EOL>k += qq<EOL><DEDENT>idcs = np.arange(len(coords)) <EOL>ridcs = []<EOL>n = <NUM_LIT:0><EOL>for (ii,x) in enumerate(coords):<EOL><INDENT>if idcs[ii] < ii: continue<EOL>dists = np.sqrt(np.sum((coords[ii:] - x)**<NUM_LIT:2>, axis=<NUM_LIT:1>))<EOL>idcs_eq = np.where(np.isclose(dists, <NUM_LIT:0>, atol=<NUM_LIT>))[<NUM_LIT:0>]<EOL>idcs[idcs_eq + ii] = n<EOL>n += <NUM_LIT:1><EOL>ridcs.append(ii)<EOL><DEDENT>if np.sum(idcs[<NUM_LIT:3>:] == idcs[-<NUM_LIT:1>]) > <NUM_LIT:1>:<EOL><INDENT>qii = ridcs[idcs[-<NUM_LIT:1>]]<EOL>coords[qii] = coords[-<NUM_LIT:1>]<EOL>bccoords[qii] = bccoords[-<NUM_LIT:1>]<EOL><DEDENT>if n > <NUM_LIT:64>: warnings.warn('<STR_LIT>' % n)<EOL>elif np.max(idcs) < <NUM_LIT:4>:<EOL><INDENT>assert(len(coords) > <NUM_LIT:4>)<EOL>if idcs[-<NUM_LIT:1>] == idcs[-<NUM_LIT:2>]:<EOL><INDENT>t = [coords[-<NUM_LIT:2>], coords[-<NUM_LIT:1>], coords[idcs[-<NUM_LIT:1>]]]<EOL>if np.cross(coords[-<NUM_LIT:2>] - coords[-<NUM_LIT:1>], coords[idcs[-<NUM_LIT:1>]] - coords[-<NUM_LIT:1>]) <= <NUM_LIT:0>:<EOL><INDENT>return (np.zeros([<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:0>]), np.reshape([[<NUM_LIT:1>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:1>],[<NUM_LIT:0>,<NUM_LIT:0>]], (<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:1>)))<EOL><DEDENT>else:<EOL><INDENT>return (np.reshape([[<NUM_LIT:1>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:1>],[<NUM_LIT:0>,<NUM_LIT:0>]], (<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:1>)), np.zeros([<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:0>]))<EOL><DEDENT><DEDENT>else:<EOL><INDENT>if (idcs[-<NUM_LIT:2>] + <NUM_LIT:1>) % <NUM_LIT:3> == idcs[-<NUM_LIT:1>]:<EOL><INDENT>return (np.reshape([[<NUM_LIT:1>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:1>],[<NUM_LIT:0>,<NUM_LIT:0>]], (<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:1>)), np.zeros([<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:0>]))<EOL><DEDENT>else:<EOL><INDENT>return (np.zeros([<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:0>]), np.reshape([[<NUM_LIT:1>,<NUM_LIT:0>],[<NUM_LIT:0>,<NUM_LIT:1>],[<NUM_LIT:0>,<NUM_LIT:0>]], (<NUM_LIT:3>,<NUM_LIT:2>,<NUM_LIT:1>)))<EOL><DEDENT><DEDENT><DEDENT>pidcs = [[i0 for (i0,i1) in zip(pii[:-<NUM_LIT:1>],pii[<NUM_LIT:1>:]) if i0 != i1] + [pii[-<NUM_LIT:1>]]<EOL>for p in pidcs<EOL>for pii in [idcs[p]]]<EOL>coords   = coords[ridcs]<EOL>bccoords = bccoords[ridcs]<EOL>internal_paths = [[],[]] <EOL>on_edges = ([],[],[])<EOL>for pii in pidcs:<EOL><INDENT>bcx = bccoords[pii]<EOL>x   = coords[pii]<EOL>zz = np.isclose(bcx, <NUM_LIT:0>, atol=<NUM_LIT>)<EOL>(k0,ke) = (<NUM_LIT:1>, len(bcx) - <NUM_LIT:2>)<EOL>for (k_, _k, dr) in zip([k0,ke], [ke,k0], [<NUM_LIT:1>,-<NUM_LIT:1>]):<EOL><INDENT>while dr*k_ < dr*_k and np.sum(zz[k_]) > <NUM_LIT:0>:<EOL><INDENT>wz = np.where(zz[k_])[<NUM_LIT:0>]<EOL>if len(wz) == <NUM_LIT:0> or not zz[k_-dr, wz].any(): break<EOL>k_ = k_ + dr<EOL><DEDENT>if dr == <NUM_LIT:1>: k0 = k_<EOL>else:       ke = k_<EOL><DEDENT>if np.sum(np.isclose(bcx[k0:ke], <NUM_LIT:0>, atol=<NUM_LIT>)) > <NUM_LIT:0>:<EOL><INDENT>raise ValueError('<STR_LIT>',<EOL>dict(coords0=coords0, bccoords0=bccoords0,<EOL>coords=coords, bccoords=bccoords,<EOL>pii=pii, pidcs=pidcs, idcs=idcs, ridcs=ridcs))<EOL><DEDENT>(p0,p1) = bcx[[<NUM_LIT:0>,-<NUM_LIT:1>]]<EOL>(z0,z1) = [np.isclose(p,<NUM_LIT:0>,atol=<NUM_LIT>) for p in (p0,p1)]<EOL>(s0,s1) = [np.sum(z)                 for z in (z0,z1)]<EOL>(e0,e1) = [((<NUM_LIT:0> if     z[<NUM_LIT:2>] else <NUM_LIT:1> if     z[<NUM_LIT:0>] else <NUM_LIT:2>) if s == <NUM_LIT:1> else<EOL>(<NUM_LIT:0> if not z[<NUM_LIT:0>] else <NUM_LIT:1> if not z[<NUM_LIT:1>] else <NUM_LIT:2>) if s == <NUM_LIT:2> else<EOL>None)<EOL>for (z,s) in [(z0,s0), (z1,s1)]]<EOL>if e0 is None or e1 is None:<EOL><INDENT>raise ValueError('<STR_LIT>',<EOL>dict(coords0=coords0, bccoords0=bccoords0,<EOL>coords=coords, bccoords=bccoords,<EOL>pii=pii, pidcs=pidcs, idcs=idcs, ridcs=ridcs))<EOL><DEDENT>(w0,w1) = (bcx[<NUM_LIT:0>, np.mod(e0 + <NUM_LIT:1>, <NUM_LIT:3>)], bcx[-<NUM_LIT:1>, np.mod(e1 + <NUM_LIT:1>, <NUM_LIT:3>)])<EOL>on_edges[e0].append((pii[<NUM_LIT:0>],  w0))<EOL>on_edges[e1].append((pii[-<NUM_LIT:1>], w1))<EOL><DEDENT>segs     = np.zeros((<NUM_LIT:2>,<NUM_LIT:2>,n*n))<EOL>seg_idcs = np.zeros((<NUM_LIT:2>,n*n), dtype=np.int)<EOL>m = <NUM_LIT:0> <EOL>eidx = [None,None,None]<EOL>for (ii,oes) in enumerate(on_edges):<EOL><INDENT>idcs = np.asarray([u[<NUM_LIT:0>] for u in sorted(oes, key=lambda u:u[<NUM_LIT:1>])], dtype=np.int)<EOL>eidx[ii] = idcs<EOL>xs = coords[idcs]<EOL>l = len(xs)<EOL>seg_idcs[<NUM_LIT:0>,m]         = ii<EOL>seg_idcs[<NUM_LIT:0>,m+<NUM_LIT:1>:m+l+<NUM_LIT:1>] = idcs<EOL>seg_idcs[<NUM_LIT:1>,m:m+l]     = idcs<EOL>seg_idcs[<NUM_LIT:1>,m+l]       = np.mod(ii+<NUM_LIT:1>, <NUM_LIT:3>)<EOL>m = m + l + <NUM_LIT:1><EOL><DEDENT>for pii in pidcs:<EOL><INDENT>l = len(pii)<EOL>seg_idcs[<NUM_LIT:0>,m:m+l-<NUM_LIT:1>] = pii[:-<NUM_LIT:1>]<EOL>seg_idcs[<NUM_LIT:1>,m:m+l-<NUM_LIT:1>] = pii[<NUM_LIT:1>:]<EOL>m = m + l - <NUM_LIT:1><EOL><DEDENT>segs[:,:,:m] = np.asarray([coords[ii[:m]].T for ii in seg_idcs])<EOL>seg_idcs = set(zip(*seg_idcs[:,:m]))<EOL>for i in range(n):<EOL><INDENT>for j in range(i+<NUM_LIT:1>,n):<EOL><INDENT>if (i,j) in seg_idcs or (j,i) in seg_idcs: continue<EOL>ss = [coords[i], coords[j]]<EOL>if segments_overlapping(segs, ss).any(): continue<EOL>sii = np.asarray(segment_intersection_2D(segs, ss))<EOL>sii = sii[:,np.isfinite(sii[<NUM_LIT:0>])]<EOL>if len(sii) > <NUM_LIT:0>:<EOL><INDENT>sii = ~(points_close(sii, ss[<NUM_LIT:0>]) | points_close(sii, ss[<NUM_LIT:1>]))<EOL>if sii.any(): continue<EOL><DEDENT>if point_in_segment(ss, coords.T).any(): continue<EOL>seg_idcs.add((i,j))<EOL>segs[:,:,m] = [coords[i], coords[j]]<EOL>m += <NUM_LIT:1><EOL><DEDENT><DEDENT>tris = set([])<EOL>neis = {u:set([]) for u in range(n)}<EOL>for (u,v) in seg_idcs:<EOL><INDENT>if u == v: continue<EOL>neis[u].add(v)<EOL>neis[v].add(u)<EOL><DEDENT>for (a,nei) in six.iteritems(neis):<EOL><INDENT>nei = np.asarray(list(nei))<EOL>(x,y) = (coords[nei] - coords[a]).T<EOL>ths   = np.arctan2(y, x)<EOL>ii    = np.argsort(ths)<EOL>nei   = nei[ii]<EOL>ths   = ths[ii]<EOL>dths  = np.mod(np.roll(ths, -<NUM_LIT:1>) - ths, <NUM_LIT:2>*np.pi)<EOL>for (u,v,th) in zip(nei, np.roll(nei, -<NUM_LIT:1>), dths):<EOL><INDENT>abc = [a,u,v]<EOL>if a == u or u == v or v == a:<EOL><INDENT>raise ValueError('<STR_LIT>',<EOL>dict(bccoords0=bccoords0, coords0=coords0,<EOL>bccoords=bccoords, coords=coords,<EOL>pidcs=pidcs, idcs=idcs, ridcs=ridcs,<EOL>a=a, nei=nei, ths=ths, tris=tris, seg_idcs=seg_idcs))<EOL><DEDENT>if np.isclose(th, [<NUM_LIT:0>,np.pi]).any() or th >= np.pi: continue<EOL>if any(np.sum(np.isin(abc, ee)) == <NUM_LIT:3> for ee in eidx): continue<EOL>tris.add(tuple(np.roll(abc, -np.argmin(abc))))<EOL><DEDENT><DEDENT>mtx = sps.lil_matrix((n,n), dtype=np.int)<EOL>for pii in pidcs:<EOL><INDENT>for (u,v) in zip(pii[:-<NUM_LIT:1>],pii[<NUM_LIT:1>:]):<EOL><INDENT>mtx[u,v] = <NUM_LIT:1><EOL>mtx[v,u] = -<NUM_LIT:1><EOL><DEDENT><DEDENT>tskip = tris<EOL>(lhs, rhs) = (set([]), set([]))<EOL>qq = <NUM_LIT:0><EOL>while len(tskip) > <NUM_LIT:0>:<EOL><INDENT>qq = qq + <NUM_LIT:1><EOL>tris = tskip<EOL>tskip = set([])<EOL>for abc in tris:<EOL><INDENT>(a,b,c) = abc<EOL>itlst = list(zip([<NUM_LIT:1>,<NUM_LIT:1>,<NUM_LIT:1>,-<NUM_LIT:1>,-<NUM_LIT:1>,-<NUM_LIT:1>], [a,b,c,a,b,c], [b,c,a,c,a,b]))<EOL>h = next((sgn*h for (sgn,u,v) in itlst for h in [mtx[u,v]] if h != <NUM_LIT:0>), None)<EOL>if h is None:<EOL><INDENT>tskip.add(abc)<EOL>continue<EOL><DEDENT>for (u,v) in zip(abc,(b,c,a)):<EOL><INDENT>if mtx[v,u] == <NUM_LIT:0>: mtx[v,u] = h<EOL><DEDENT>(lhs if h == <NUM_LIT:1> else rhs).add(abc)<EOL><DEDENT>if tskip == tris: raise ValueError('<STR_LIT>' % tskip)<EOL><DEDENT>bccoords = bccoords[:,:<NUM_LIT:2>]<EOL>return tuple([np.transpose(ll, (<NUM_LIT:1>,<NUM_LIT:2>,<NUM_LIT:0>)) if len(ll) > <NUM_LIT:0> else np.array(ll)<EOL>for hs in (lhs,rhs)<EOL>for ll in [[bccoords[abc] for abc in np.asarray(list(hs))]]])<EOL>
tesselate_triangle_paths([path1, path2...]) yields a (3x2xN) array of N 2D triangles that
  tesselate a triangle without crossing any of the given paths. The paths themselves should
  be in barycentric coordinates and should each start and end on an edge without touching 
  any edge between. The 2nd dimension consists of the first two barycentric coordinates
  while the first dimensions corresponds to the edges of each tesselated triangle.

This function is probably not particularly performant--it operates by trying to connect
every pair of vertices and rejecting a pairing if it crosses any existing line.