Maximal Rectangle for Pixel Art

<!DOCTYPE html>
<html>
<head>
<script language="javascript">
/*
https://www.w3schools.com/code/tryit.asp?filename=GJ348BT5QHBE

https://stackoverflow.com/questions/54757142/find-the-coordinates-of-all-rectangles-of-contiguous-1s-in-a-2d-array-in-javascr

Here is a way to do it with using a simple algorithm.

Calculate the total area covered by rectangles -> A
While the area of the rectangles found so far is smaller than A
Find a new rectangle
Find the upper left corner, scan the matrix and stop at the first 1 found
Find the bottom right corner, starting at the upper left corner, scan the matrix and stop at the first 0 found
Mark the rectangle found by setting each cell to something else than 1
Add its area to the accumulated area
Push the rectangle to a list

Convert tilemap default data using Notepad++: find/replace (regular expression) 

for left side: (\t) => ([) make Tabs then replace them with 
left bracket, then find/replace (regular expression)

for right side: (,\r) => (],\r)

Output:
2nd num minus the first +1(because "0") to get length OR height
[
  {
    "x1": 4,
    "x2": 16,
    "y1": 0,
    "y2": 2
  },
  {
    "x1": 4,
    "x2": 6,
    "y1": 3,
    "y2": 17
  },
  {
    "x1": 7,
    "x2": 15,
    "y1": 7,
    "y2": 9
  },
  {
    "x1": 7,
    "x2": 16,
    "y1": 15,
    "y2": 17
  }
]

*/

const _pixelArt = [27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,
27,51,36,22,22,22,22,36,51,36,22,22,22,22,36,51,27,
27,51,36,22,22,22,22,36,51,36,22,22,22,22,36,51,27,
27,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,27,
27,51,27,27,27,27,27,51,27,51,27,27,27,27,27,51,27,
27,51,36,22,22,22,27,51,51,51,22,22,22,22,36,51,27,
27,51,36,22,22,22,27,27,27,27,22,22,22,22,36,51,27,
27,51,36,22,22,22,22,22,22,22,22,22,22,22,36,51,27,
27,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,27,
27,51,51,27,27,27,27,27,27,27,27,27,27,27,51,51,27,
27,27,27,56,56,56,56,56,56,56,56,56,56,56,27,27,27]

const _width = 17;
const _height = 11;
const _name = "TreasureChest";// 'Art' prefix is assumed

const mat = [
[27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27],[27,51,36,22,22,22,22,36,51,36,22,22,22,22,36,51,27],[27,51,36,22,22,22,22,36,51,36,22,22,22,22,36,51,27],[27,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,27],[27,51,27,27,27,27,27,51,27,51,27,27,27,27,27,51,27],[27,51,36,22,22,22,27,51,51,51,22,22,22,22,36,51,27],[27,51,36,22,22,22,27,27,27,27,22,22,22,22,36,51,27],[27,51,36,22,22,22,22,22,22,22,22,22,22,22,36,51,27],[27,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,27],[27,51,51,27,27,27,27,27,27,27,27,27,27,27,51,51,27],[27,27,27,56,56,56,56,56,56,56,56,56,56,56,27,27,27]
];

const W = mat[0].length;
const H = mat.length;

//const _needle = 7; // the no. we're seeking for rectangles


const rects = [];
let rectArea = 0;


function _convertArray()
{
  // convert tilemap array to the other array type
  let _build = "";
  let aa = 0;
  for (let h = 0; h < _height; ++h) {
  _build += h != 0 ? ",[" : "[";
    for (let w = 0; w < _width; ++w) {
      // 56 is our "blank(0)"
       _build +=_pixelArt[aa];
       _build += w == _width-1 ? "]" : ","
       ++aa;
    }
  }
    document.getElementById("convertarray").innerHTML = _build;
}


