我有一些需要渲染到
HTML5画布上的对象.我的输入是轴对齐边界框的有序列表.这些箱子经常重叠,但也经常留下大面积的空白空间.
我想最大限度地减少画布表面积,我必须创建,以正确的顺序渲染所有这些项目,而不必在多个画布上渲染单个对象的部分(从而阻止简单的解决方案创建画布紧紧地适应所有占据的空间).
所以基本上,我想要将一组对象全部渲染在同一个画布上,而不重叠的对象应该在单独的画布上呈现.但并不是所有的重叠对象都应该在单个的画布上呈现 – 例如,一个非常高和非常宽的对象,它们稍微重叠以形成一个L,仍然应该被渲染在两个独立的画布上,因为它们组合会导致很多浪费的画布空间在L.的开放部分.
维护Z订单也会导致一些困难的情况.例如,以下图像表示一个潜在的布置：
在这种情况下,您可能希望将蓝色和绿色层合并成一个单一的画布,但是如果没有包含红色图层,则无法生成正确的分层,最终会造成大量的死空间.
但是,您也不能仅限制组合层与Z顺序连续的项目. Z顺序可能与上述图像相同,但红色项可能与其他图像不重叠,在这种情况下,您需要组合蓝色和绿色层.
我正在努力为这个问题提出一个很好的算法.任何人都在关心？
解决方法
这是一个简单的建议,这可能不会解决一些角落的情况,但至少部分解决它,并希望建议一个更好的解决方案：
a = <a z-ordered list of the objects> ;
b = [];
bounds = null;
objects = [];
while ( a.length > 0) {
c = a.pop();
if( <c overlaps bounds> && <area of combined canvases> < <area of seperate canvases> || bounds === null) {
objects.push(c);
bounds = <union of bounds and c,or bounds of c if bounds is null>;
} else {
b.push(c);
}
if( a.length === 0) {
a = b;
b = [];
<do something with the current bounds and objects list>
bounds = null;
objects = [];
}
}
哪里
< area of combined canvases> = sum( < area of each canvas> ) - sum( <interesections> ) < area of seperate conavases> = sum( < area of each canvas> )
这不会捕获两个相交对象的两个不相交的对象的情况,但是可能会通过在每次迭代中回顾所有较低的z顺序对象来改进这些对象.
