图像布局优化
图像布局优化
提问于 2015-12-27 04:57:56
我需要在网站页面上用JavaScript优化布局图像，以便将空白的数量降至最低。
优化问题基本上是最小化以下内容：
(rightmost x-coordinate of an image - leftmost x-coordinate of an image) +
(bottommost y-coordinate of an image - topmost y-coordinate of an image)但是，任何图像都不能重叠，因此对每个图像的约束是：
for i in images
for j in each other image
(topmost coordinate of i > bottommost coordinate of j) ||
(bottommost coordinate of i < topmost coordinate of j) ||
(leftmost coordinate of i > rightmost coordinate of j) ||
(rightmost coordinate of i < leftmost coordinate of j)此外，还有一个约束，即任何图像的最右边的坐标不能大于页面的宽度，任何图像的最左边的坐标必须大于0。
首先，我考虑将其描述为一个线性规划问题，但我在JavaScript中看到的所有线性编程库都不允许这样复杂的约束，所以我认为这可能不是一个线性问题。
然后我开始把它想成一个动态编程问题，但我不确定如何在不尝试每种布局组合的情况下解决它，这将是非常慢的。
有人知道如何有效地解决这类问题吗？
回答 2
Stack Overflow用户
发布于 2015-12-27 05:15:15
我认为你已经遇到了cutting stock problem，这是NP困难的。我相信维基百科的页面上有一些启发式的次优解决方案，它们可能更适合你。
Stack Overflow用户
发布于 2015-12-27 06:37:05
事实上，这不能用纯粹的线性规划来完成。但是，可以使用额外的二进制变量(这将使其成为MIP -混合整数规划问题)或使用约束编程技术来制定无重叠约束。Here就是这些约束的一个例子。这个演示文稿Constraint programming in the browser也很有趣。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34475180
复制相关文章
相似问题
腾讯云开发者
