T-Junctions re-visited

[Tim Gould]

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:

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