转载

如何实现一个不规则排列的图片布局算法

一直在 500px 上看照片，发照片。以前看它的首页图片展示就只是觉得好看，洋气，也没想过自己在iOS上实现一下。昨天不知怎么的就开始想其中的算法了，现在我把思考的过程在这里贴出来分享一下，如果你有更好的算法欢迎探讨。

最终我做出的效果是这样的：

垂直滚动

如何实现一个不规则排列的图片布局算法

水平滚动

如何实现一个不规则排列的图片布局算法

算法总体思路

先说一下总体上的思路。既然图片的大小、位置各不一样，我们很自然地会想到需要算出每个item的frame，然后把这些frame赋值给当前item的 UICollectionViewLayoutAttributes 。

自定义 UICollectionViewLayout 的关键两步是先后重载下面两个方法：

- (void)prepareLayout;

和

- (NSArray *)layoutAttributesForElementsInRect:(CGRect)rect;

所以我们的思路是在 - (void)prepareLayout; 方法中算出所有item的frame，并赋值给当前item的 UICollectionViewLayoutAttributes 。用图片的形式比较直观：

如何实现一个不规则排列的图片布局算法

接下来问题就化归到了如何求每个item的frame。

这里我们抽象出一个 列 的概念：

如何实现一个不规则排列的图片布局算法

除此之外，我们还需要维护一个存储高度的数组 COLUMNSHEIGHTS 。数组中有 n 个元素， n 表示所有列数，如上图，n = 3。缓存的值表示当前列的高度，上图的例子中， COLUMNSHEIGHTS = [104,123,89] 。

然后我们把item逐个放入列中，以这样的规则：从左到右，item优先放入 COLUMNSHEIGHTS 中最短的列。

打个比方，下一个item就应该放入最短的列，也就是第三列:

如何实现一个不规则排列的图片布局算法

以此规则，循环下去，直到所有item都放置完毕。

细节

item.frame.origin:

用自然语言描述，

坐标x应该是这样的: （最短列的编号-1）x 列宽

坐标y应该是这样的: 从 COLUMNSHEIGHTS 中取出最短列对应的高度

所以我们需要一个算法来找出当前 COLUMNSHEIGHTS 中的最短的列，最直接的方法就是0(n)时间复杂度的循环比较，这里还好因为数据量比较少，如果遇到数据量大的情况可能就需要考虑分治法了。

//寻找此时高度最短的列.第一列为0 -(NSUInteger)findShortestColumn{  NSUInteger shortestIndex = 0;  CGFloat shortestValue = MAXFLOAT;  NSUInteger index=0;//游标  for (NSNumber *columnHeight in self.COLUMNSHEIGHTS) {   if ([columnHeight floatValue] < shortestValue) {    shortestValue = [columnHeight floatValue];    shortestIndex = index;   }   index++;  }  return shortestIndex; }

找到了最短列，表达出item的x坐标和y坐标就很容易了：

NSUInteger origin_x = [self findShortestColumn] * [self columnWidth];  NSUInteger origin_y = [self.COLUMNSHEIGHTS[shtIndex] integerValue] ;

item.frame.size.width:

由于列数是有用户决定的，所以是个变量，由此可以获得列宽 columnWidth = self.collectionView.bounds.size.width / self.columnsCount

然后我们规定，默认情况下item的宽度等于 columnWidth 。当满足当前列和下一列(如上图红色方块，就是属于当前列位于列2，下一列列3)高度相等时，可以横跨两栏。(再看红色方块，因为在它放进去之前，第二列高度为0，第三列高度也为0，满足横跨的条件)

但是！

如果出现了下面的这种情况：

如何实现一个不规则排列的图片布局算法

也就是说，单单满足 当前列和下一列 高度相等还不够，因为只要一旦满足这个条件，接下去将会一直是横跨的状态。所以我们还需要再加一个条件来筛选这些即使满足 当前列和下一列高度相等 的item。我们可以用随机数：

NSUInteger randomOfWhetherDouble = arc4random() % 100;//随机数标记是否要双行

arc4random() % 100; 会随机生成一个0～100的整数。然后我们设定一个阈值，比如 40 .只有当同时满足 当前列和下一列高度相等 和 randomOfWhetherDouble < 40 的item才能真正实现跨行。换句话说，即使当前列和下一列高度相等，也只有百分之40的几率出现跨行的item，这样就很好的保证了宽度不一的item随机出现！

所以宽度的代码是:

        if (shtIndex < self.columnsCount - 1 && [self.COLUMNSHEIGHTS[shtIndex] floatValue] == [self.COLUMNSHEIGHTS[shtIndex+1] floatValue] && randomOfWhetherDouble < 40) {              size_width = 2*[self columnWidth];          }else{              size_width = [self columnWidth];         }

item.frame.size.height:

这个可以自由规定，因为在竖直方向高度没有特别的限制。比如我规定：

1.如果是横跨的,高度＝宽度 * (0.75~1随机)

float extraRandomHeight = arc4random() % 25;   retVal = 0.75 + (extraRandomHeight / 100);   size_height = size_width * retVal;

2.如果是单列的，高度＝宽度 * (0.75~1.25随机)

float extraRandomHeight = arc4random() % 50;   retVal = 0.75 + (extraRandomHeight / 100);   size_height = size_width * retVal; // 高度为宽度的0.75~1.25倍

补充：

实际测试中发现，即使把出现横跨item的阈值调成0，也就是只要满足 当前列和下一列高度相等 ，100%出现横跨的情况，出现横跨的情况也是少之又少。为什么呢？原因出在了数据类型上，之前我的用的数据类型全是 CGFloat 或者 float 的浮点类型，两个浮点数要相等的概率可想而知。改成 NSUInteger 之后就好多了。除此之外，为了增加横跨情况出现的概率，我还用到了 四舍五入 。拿图举个例子：

如何实现一个不规则排列的图片布局算法

我们让item的高度对某个整数取余，比如以40为单位，让高度对40取余，再让item的高度剪掉这些余数。剩下的高度肯定是40的整数倍。

代码很简单：

size_height = size_height - (size_height % 40);

这可以把某个范围内的高度都归约到用一个高度，也就让左右两列高度相等的概率增加了，出现横跨item的可能性也变大了。

然后，在循环的过程中把每个item的frame赋值给对应的attributes,并把这些attributes保存到一个数组里。

//给attributes.frame 赋值，并存入 self.itemsAttributes NSIndexPath *indexPath = [NSIndexPath indexPathForItem:i inSection:0];   UICollectionViewLayoutAttributes *attributes = [UICollectionViewLayoutAttributes layoutAttributesForCellWithIndexPath:indexPath];   attributes.frame = CGRectMake(origin_x, origin_y, size_width, size_height);   [self.itemsAttributes addObject:attributes];

然后在 layoutAttributesForElementsInRect 方法中返回：

- (NSArray *)layoutAttributesForElementsInRect:(CGRect)rect{     return self.itemsAttributes;  }

最后

为了能让collectionView滑起来，我们还需要设置它的 ContentSize .其实只要让ContentSize的高度变成 COLUMNSHEIGHTS 中最长列的高度即可。至于这个求数组中最长列的算法，和前面的求最短列类似。

-(CGSize)collectionViewContentSize{  CGSize size = self.collectionView.bounds.size;  NSUInteger longstIndex = [self findLongestColumn];  float columnMax = [self.COLUMNSHEIGHTS[longstIndex] floatValue];  size.height = columnMax;  return size; }