矩形标签云算法实现

标签云在移动端已经应用得比较多了,比较常见的是流式布局,3D球状布局,或者是随机布局。而在Web端则有更多的布局形式,比较多的是图像轮廓布局,例如下图所示
Image Image


本文要分享和记录的则是一个在移动端实现的矩形标签云算法的实现,效果如下图:
Image


装箱问题

在实现上面的效果之前,我们可以简单理解为就往一个底边固定,高度可以任意延伸的矩形区域内填充标签,当然每个标签是可大可小的,于是乎就形成了一个经典的二维装箱问题。与之相对应的还有一个改进过的算法2D 条带矩形 Packing 问题
我去尝试了这个算法后,整体效果还可以,但有一个非常明显的问题,那就是每次计算出的结果是一致的,如果想要达到一种随机排列的效果,显然存在一定的局限性。


图像轮廓布局

矩形框其实也可以理解为一个轮廓为矩形的区域,自然也是可以直接使用轮廓布局的算法的,轮廓布局算法的核心是把一个图案切分成若干个小的矩形区域,然后从需要填充的词语中随机选择词语进行填充,这样一来,很难保证一些重点内容的突出展示。


简易矩形标签云算法

下面介绍一下一个简易矩形标签云算法,这个算法只适合标签内容不多的情况,如果标签内容过多,计算量将会比较大,不太适宜。

  • 标签排序

把标签按一定的权重规则,排列为字号大小不一的标签,有了字号内容,我们就可以计算出每个标签的frame。在计算frame时,有个问题得强调一下,如果我们使用NSAttributedString size方法,我们会发现计算出来的高度比实际渲染的高度要高。

Image
边框(Bounding Box):一个假想的边框,尽可能地容纳整个字形。

基线(Baseline):一条假想的参照线,以此为基础进行字形的渲染。

基础原点(Origin):基线上最左侧的点。

行间距(Leading):行与行之间的间距。

字间距(Kerning):字与字之间的距离,为了排版的美观,并不是所有的字形之间的距离都是一致的,但是这个基本不影响到我们的文字排版。

上行高度(Ascent)和下行高度(Decent):一个字形最高点和最低点到基线的距离,前者为正数,而后者为负数。当同一行内有不同的字体文字时,就取最大的值为相应的值。

如果标签内容全部是中文的话,是可以把计算出来的高度减去font.lineHeight - font.pointSize,但如果标签内容里面还包含有英文、或者是emoji表情的话,使用这个方法,就会出现内容被裁剪的情况。

另外一个比较好的方法是通过coreText渲染来计算实际高度,缺点是计算繁琐一点。

- (CGFloat)displayHeight:(NSAttributedString *)string width:(CGFloat)width font:(UIFont *)font
{
    CGFloat returnY = 0;
    CTLineRef line = CTLineCreateWithAttributedString((__bridge CFAttributedStringRef)string);
    CFArrayRef runArray = CTLineGetGlyphRuns(line);

    CGFloat ascent, descent, leading;
    CTLineGetTypographicBounds(line,&ascent,&descent,&leading);

    for (int i = 0; i < CFArrayGetCount(runArray); i++) {
        CTRunRef run = (CTRunRef)CFArrayGetValueAtIndex(runArray, i);
        CFRange range = CFRangeMake(0, 0);
        CGRect glyphRect = CTRunGetImageBounds(run, NULL, range);

        returnY = MAX(returnY, glyphRect.size.height-glyphRect.origin.y);
    }
    CFRelease(line);
    if (returnY > ascent) {
        return returnY;
    }
    else
    {
        return ascent + descent;
    }
}

然后,我们把标签按面积从大到小进行排序。

  • 锯木板

根据现有的标签内容,估算出一个大概的矩形区域,例如我们可以把所有标签的面积累加起来,再乘以1.4倍,得到一个填充矩形供这些标签填充。

如果把整个填充区域看成是一块"木板"的话,那我们选择把面积较大的标签从"木板"的边缘锯掉,剩下的区域则更能适合其它较小的标签进行填充。按照这个思路,我们每次都在"木板"边缘进行填充,当然我们支持横、竖两个方向的填充。然后,再对所有这些标签进行一个向中心点靠拢的收缩。

于是我们就可以大致得出一个标签云的排版内容。

  • 空白区域填充

通过上面的算法处理后,矩形区域内会残留许多空白区域,如何找出这些空白区域,并尽可能地找出里面最大的空白区域,是我们下一步要处理的核心。
Image

1)从已填充的标签上、下、左、右出发,查找最大空白区域。
2)以左图标签C右侧为例,在遍历查找过程中与B做碰撞检测找出C’和C’’这两块区域。对于多个结果深入递归后取最大面积(忽略较小面积)
3)所有找出来的空白区域,去除相交后,保留最大面积。
4)针对各个空白区域,寻找最合适的现有标签进行填充(形状最匹配)。
5)一次填充后,再次递归上面的操作,直到找不出新的空白区域。

最终结果如下:
Image

  • 渲染

对于横向标签,可以直接使用UILabel进行渲染,但竖向渲染需要一些额外的工作,网上有一些取巧的竖向渲染的方法,例如在每个字符后面加上换行符。例如"天气不错"改为"天\n气\n不\n错",但在遇到英文的时候发现很难阅读。

这个时候需要用coreText自行进行排版,YYLabel就很好地支持了竖向排版。


最终效果:

Image

2017-07-27 10:3596