Re: From adjacency graph to triangle mesh

From: Carlos Felippa (carlos_at_colorado.edu)
Date: 11/07/04 

Date: 6 Nov 2004 17:46:22 -0800

fakeuser@invalid.domain wrote in message news:<cmionq$quc$1@news.fsu.edu>...
> In article <6bd3575.0411051631.35516711@posting.google.com>,
> Carlos Felippa <carlos@colorado.edu> wrote:
> >Hi - I am looking for a adjacency-graph-to-triangle-corner
> >code for a class project in mesh generation. Specifically,
> >given an adjacency graph build by Delaunay, for example.
>
> Isn't the set of all possible triangles only O(N^3)?
> So checking them one by one is already faster. Since
> your graph is sprase why not
> for i = 1 to N do
> for j > i and adjacent to i do
> for k > j and adjacent to j do
> if k adjacent to i
> add triangle {i, j, k}
> else if k > max adjacent to i
> break; // early exit, might not be worth it.
>
> This is O(N*Delta^2) where Delta = max degree.

That makes sense. Here is a Mathematica prototype
implementation following your algorithm, before conversion to C:

TriangleList[g_]:=Module[{T={},i,j,k,m,n,gi,gj},
   For [i=1,i<=Length[g],i++, gi=g[[i]];
       For [m=1,m<=Length[gi],m++, j=gi[[m]];
            If [j<=i,Continue[]]; gj=g[[j]];
            For [n=1,n<=Length[gj],n++, k=gj[[n]];
                 If [k<=j,Continue[]];
                 If [!MemberQ[T,{i,j,k}], AppendTo[T,{i,j,k}]];
   ]]]; Return[T]];

Any obvious improvements?

Relevant Pages
Quantcast