Hi Travis,

I'm not sure what the hardest stage is, but if one computes all valid edges (on triangles or quads), then one can efficiently check if points lie within lines as follows:

After that, one needs to split all tris and quads that have a point K in the line trios.

What this does may not deal with well is quads with splits on multiple edges. That could perhaps be checked for if results from the above suck.

Tim

I'm not sure what the hardest stage is, but if one computes all valid edges (on triangles or quads), then one can efficiently check if points lie within lines as follows:

Code:

`# O (N_Edges N_Points)`

for I,J in Edges

for K in Points

DIJ=Dist(P(I),P(J))

DIK=Dist(P(I),P(K))

DJK=Dist(P(I),P(K))

if (abs(DIJ-(DIK+DJK))<TOL)

# K is on the line between I & J

PushLineTrio(I,J;K)

endif

endfor

endfor

After that, one needs to split all tris and quads that have a point K in the line trios.

Code:

`# O(N_LineTrios log(N_LineTrios))`

SortLineTriosBy(I,J)

# O(N_LineTrios)

foreach I,J in LineTrios # Count on I,J first to split along a line

if (NumberLineTriosWith(I,J) is 1)

SplitIJAtKTri/Quad # For quads there are two options here, perhaps split into three tris here rather than trying to choose

else

SplitIJAtMultipleKTri/Quad # Hard

endif

endfor

Code:

`routine SplitIJatKTri(I,J;K)`

foreach Tri with I,J as an edge # This is slow but won't be called very often

NewTri(I,K,Tri.L)

NewTri(J,K,Tri.L)

DeleteTri(I,J,Tri.L)

endfor

routine SplitIJatMultipleKTri(I,J;KS)

foreach Tri with I,J as an edge # This is slow but won't be called very often

NewTri(I,KS(1),Tri.L)

for IK in 1..(NKS-1)

NewTri(KS(IK),KS(IK+1),Tri.L)

endfor

NewTri(KS(NKS),J,Tri.L)

DeleteTri(I,J,Tri.L)

endfor

routine SplitIJatKQuad(I,J;K)

# Quad has I,J,L,M going around

foreach Quad with I,J as an edge # This is slow but won't be called very often

NewTri(I,K,Tri.M)

NewTri(J,K,Tri.L)

NewTri(K,Tri.L,Tri.M)

DeleteQuad(I,J,Quad.L,Quad.M)

endfor

What this does may not deal with well is quads with splits on multiple edges. That could perhaps be checked for if results from the above suck.

Tim