Matlab: adjacency matrix from patch object

Question

I have a Matlab patch object, in which the Faces property is a list of vertex index triplets, so each row represents one triangular face. For example:

   293    13     1
   433    13   293
   293   294   433
   434   433   294

In this case, the first row defines a face stretched between the vertices 1,13 and 293. My actual matrix has about 200,000 vertices and 400,000 faces.

I'd like to form a vertex adjacency matrix, e.g. a sparse binary square matrix A s.t. A(i,j) is true iff vertices i,j have a shared face.

Is there any efficient way to do it in matlab? A simple for loop searching for the occurrence of one face in each iteration is slow.

Answer 1

This can be used for arbitrary dimensional simplicial data:

halfedges = nchoosek(1:size(Faces,2), 2);
edges = [halfedges; fliplr(halfedges)];
A = logical(sparse(Faces(:,edges(:,1)), Faces(:,edges(:,2)), 1));

If memory overhead is more of a concern to you than speed, you could loop over the edges:

nv = max(Faces(:)); % Get the maximum vertex id.

halfedges = nchoosek(1:size(Faces,2), 2);
edges = [halfedges; fliplr(halfedges)];
A = sparse(nv,nv);
for i = 1:size(edges,1)
    A = A | logical(sparse(Faces(:,edges(i,1)), Faces(:,edges(i,2)), 1, nv, nv));
end

An alternative could be to build a triangulation object and then use the built-in isConnected function.