Tile map optimization algorithm

From that picture it looks like the method to put tiles into regions like that is to check left as far as you can go for sameness, and then check for sameness below as far as you can go without a mismatch. Regions would be defined by their top left and bottom right tiles. You'd just do that, line by line, and have something in place to indicate certain tiles are already part of a region. That could just be another temporary array the same size as the tile map filled with booleans that you set when you add a tile to a region.

for ( int y = 0; y < tilemap.height; ++y){
    for ( int x = 0; x < tilemap.width; ++x){
        if (taken_tiles[x,y]){
            continue;
        } else {
            Region* rc = region_container.add(x, y, tilemap[x,y].tile_type);
            taken_tiles[x,y] = true;
            for ( int x2 = 0; x2 < tilemap.width - x; ++x2){
                if (tilemap[x+x2,y].tile_type == tilemap[x,y].tile_type
                    && !taken_tiles[x + x2,y]){
                    rc->last_tile(x + x2, y);
                } else {
                    for ( int y2 = 0; y2 < tilemap.height - y; ++y){
                        //check then row below the previously added row
                        //from rc->first_tile.x to rc->last_tile.x on the
                        // y + y2 line. If all are same then make each
                        // of them taken and make the y + y2 as rc->last_tile.y
                        // if there's a difference then break
                    }
                    break;
}    }    }    }    }