单元格面积大优先合并问题

【Javascript】

下载

新闻

文章

Q群里有人提问一个表格面积优先合并算法，考虑了良久才写了出来。

假如有这么个数组：

    var arr = [
        [1,1,1,2,2,2,2],
        [1,1,1,2,2,1,1],
        [1,3,1,1,1,2,2],
        [1,3,1,2,2,1,1],
        [1,3,1,2,1,1,1],
        [1,1,1,2,2,2,2]
    ]

把它绘成表格，然后合并相同单元格，并按面积最大优先合并。

开始想到的方法是先取一个元素，然后循环所有元素，找出该元素能合并的最大面积并合并。并循环遍历一下即可，得到如下图：

但仔细一看右下角有问题，本来最后一行右边可以合并4个单元格的。其实这个面积优先计算它应该要全方位考虑，很多单元格是相互制约关系。

此算法应该优先取出最大面积来合并。方法就是前面的基础上循环遍历，即每次取一个最大面积来合并单元格。重点是合并完后需要重新计算各自能合并的最大面积，因为有些相关单元格可能被合并了。如此循环到最后就能绘制表格了。

<table border="1" style="width:400px">
    <thead></thead>
    <tbody></tbody>
</table>
<script type="text/javascript">
    var arr = [
        [1,1,1,2,2,2,2],
        [1,1,1,2,2,1,1],
        [1,3,1,1,1,2,2],
        [1,3,1,2,2,1,1],
        [1,3,1,2,1,1,1],
        [1,1,1,2,2,2,2]
    ]
    var arrMap = [] // 克隆数组
    var arrPlane = [] // 扁平数组
    arr.forEach((array,l)=>{
        let a = []
        array.forEach((v,i)=>{
            let o = {v,l,i,a:1,ml:1,mr:1}
            a.push(o)
            arrPlane.push(o)
        })
        arrMap.push(a)
    })
    // 循环遍历函数
    ;(function(){
        if(!arrPlane.length){
            const _array = []
            arrMap.forEach(line => {
                let _arr = ['<td>*</td>']
                line.forEach(item => {
                    if (item.a === 0) {
                        _arr.push(`<td align="center" ${item.ml > 1 ? ' rowspan="' + item.ml + '"' : ''}${item.mr > 1 ? ' colspan="' + item.mr + '"' : ''}>${item.v}</td>`)
                    }
                })
                _array.push(_arr.join(''))
            })
            document.querySelector('thead').innerHTML = '<tr><th>#</th>'+arr[0].map(()=>'<th>#</th>').join('')+'</tr>'
            document.querySelector('tbody').innerHTML = '<tr>'+_array.join('</tr><tr>')+'</tr>'
            return
        }
        const length = arrMap.length
        // 核心计算最大面积
        arrPlane.forEach(obj => {
            var maxLine = 0 // 最大行数
            var maxRow = 0 // 最大列数
            var maxLen = null; // 序号
            var line,group,i,_line,_row
            hook:
              for (line = obj.l; line < length; line++) {
                  group = arrMap[line] // 整行数据
                  maxLen = maxLen === null ? group.length : maxLen
                  for (i = obj.i; i < maxLen; i++) {
                      var _obj = group[i]
                      if (_obj.v !== obj.v || _obj.a < 1) {
                          if (i === obj.i) break hook
                          break
                      }
                  }
                  maxLen = i
                  _line = line - obj.l + 1
                  _row = i - obj.i
                  // > ：相同面积下优先合并行， >= ：相同面积下优先合并列
                  if (_line * _row >= maxLine * maxRow) {
                      maxLine = _line
                      maxRow = _row
                  }
              }
            obj.mr = maxRow
            obj.ml = maxLine
            obj.a = maxLine * maxRow // 得出能合并的最大面积
        })
        // 按面积大小排序
        arrPlane.sort((a, b) => a.a > b.a ? -1 : 1)
        // 取最大面积的元素、并处理需要合并的单元格
        let obj = arrPlane.shift()
        for (var line = obj.l; line < obj.l + obj.ml; line++) {
            var group = arrMap[line]
            for (var row = obj.i; row < obj.i + obj.mr; row++) {
                group[row].a = -1
            }
        }
        obj.a = 0
        // 过滤数组
        arrPlane = arrPlane.filter(obj => obj.a > 0)
        arguments.callee()
    }())
</script>

效果如下：