Extract unique edge vectors and average edge length, given face list and vertex position array
Alec Jacobson
November 06, 2009
Given an n-length array of vertex positions (I'll assume here that the positions are two dimensional, but it's trivial to make it 3,4, ... , m dimensional) and a triangle face list where each item in the face list is a 3-tuple of vertex indices, then the task is to extract a list of edges (2-tuples of vertex indices) and from that list then average the edge vector lengths. Here's my MATLAB code, assuming your vertex positions are in V and face list in F:
Step 1, extract edges:
edges = unique(sort([F(:,1) F(:,2); F(:,2) F(:,3); F(:,3) F(:,1)]')','rows');
First, [F(:,1) F(:,2); F(:,2) F(:,3); F(:,3) F(:,1)] creates a matrix where each row is an edge on some face. All edges are present but some may appear twice. Since we don't care about orientation on the edges, sort() called on the transpose (notice the first tick) of that matrix gives sorted matrix whose transpose (notice the second tick) is a list of edges with lowest vertex index in the first column. Finally, unique( ... , 'rows') removes all duplicate edges.
Step 2, average edge vector lengths:
edge_norms = sqrt(sum((V(edges(:,1),:)-V(edges(:,2),:)).^2,2));
average_edge_norm = mean(edge_norms);
First, (V(edges(:,1),:)-V(edges(:,2),:)) finds the edge vector for each edge in edges then the .^2 squares each component. The sum(...,2) call sums the entries in each row. Lastly, sqrt(...) takes the square root of each row completing the L2 norm of each edge vector. So now, edge_norms is an array of the lengths of each edge vector. Finally, mean(edge_norms) takes the average across edge vector norms (across rows).
Note: This is my first MATLAB post and I have to admit that I've yet to become a vector-minded programmer, so please post any problems or speed-ups for these code.