function MaximalRectangle(_needle=7)
{
  // get the area covered by rectangles
  let totalRectArea = 0;
  for (let i = 0; i < W; ++i) {
    for (let j = 0; j < H; ++j) {
      // 56 is our "blank(0)"
      totalRectArea += mat[j][i] == _needle ? 1 : 0;
    }
  }

  rectArea = 0;

  // find all rectangle until their area matches the total
  while (rectArea < totalRectArea) {
    const rect = findNextRect(_needle);
    rects.push(rect);
    markRect(rect);
    rectArea += (rect.x2 - rect.x1 + 1) * (rect.y2 - rect.y1 + 1);
  }

}


//console.log(rects);



function findNextRect(_needle) {
  // find top left corner
  let foundCorner = false;
  const rect = {color:_needle, x1: 0, x2: W-1, y1: 0, y2: H-1 };
  for (let i = 0; i < W; ++i) {
    for (let j = 0; j < H; ++j) {
      if (mat[j][i] === _needle) {
        rect.x1 = i;
        rect.y1 = j;
        foundCorner = true;
        break;
      }
    }
    if (foundCorner) break;
  }
  // find bottom right corner
  for (let i = rect.x1; i <= rect.x2; ++i) {
    if (mat[rect.y1][i] !== _needle) {
      rect.x2 = i-1;
      return rect;
    }
    for (let j = rect.y1; j <= rect.y2; ++j) {
      if (mat[j][i] !== _needle) {
        rect.y2 = j-1;
        break;
      }
    }
  }
  return rect;
}

// mark rectangle so won't be counted again
function markRect({ x1, y1, x2, y2 }) {
  for (let i = x1; i <= x2; ++i) {
    for (let j = y1; j <= y2; ++j) {
      mat[j][i] = 56;
    }
  }
}



for(let aa = 0; aa < 56; ++aa)
{
    MaximalRectangle(aa)
}

//MaximalRectangle(12);MaximalRectangle(7);MaximalRectangle(1);

//show array as string (to view)
const _showMat = mat.toString();
const _showRects = rects.toString();
const _rCount = rects.length;
const WR = rects[6]["x2"] - rects[6]["x1"] +1;
const HR = rects[6]["y2"] - rects[6]["y1"] +1;
const _sizeMat = String(W) + "w : " + String(H) + "h";
const _sizeRects = String(WR) + "w : " + String(HR) + "h";

//totalRectArea
const _print = W * H + " elements => result: " + _rCount + " tiles" ;

// print out the new array to copy
function _printArray()
{
  let _build = "local _pixelArt = { -- Art"+_name+"<br />";
  
  
  for(var i = 0; i < rects.length; i++) {
      let _width = rects[i]["x2"] - rects[i]["x1"] + 1;
    let _height = rects[i]["y2"] - rects[i]["y1"] + 1;
      _build += "{";
      
      _build += rects[i]["color"] + ",";
      
      _build += rects[i]["x1"] + ","
      
      _build += rects[i]["y1"] + ",";
      
      _build += _width + ",";
      
      _build += _height + "}";
      
      _build += i < rects.length-1 ? "," : "";
      
      //_build += rects[i]["x2"];// ends
      //_build += rects[i]["y2"];
      
  }
      _build += "<br />}<br />_pixelArt._width = "+_width+"<br />";
    _build += "_pixelArt._height = "+_height+"<br />";
    _build += "return _pixelArt";
    document.getElementById("printarray").innerHTML = _build;
  
}

</script>
</head>
<body>

<h2>Find Large Rectangles</h2>

<button type="button"
onclick="onclick=_convertArray()">
Convert Tilemap</button>

<button type="button"
onclick="document.getElementById('demo').innerHTML = _print">
Test Data</button>

<button type="button"
onclick="_printArray()">
Pixel Array</button>

<p id="demo"></p>
<p id="convertarray"></p>
<p id="printarray"></p>
</body>
</html> 

Latest Posts

Emulation ProcessEmulation Process

  Record Locs for Emulation in Core Grab data. Here, I am recording x,yz, and name data to emulate. Next Convert to usable array for Core template data. Snippet>> Pattern  Core template replacement pattern: Path:[C:\Users\soandso\Documents\My Games\CORE\Saved\Maps\mycoregame\Data\Tree\Emulator_