Grid 布局算法!自己动手实现一个 Grid

Grid 布局算法!自己动手实现一个 Grid

2018-05-20 07:11

Avalonia 是一款尚在开发中的基于 .NET Core 的跨平台 UI 框架。目前用在个人项目中还是不错的,不过还需要大家在开源社区中多多支持。

我为它写了一个全新的 Grid 布局算法,此算法是 WPF 在通常情况下的性能的两倍。本文将分享我在此项目中实现的算法的原理。


Grid 的布局行为到底是怎样的?

Grid 算是 WPF/UWP 入门中非常重要的一个布局容器了。面对它那强大而熟悉的布局方式,大家应该没有什么疑问吧!

比如:

  • 可以定义行和列
  • 可以分别为每一行和列指定宽高
  • 宽高的值可选 Auto, * 和数值
    • Auto 表示 Grid 将按照元素的实际所需尺寸进行布局
    • * 表示行列在布局中的比例,* 前面的数值表示比例值
    • 数值使用的是 WPF/UWP 布局单位
  • 元素在 Grid 中可跨行或跨列

基本上大家所熟知的 Grid 布局差不多就这样么多了。

如果想了解 WPF/UWP 的布局单位,可以阅读我之前的一篇文字将 UWP 的有效像素(Effective Pixels)引入 WPF - 吕毅

然而,事实上 Grid 的布局行为才没有那么简单呢!它诡异的地方在于没有定义好多种复杂布局情况下的交叉行为。我写了中英两篇文章来说明了这些不太符合预期的行为:

作为一个非常有潜力的 .NET Core 跨平台 UI 框架 Avalonia,应该认真定义好这些行为,而不是像 WPF/UWP 现有的 Grid 那样在某些情况下比较含糊,出现难以解释的布局行为。

为这样的 Grid 布局行为设计一套算法

如果你熟知 WPF/UWP 的布局系统,那么 MeasureOverrideArrangeOverride 一定不陌生,虽然它们只是布局的一部分(为什么是一部分?详见 Visual->UIElement->FrameworkElement,带来更多功能的同时也带来了更多的限制 - 吕毅)。

不过,写一个 Grid 确实只需要关心这两个函数就够了。MeasureOverride 传入父级测量的可用尺寸,返回此 Grid 测量发现所需的最小尺寸;ArrangeOverride 传入父级实际可提供的可用尺寸,返回此 Grid 实际布局所用的尺寸。

分析 Grid 的布局思路

如果行或列设置为 Auto,那么 Grid 的行或者列将为这个元素的尺寸进行适配,并且元素的所需尺寸也会影响到 Grid 的最小所需尺寸;如果行或列设置为 *,那么 Grid 的行列不会为此元素适配,但是元素的所需尺寸依然会影响到 Grid 的最小所需尺寸。

由于我们必须要计算 Grid 的最小所需尺寸,所以整个布局过程中,必须得到每个行列的最小所需尺寸。这意味着,即便我们不能确定此行或此列的尺寸,或者甚至在父级尺寸确定的情况下能够确定此行或此列时,也应该计算最小尺寸。而 Auto、元素的 DesiredSize* 或者行列的最小值都会影响到此最小尺寸,所以这些都应该先考虑。而行或列的最大值应该在最后再考虑。

于是,我们将整个布局过程分成以下几步:

  1. 测量行列范围中包含 Auto* 的元素(前者影响行列和最小尺寸,后者仅影响最小尺寸)
  2. 将所有的已确定尺寸确定
  3. 将所有的有最小尺寸,且 * 展开后超过此最小尺寸的行列按最小值确定
  4. 将所有 Auto 行列确定
  5. 按照父级尺寸估算 * 的尺寸
  6. 计算 Grid 所需的最小尺寸
  7. 将估算缩得的尺寸作为实际尺寸进行测量

布局算法设计

