strict rectangles

rectangles.R

library(data.table)

shapes <- function(m) {
    n <- length(m)
    nrow <- nrow(m)
    
    index <- seq_len(n)
    rows <- ((index - 1L) %% nrow) + 1L
    cols <- ((index - 1L) %/% nrow) + 1L
    
    shapes <- integer(n)
    shapes[1L] <- shp <- 1L
    for (i in index[-1L]) {
        row <- rows[i]
        col <- cols[i]
        if (col == 1L) {
            if (m[i] == m[i - 1L]) {
                shapes[i] = shapes[i - 1L]
            } else {
                shp <- shp + 1L
                shapes[i] <- shp
            }
        } else {
            if (row == 1L) {
                j <- (col - 2L) * nrow + row
                if (m[i] == m[j]) {
                    shapes[i] = shapes[j]
                } else {
                    shp <- shp + 1L
                    shapes[i] <- shp
                }
            } else {
                if (m[i] == m[i - 1L]) {
                    shapes[i] = shapes[i - 1L]
                } else {
                    j <- (col - 2L) * nrow + row
                    if (m[i] == m[j]) {
                        shapes[i] = shapes[j]
                    } else {
                        shp <- shp + 1L
                        shapes[i] <- shp
                    }
                }
            }
        }
    }
    
    DT <- data.table(rows, cols, shapes)
    
    .is_rectangle <- function(rows, cols) {
        top <- min(rows)
        bottom <- max(rows)
        height <- bottom - top + 1L
        
        left <- min(cols)
        right <- max(cols)
        width <- right - left + 1L
        
        if (width * height == length(rows)) TRUE else FALSE
    }
    
    DT <- DT[, rectangle := .is_rectangle(rows, cols), by = shapes]
    DT <- DT[rectangle == TRUE]

    .corners <- function(rows, cols) {
        top <- min(rows)
        bottom <- max(rows)
        left <- min(cols)
        right <- max(cols)
        list(
            corner = c("top_left", "top_right", "bottom_left", "bottom_right"),
            row = c(top, top, bottom, bottom),
            col = c(left, right, left, right)
        )
    }
    DT <- DT[,.corners(rows, cols), by = shapes]
    DT[, rectangle := .GRP, by = shapes][,shapes := NULL][]
    setcolorder(DT, "rectangle")[]
}

in answer to https://fosstodon.org/@teunbrand/111262964634123976

no need for the .corners() bit if all coords are wanted.