T-Junctions re-visited

Re: T-Junctions re-visited
#2
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
« Next Oldest | Next Newest »

 Messages In This Thread T-Junctions re-visited - by Travis Cobbs - 2013-03-12, 5:38 Re: T-Junctions re-visited - by Tim Gould - 2013-03-12, 6:31 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-12, 18:17 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-12, 18:17 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-12, 18:22 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-12, 18:32 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-12, 18:41 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-12, 18:55 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-13, 17:08 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-13, 18:27 Re: T-Junctions re-visited - by Allen Smith - 2013-03-12, 21:01 Re: T-Junctions re-visited - by Michael Heidemann - 2013-03-13, 16:27 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-13, 17:37 Re: T-Junctions re-visited - by Tim Gould - 2013-03-13, 21:31 Re: T-Junctions re-visited - by Michael Heidemann - 2013-03-13, 22:42 Re: T-Junctions re-visited - by Michael Heidemann - 2013-03-17, 11:35 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-17, 15:43 Re: T-Junctions re-visited - by Michael Heidemann - 2013-03-17, 15:59 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-17, 16:02 Re: T-Junctions re-visited - by Magnus Forsberg - 2013-03-17, 16:15 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 5:09 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-18, 14:30 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 17:57 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-18, 18:27 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 19:23 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-18, 20:41 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-18, 21:51 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 21:59 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-18, 22:41 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-19, 1:09 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-19, 18:38 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-19, 18:43 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-20, 2:07 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-20, 5:13 Re: T-Junctions re-visited - by Tim Gould - 2013-03-20, 10:56 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-20, 17:13 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-20, 17:23 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-20, 17:29 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-20, 17:26 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-20, 18:18 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-20, 13:42 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-20, 18:36 Re: T-Junctions re-visited - by Philippe Hurbain - 2013-03-20, 13:36 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-20, 13:58 Re: T-Junctions re-visited - by Allen Smith - 2013-03-20, 16:08 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-20, 18:35 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-20, 18:50 Re: T-Junctions re-visited - by Michael Heidemann - 2013-03-18, 22:54 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-13, 17:03 Re: T-Junctions re-visited - by Tim Gould - 2013-03-13, 22:56 Re: T-Junctions re-visited - by Sergio Reano - 2013-03-13, 22:51 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-13, 23:36 Re: T-Junctions re-visited - by Tim Gould - 2013-03-14, 0:10 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-15, 3:17 Re: T-Junctions re-visited - by Tim Gould - 2013-03-15, 3:41 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-15, 17:56 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-15, 18:36 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-14, 1:58 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-14, 2:27 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-14, 2:37 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-14, 2:59 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-14, 3:18 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-14, 22:23 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-14, 22:34 Re: T-Junctions re-visited - by Tim Gould - 2013-03-14, 22:41 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-15, 18:33 Re: T-Junctions re-visited - by Tim Gould - 2013-03-14, 2:43 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-14, 3:08 Re: T-Junctions re-visited - by Tim Gould - 2013-03-14, 3:18 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-15, 3:15 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-15, 18:29 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-15, 19:27 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-16, 0:08 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-17, 6:29 Re: T-Junctions re-visited - by Ben Supnik - 2013-03-17, 15:58 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-17, 19:35 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 19:28 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-18, 19:32 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-19, 0:00 Re: T-Junctions re-visited - by Travis Cobbs - 2013-03-19, 6:05 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-19, 18:38 Re: T-Junctions re-visited - by Sergio Reano - 2013-03-26, 21:46 Re: T-Junctions re-visited - by Roland Melkert - 2013-03-27, 18:19 Re: T-Junctions re-visited - by Sergio Reano - 2013-03-27, 20:48

Forum Jump:

Users browsing this thread: 1 Guest(s)