# [R] Add transitivity to a matrix?

Duncan Murdoch murdoch@dunc@n @end|ng |rom gm@||@com
Tue Jun 18 15:44:02 CEST 2019

```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

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

```