把几张图片铺满一个矩形区域，有什么好的算法可以用？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 3718 天前的主题，其中的信息可能已经有所发展或是发生改变。

条件：
图片数量不固定（ 3-9 张）
每张图片宽高已知（长短边比例在 16:9 ~ 1:1 之间）

目标：
尽量让图片宽高比变化最小（不要裁剪掉太多）
也尽量让各图片尺寸保持均匀（不要有些特别大，有些特别小）

伤脑筋~~

第 1 条附言 2015-10-14 12:29:56 +08:00

就是类似下面的效果，只是这种布局最好能用算法算出来。

图片

高比

伤脑筋

矩形

27 条回复 2015-10-15 00:52:32 +08:00

hellov22ex

2015-10-14 11:28:02 +08:00

瀑布流？

如果是，就控制它们间的缝隙

如果不是，这样子好看？

pubby

2015-10-14 11:34:32 +08:00

@hellov22ex 不是瀑布流。

就是少量的几张照片做一个合集的样子

pubby

2015-10-14 11:37:09 +08:00

@hellov22ex 目前想到的是
每种照片数量，定义几个平铺模板，然后挑选尺寸最合适的照片依次填充

不过，应该还有更智能的算法吧？

shuiniushushu

2015-10-14 11:44:12 +08:00

还是要预先定好布局才好弄，不然算法得很复杂。如果是一次性的就手工排吧

imn1

2015-10-14 11:47:24 +08:00

算法不清楚，个人觉得只是尺寸不会太难
这样的软件已经有不少了

pubby

2015-10-14 11:47:50 +08:00

@shuiniushushu 嗯，暂时方案是设计几套模板，挑最合适的套用。

只是看看有没有更优雅智能的方案

zzetao

2015-10-14 11:47:55 +08:00

网易云音乐的歌单封面只显示 4 张图片铺满一个矩形

歌曲少于 4 条，歌单封面默认显示最新一条歌曲图片
歌曲大于 4 条，歌曲封面显示最新 4 条歌曲封面，也就是这样子：
http://p3.music.126.net/caZ2Ny7buMH4lVQOEDbKBQ==/3370003140324210.jpg?param=200y200

pubby

2015-10-14 11:50:14 +08:00

@zzetao 这个。。。。有点单调

tan90ds

2015-10-14 11:56:12 +08:00

http://www.pixiv.net
我不能回答楼主的问题，但是这个网站的首页似乎是楼主想要的效果（刷新几次再看看）。
也许是用 js 实现的？

pubby

2015-10-14 12:01:06 +08:00

@tan90ds 谢谢。它这个每行等高的，而且每行宽度并不严格相等，处理起来稍微容易点。

tan90ds

2015-10-14 12:05:02 +08:00

@pubby 如果你要完全实现你描述的效果的话，恐怕得找个玩 OI/ACM 的人来设计一下算法。

imn1

2015-10-14 12:28:59 +08:00

其实二维+可以缩放 /裁剪就很好做的
规则就两条：
1.长边和与宽边和趋向接近容器的长边与宽边
2.总面积趋向接近容器的面积

几个思路：
1.人类思维（填充）
先放入大面积，再放小面积，缺点是会头重脚轻，大面积会集中在某一端
2.演变填充
容器比较大的话，把容器分为分布均匀的小容器，每个小容器按上述 1 填充
3.计算机穷举
在允许缩放的范围内，计算所有图片的单边长和面积，依据两条规则排除不合适的
4.中心逼近
按边长先填入四周，中心部分以缩放调节
5.数学算法
请搜索“多边形填充算法”
6.视角、美学算法
不详，除了填充还要讲究排版的美学

pubby

2015-10-14 13:00:35 +08:00

@imn1 谢谢。看来不是几行代码可以搞定了 -_-

irainy

2015-10-14 13:10:19 +08:00

搜一下： rectangle packing algorithm

undeflife

2015-10-14 13:47:15 +08:00

http://miromannino.github.io/Justified-Gallery/

yellowV2ex

2015-10-14 13:47:45 +08:00

比如 google 的图片搜索，其实是 Aspect Fill ，也就是说缩略图的尺寸比例并非原图的比例，每排算一下数量，然后把多出来的宽度差平均或者放到影响最小的几个缩略图上就好啦。横竖混排的话计算一下双倍差最小的排到一起。

canesten

2015-10-14 13:48:50 +08:00

直接给你介绍工具可以吗？

braineo

2015-10-14 14:12:27 +08:00

是 exact cover problem 吗？
是的话可以 dancing links 跟 algorithm X

pubby

2015-10-14 15:06:03 +08:00

@irainy
@braineo 除了排列，还有图片的裁剪和缩放，才能最后铺满不留缝隙。

pubby

2015-10-14 15:09:44 +08:00

@undeflife
@yellowV2ex 他们是分成水平多行，然后行内调整。

ybh37

2015-10-14 15:45:14 +08:00

先设置几个模板，将所有的图片按宽高比例适配加载后再等比缩放。

canesten

2015-10-14 15:53:57 +08:00

楼主是指 HTML 页面布局上的解决方案？

pubby

2015-10-14 16:29:00 +08:00

@ybh37 嗯，这是简单的实现方案。

@canesten 不限制在 HTML ，只是算法，最后只要得到每张图的位置和大小即可

canesten

2015-10-14 16:32:40 +08:00

那直接 texture packer 就完了嘛
https://www.codeandweb.com/texturepacker

zongwan

2015-10-14 20:49:58 +08:00

MaxRects
Rectangle Bin Packing
http://clb.demon.fi/projects/rectangle-bin-packing/
之前在做 as3 的时候做过 sprites 工具时研究过

网上有源代码
大概五种算法最后一种很慢
NP 问题效果不一
按一定规则排序(个人经验不公开)放入图片可固定得出近似最优解
随机图片顺序生成的结果随机

ccswizard

2015-10-14 22:24:30 +08:00

装箱算法？

pubby

2015-10-15 00:52:32 +08:00 via Android

@zongwan 谢谢，我去看看