[R] Add transitivity to a matrix?

[Duncan Murdoch]

On 18/06/2019 9:01 a.m., Eric Berger wrote:
> Very nice, Peter.
> Here is one version of Peter's suggestion expressed in R code
> 
> M <- M | t(M)  # first step as symmetric matrix as stated by OP
> Q <- M
> for ( i in 2:(ncol(Q)-1) )
>     Q <- Q + Q %*% M
> 
> R <- (Q > 0)
> R
> 

That's not quite the same calculation as Peter suggested, but I think 
it's also going to work.  Of course, I might use seq_len(ncol(Q) - 2) 
instead of 2:(ncol(Q)-1), but that also won't make a difference in the 
final result.

Thanks to everyone who has suggested calculations here.  I'm glad we saw 
such good suggestions, because (I'm embarrassed to say) it turns out 
that I don't actually want transitivity after all.

In case anyone is interested, here's the application:

I was asked whether rgl could render a surface made up of triangles or 
quadrilaterals to look smooth.  It can do that, but needs normals at 
each vertex; they should be the average of the normals for each polygon 
sharing that vertex.  Then OpenGL will interpolate the normals across 
the polygons and give the illusion of smoothness.

To do this, it needs to know which polygons share each vertex.  If the 
surface is described as a list of triangles or quadrilaterals, that 
means identifying vertices that are in multiple polygons, and converting 
the representation to a "mesh3d" object (which is a matrix of vertices 
and a matrix of vertex numbers making up triangles or quads).  Then the 
addNormals() function will add the normals.

But sometimes two polygons will share vertices (within numerical 
tolerance) without the user wanting them to be considered internal to 
the surface, or you might want one sharp edge in an otherwise smooth 
surface.  This means I needed a way to declare that two vertices from 
the original list of vertices in the triangles or quads are "not equal", 
even when they test numerically equal.

That's what was going to be the matrix R in Eric's notation.  If vertex 
i and vertex j test equal, but R[i,j] is TRUE, they should not be merged 
into a single vertex.  Clearly symmetry is a requirement.

The transitivity came in when I thought about how the user would specify 
the matrix.  It's really tedious to enter a full matrix, so I wanted to 
allow the user to give less information and have the function fill out 
the rest.  For example, if I compute

cube <- cube3d()
x <- cube$vb[1, c(cube$ib)]
y <- cube$vb[2, c(cube$ib)]
z <- cube$vb[3, c(cube$ib)]

then quads3d(x,y,z, col = "red") will plot a red cube, but without 
information about which faces are joined.  It works with this matrix of 
vertices:

 > cbind(x,y,z)
        x  y  z
  [1,] -1 -1 -1
  [2,] -1  1 -1
  [3,]  1  1 -1
  [4,]  1 -1 -1
  [5,] -1  1 -1
  [6,] -1  1  1
  [7,]  1  1  1
  [8,]  1  1 -1
  [9,]  1 -1 -1
[10,]  1  1 -1
[11,]  1  1  1
[12,]  1 -1  1
[13,] -1 -1 -1
[14,] -1 -1  1
[15,] -1  1  1
[16,] -1  1 -1
[17,] -1 -1 -1
[18,]  1 -1 -1
[19,]  1 -1  1
[20,] -1 -1  1
[21,] -1 -1  1
[22,]  1 -1  1
[23,]  1  1  1
[24,] -1  1  1

and plots a quadrilateral for each successive group of 4 vertices.

Now I can see that vertices 1, 13 and 17 are the same, and my algorithm 
would merge them into one unless told not to.  So I thought a user 
should be able to say they are not equal by saying 1 != 13, 1 != 17 and 
transitivity would yield 13 != 17.  But in fact, a user might want to 
merge 13 and 17, but keep 1 separate:  so I don't want transitivity, I 
only want symmetry.  After setting

M <- matrix(FALSE, 24,24)
M[1, 13] <- TRUE
M[1, 17] <- TRUE

I should get different results if I set

M[13, 17] <- TRUE

or leave it FALSE.

Hopefully people found the transitivity discussion interesting, even if 
I won't use it for this problem.

Duncan Murdoch