Grid 的布局算法似乎难以用语言描述,不过,我可以尝试用更具体的文字用接近代码的方式来描述:

  • 测量过程
    1. 寻找所有行列范围中包含 Auto 和 * 的元素,使用全部可用尺寸提前测量
    2. 排除所有固定尺寸的行列,然后从总长中将其减掉
    3. 进行循环(以排除全部 min 要求的,总长为负也要继续
      • 计算单位星长(单位星长 = 剩余总长 / 星数,最小为 0)
      • 找出第一个不满足 min 要求的 *,置其长度为 min,排除此行列,然后从总长中将其减掉
      • 所有的 * 检查完毕后,退出循环
    4. 进行循环(以排除全部 Auto,总长为负也要继续
      • 计算单位星长(单位星长 = 剩余总长 / 星数,最小为 0)
      • 找到第一个 Auto,找到对此 Auto 的约束(跨行列或不跨行列都需要)
      • 对每个约束,检查目前尺寸是否满足约束(跨行列尺寸 >= Max(DesiredSize, min.Sum())
      • 满足约束的忽略,不满足的约束需要计算约束大出行列的尺寸值,将此值设定为此 Auto 的待选长度
      • 当所有的约束检查完毕,在所有的待选长度中取最大值,设定为 Auto 的尺寸,排除此行列,然后从总长中将其减掉
      • 所有的 Auto 检查完毕后,退出循环
    5. 按照父级尺寸估算 * 的尺寸
      • 如果还有剩余长度,则将 * 展开,但需要考虑 * 行列的最小尺寸
    6. 确定 Grid 的 DesiredSize
      • 如果剩余总长 >= 0,则 Grid.DesiredSize = 可用长度 - 剩余总长
      • 如果剩余总长 < 0,则返回的 Grid.DesiredSize = 可用长度,实际需求的 Grid.DesiredSize = 可用长度 - 剩余总长
    7. 如果总长 >= 0,则进行循环(以确定剩余全部子元素的测量所用尺寸);否则直接将剩余 * 全部设置为 0
      • 进行循环
        • 计算单位星长(单位星长 = 剩余总长 / 星数)
        • 找出第一个不满足 max 要求的 *,置其长度为 max,排除此行列,然后从总长中将其减掉
        • 所有的 * 检查完毕后,退出循环
      • 至此,剩余的所有 * 都将不再有约束(即便元素 DesiredSize 不满足也无需处理,直接将元素裁剪)
        • 计算单位星长(单位星长 = 剩余总长 / 星数)
        • 计算所有剩余 * 的长度
      • 至此,所有子元素测量所用尺寸已经全部确定,使用此尺寸对子元素进行测量
    8. 分开保存 1~5、6 计算后的所得结果,布局过程即结束
  • 排列过程
    1. 如果排列可用尺寸大于测量可用尺寸,则测量过程中的全部计算部分需要重新进行(因为可能此前的 min 现在不满足条件)
    2. 如果排列可用尺寸等于测量可用尺寸,则直接使用测量第 6 步的结果,依次进行排列,不足部分的空间全部使用 0
    3. 如果排列可用尺寸小于测量可用尺寸,则重新执行测量第 6 步的计算,以确定新的行列尺寸,依次进行排列,不足部分的空间全部使用 0

我在 Avalonia 的代码注释中,画出了每一个步骤的变化图。

// 1. 测量行列范围中包含 `Auto` 或 `*` 的元素(前者影响行列和最小尺寸,后者仅影响最小尺寸)
//
// 2. 将所有的已确定尺寸确定
// +-----------------------------------------------------------+
// |  *  |  A  |  *  |  P  |  A  |  *  |  P  |     *     |  *  |
// +-----------------------------------------------------------+
//                   |#fix#|           |#fix#|
//
// 3. 将所有的有最小尺寸,且 `*` 展开后超过此最小尺寸的行列按最小值确定
// +-----------------------------------------------------------+
// |  *  |  A  |  *  |  P  |  A  |  *  |  P  |     *     |  *  |
// +-----------------------------------------------------------+
// | min | max |     |           | min |     |  min max  | max |
//                   | fix |     |#fix#| fix |
//
// 4. 将所有 `Auto` 行列确定
// +-----------------------------------------------------------+
// |  *  |  A  |  *  |  P  |  A  |  *  |  P  |     *     |  *  |
// +-----------------------------------------------------------+
// | min | max |     |           | min |     |  min max  | max |
//       |#fix#|     | fix |#fix#| fix | fix |
//
// 5. 按照父级尺寸估算 `*` 的尺寸
// +-----------------------------------------------------------+
// |  *  |  A  |  *  |  P  |  A  |  *  |  P  |     *     |  *  |
// +-----------------------------------------------------------+
// | min | max |     |           | min |     |  min max  | max |
// |#des#| fix |#des#| fix | fix | fix | fix |   #des#   |#des#|
//
// 6. 计算 `Grid` 所需的最小尺寸
//
// 7. 将估算缩得的尺寸作为实际尺寸进行测量
// +-----------------------------------------------------------+
// |  *  |  A  |  *  |  P  |  A  |  *  |  P  |     *     |  *  |
// +-----------------------------------------------------------+
// | min | max |     |           | min |     |  min max  | max |
// |#fix#| fix |#fix#| fix | fix | fix | fix |   #fix#   |#fix#|

布局算法的代码

为了让代码更容易调试,我专门写了一个 GridLayout 类来完成布局过程,而且 GridLayout 的计算设计为与 Grid 布局过程无关。做法是,将 GridLayout 的大部分方法设计为“纯方法”(纯方法只随便调用,调用此方法不会改变任何系统状态,只有拿到其返回值才会真正发挥作用)。

具体的代码非常长,含单元测试供 1200+ 行,建议去 Avalonia 仓库查看:

效果和性能

在性能测试中,此算法还是表现不错的,以下是 Pull Request 中的性能测试截图(已经合并)。

本文会经常更新,请阅读原文: https://walterlv.com/post/grid-layout-algorithm.html ,以避免陈旧错误知识的误导,同时有更好的阅读体验。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布,但务必保留文章署名 吕毅 (包含链接: https://walterlv.com ),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。如有任何疑问,请 与我联系 (walter.lv@qq.com)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wym

Bomb Catcher 游戏 (Pygame)

991
来自专栏Spring相关

Css权重解析

关于CSS权重,我们需要一套计算公式来去计算,这个就是 CSS Specificity,我们称为CSS 特性或称非凡性,它是一个衡量CSS值优先级的一个标准 具...

1362
来自专栏葬爱家族

Android高德之旅(8)绘制线废话简单的api总结

绘制线会比绘制点稍微复杂点,抛开一些复杂的属性不谈,主要分为三类:实线、虚线、纹理。绘制线在自定义地图中是非常重要的一个环节。

3455
来自专栏编程

你不知道的前端算法之热力图的实现

作者:TalkingData 李凤禄 本文为TalkingData原创,未经授权禁止转载。申请授权请在评论中留言联系! inMap 是一款基于 canvas 的...

7798
来自专栏深度学习之tensorflow实战篇

R语言高级绘图命令(标题-颜色等)

plot(x)          以x的元素值为纵坐标、以序号为横坐标绘图 plot(x,y)        x(在x-轴上)与y(在y-轴上)的二元作图 ...

6246
来自专栏jojo的技术小屋

原 CSS3 filter

作者:汪娇娇 日期:2016.10.9 其实之前几乎都没用过filter属性,就算知道也只是在脑中留了点浅浅的印象,直到最近因为项目的原因,才对filter进行...

2053
来自专栏用户2442861的专栏

Python PIL ImageDraw 和ImageFont模块学习

http://blog.csdn.net/dou_co/article/details/17618319

9652
来自专栏前端那些事

过渡与动画 - 逐帧动画&steps调速函数

上一篇中我们熟悉五种内置的缓动曲线和(三次)贝塞尔曲线,并且基于此完成了缓动效果.

900
来自专栏HTML5学堂

一步步教你弹性框架-上篇

HTML5学堂:本系列主要在于跟大家分享弹性运动框架的制作方式。弹性运动框架的运动方式类似于弹簧,有一种回弹的效果,在网站中的一些特效当中还是有一些应用的。实现...

3648
来自专栏工科狗和生物喵

【机器视觉与图像处理】基于MATLAB+Hough的圆检测

本次文章,没有太多好写的,就是最近做的一个机器视觉的课程设计作业,是要做一个流水线的生产线建模以及对于产品的检测识别,我个人承包了圆心半径检测的内容,熬了好几天...

2941

扫码关注云+社区

领取腾讯云代金券