没有办法填补每列底部的空隙,因为砌体按垂直顺序对砖块进行排序,然后按水平顺序排列。它类似于装箱算法,具有一些类似于树图算法的附加数学。装箱算法的想法是最小化在柱中堆叠固定数量的砖所需的柱数量。这是一个 np 完全问题,自然在底部(或顶部)有空隙,而这些空隙无法填补。
对于树形图,您可以使用 kd-tree。一个很好的描述在这里: http: //www.blackpawn.com/texts/lightmaps/default.html。
{
Node* child[2]
Rectangle rc
int imageID
}
Node* Node::Insert(const Image& img)
if we're not a leaf then
(try inserting into first child)
newNode = child[0]->Insert( img )
if newNode != NULL return newNode
(no room, insert into second)
return child[1]->Insert( img )
else
(if there's already a lightmap here, return)
if imageID != NULL return NULL
(if we're too small, return)
if img doesn't fit in pnode->rect
return NULL
(if we're just right, accept)
if img fits perfectly in pnode->rect
return pnode
(otherwise, gotta split this node and create some kids)
pnode->child[0] = new Node
pnode->child[1] = new Node
(decide which way to split)
dw = rc.width - img.width
dh = rc.height - img.height
if dw > dh then
child[0]->rect = Rectangle(rc.left, rc.top,
rc.left+width-1, rc.bottom)
child[1]->rect = Rectangle(rc.left+width, rc.top,
rc.right, rc.bottom)
else
child[0]->rect = Rectangle(rc.left, rc.top,
rc.right, rc.top+height-1)
child[1]->rect = Rectangle(rc.left, rc.top+height,
rc.right, rc.bottom)
(insert into first child we created)
return Insert( img, pnode->child[0] )
您的 htmlx 和 html5 填充问题的问题很容易解释。你有一个 padding:8px; 在 html5 文档的 body 标记中。所以图像和周围图像之间每边都有 4px 的间隙。看我的图片: