#### Some notes on my implementation of "The Bottom-Left Bin-packing Heuristic: An Efficient Implementation" by Chazelle.

(This post didn't end up as polished or complete as I'd hoped, but posting it anyway in hopes it will be useful next time I look at the code.)

##### General comments

I suspect the proof of O(N^2) in the paper isn't quite correct, though
not sure it affects the results. In the explanation of `QWi`

, it says

Thus, it is important to know which obstacles the right part of the device can encounter when this part starts leaving the subhole and the device is still partially inside it. Since both upper- and right-notches are ruled out,

`QNi`

as defined, is the first and only possible obstacle which will stop the motion of the device.

First, that `QNi`

seems to be a typo in the paper and should be `QWi`

,
but in that case there are 2 problems, shown in the following image:

The first problem is that it is ambiguous which point should actually
be `QW1`

, `A`

or `B`

. If `QW1`

is at `A`

, the edge below `A`

is too
low to actually block anything in subhole `L1`

. If it is at `B`

, it is
also `QW2`

, and we can't make a single link back from `B`

to a `Q`

node.

The other problem is that `QWi`

doesn't always stop the device, and in
some cases it might need to raise and continue. In the example, there
are 3 rectangles which start inside subhole `L1`

and extend past
either possible `QWi`

. In 2 cases, the rectangles are only supported
from below by lower notches outside the subhole (`N3`

or `N4`

). Both
are valid "bottom left" placements, so should be found either while
searching subhole `L1`

or `L3`

.

To find them from `L1`

, we need to extend `FB(L1)`

to include `N2-4`

as well as the rightmost edge. In that case, they also need to be
included in `FB(L2)`

in case they are the bottom support of a
placement supported on the left by a vertical edge right of `QN1`

inside subhole `L2`

.

To find them from `L3`

, it would need to include the entire top edge
starting from `L1`

in `FT(L3)`

instead of starting at `L3`

, which
doesn't match my understanding of the algorithm.

In either case, it seems like it potentially has to look at some edges more than once per placement. Not sure if the number of those edges is enough to affect the proof of O(N) work per placement or not.

##### Heuristics

The paper mentions that it works for heuristics that preserve
`bottom-left stability`

, where a placement can't move downwards or
leftwards, and the placements it generates fit that restriction. I
think this can be expanded a bit, in that the data structures work for
placements where there is non-zero contact on at least one edge at the
bottom left corner even if it could slide along that edge. I think the
algorithm could be extended to generate ranges of such placements
instead of strictly "bottom left" placements, though not sure if a
heuristic could efficiently make use of that ability. It still might
be interesting because the popular `maxrects`

algorithm can generate
those placements, so it would allow directly comparing the space/time
complexity of the 2 algorithms with the same set of placements.

The available data for a heuristic with this algorithm is different
from that provided by `maxrects`

, so we can't directly use most of the
popular `maxrects`

heuristics.

(A Thousand Ways to Pack the Bin - A Practical Approach to
Two-Dimensional Rectangle Bin
Packing)[https://raw.githubusercontent.com/juj/RectangleBinPack/master/RectangleBinPack.pdf]
by Jylänki lists a few options for `maxrects`

heuristics:

`Bottom left`

works directly with Chazelle's algorithm.

`Contact Point`

aka `Touching Perimeter`

translates well to the data
structures stored by Chazelle's algorithm, and is what I am using. I
think calculating full contact length for every potential placement
might add an extra factor of `O(N)`

in worst case (consider placing a
sequence of sets of `N`

squares of size `1/N`

, where each set of `N`

squares divides the lower left edge into increasingly finer
stair-steps, so there are always `O(N)`

potential placements.) In
practice, tie-breaker heuristics can be tuned to discourage worst-case
behavior, and due to the properties of the holes in ```
bottom-left
stable
```

placements we can usually avoid a full search of the hole (for
example when searching clockwise, once we go strictly past the top of
the placement there can be no more intersections until a ```
falling
corner
```

or right edge. Similarly searching counter clockwise there can
be no more contacts once strictly past right edge. In both cases, `Q`

links can also be used to avoid searching the entire edge.)

It might be worth adding a partial contact version, only comparing the contacts adjacent to the lower left corner of the placement, since that can be calculated (with a bit of extra data in the edge descriptions) in approximately constant time instead of O(N) for full contact.

`Best Area Fit`

, `Best Short Side Fit`

, and `Best Long Side Fit`

all
compare the rectangle being placed to the "maximal rectangle" being
considered, so can't be applied directly, but might be useful with
some modifications. If we track bounds for each hole/subhole (useful
for quick rejection of small holes anyway), we can apply the
heuristics to the bounding rectangle, though it probably wouldn't give
as good results as in `maxrects`

.

If also we maintain actual available area in addition to bounds (which
should be trivial in the case where a hole isn't split into multiple
holes, and i think still O(N) when it is split?), `Best area fit`

would probably be useful.

Similarly, we could compare the length of the short or long dimensions of the rectangle to the length of the corresponding edge(s) supporting it.

In some cases, particularly for unsorted/online packing, it is
probably also worth comparing the sizes of the holes being
considered. Either a `Pick Smallest Hole First`

or modified ```
Best Area
Fit
```

that maintained a total available area for each hole would make
it less likely for a small rectangle to break up a large hole in a way
that prevents fitting a later large rectangle there.

##### Bin shaping/sizing heuristics

For my main use (texture/font atlases) there is usually a strict upper bound for bin size, but it is frequently much larger than the actual size needed by the rectangles being packed. For example max texture size might be 16384x16384, while a particular font atlas might only need 2000x2000 or so. In that case, many heuristics would pack along bottom and left edges leaving the middle and upper right empty. To avoid that, I add an extra "shaping" heuristic, that adds a penalty to placements depending on how much unused space they would add to the bounds of the active placement area. This can be tuned for various common texture use cases like "must be power of 2 dimensions" required by older hardware, "must be multiples of 4 or 16" for various texture compression formats, or "increase in 256 x 256 blocks" for sparse texturing.

Starting from an active area of 1x1 tends to restrict placements too
much, affecting efficiency. starting with an initial estimate of
`sqrt(total-pixels)`

for offline packing seems to give reasonably good
results. If efficiency needs to be maximized, a few initial sizes
between that and the actual size found can be tried.

##### Hole vertices

The vertices of a hole are stored as a doubly linked list in clockwise
order, with no intersecting edges. Each vertex stores `x`

and `y`

coordinates, `previous`

and `next`

links, and optional `q`

flag and
`w`

,`n`

links.

`N`

and `W`

links point from a `Qi`

node to corresponding `QNi`

or
`QWi`

node, or from `QNi`

/`QWi`

back to corresponding `Q`

node.

`Q`

flag indicates whether a node with `N`

or `W`

set is `Q`

or `QN`

/`QW`

.

Special vertices (leftmost edge, left notch or rightmost edge, falling corners) store links back to the corresponding subhole/hole to make it easier to detect which are affected by a given modification.

Additionally, some extra metadata is stored to make it easier to traverse the edge correctly, describing what type of vertical edge the vertex is on, and where.

Possibly should add an extra link from the upper right corner of lower notch to the vertical edge right of that vertex, to optimize finding the lower notches that could support a placement in a particular subhole, though I think that just affects the constant factors, and not overall time complexity.

##### Subholes / F data structure

For each `leftmost edge`

in a hole, we have a `subhole`

, which
together partition the hole into "nice" areas (plus some extensions).

Each subhole contains a `top`

and `bottom`

edge, both stored as a
sequence of `x`

and `y`

values corresponding to the start point and
the tops of each vertical edge in the (extended) subhole.

For the `top`

edge, we also need to handle the problem of vertical
edges possibly being discontinuous if they contain one or more `Q`

vertices.

In this example, placements `1`

,`2,`

4`are valid for subhole`

A`.`

3```
and
```

5```
are not valid (though there may be a valid placement for
subhole
```

B`or`

C```
), though 3 could be a valid place for a taller
rectangle. To differentiate them, we either need to store 2 vertical
edges (
```

L1`and`

L2`) with the same`

X`coordinate in the`

top```
edge
for subhole
```

A`, or a single vertical edge with 2 gaps (`

G1`,`

G2`).

While gaps could be tracked by including multiple vertical edges with
the same X value, `D`

is stored as horizontal edges, so it would need
to combine them into something similar to the list of gaps anyway.

The actual top or bottom edge can be reconstructed by forming a
horizontal edge from `xn`

,`yn`

to `xn+1`

,`yn`

then a vertical edge
from that to `xn+1`

,`yn+1`

.

In addition to the `top`

/`bottom`

edges, there are links to the
containing hole, a falling corner if any, and `start`

and `end`

vertices. `Start`

is the lower vertex of the `leftmost edge`

, and
`end`

is either the `Q`

vertex or the lower vertex of the ```
rightmost
edge
```

of the subhole.

`X`

coordinate of `end`

vertex, and dimensions of bounding box are
also stored for optimization.

##### Constructing (extended) subholes

example image based on figure 6 from the paper, with an extra `lower notch`

:

The main hole is drawn in red, with dots at vertices. Each subhole is
drawn in different colors with a different offset up and to right of
the corresponding parts of the main hold. The extension of the subhole
is drawn in a darkened version of the subhole's color. ```
Leftmost
edges
```

are marked `L1`

- `L4`

, along with corresponding `Q2`

- `Q4`

points. Dots mark places we need to check for a given subhole when
placing an object in that subhole.

To build the top/bottom edges, we walk the doubly linked list of
vertices starting at the corresponding part of the `leftmost edge`

for
that subhole, forwards for top and backwards for bottom, looking at
each vertical edge. When walking forwards, we follow all `Qi`

->`QNi`

links. When walking backwards, we follow `Qi`

->`QWi`

links. In both
cases, we stop when we see a horizontal edge going towards the left.

For the bottom edge, we collect upwards edges until we hit a `Qi`

point, then we only collect upwards edges with y values greater than
previous Y value. If the `Qi`

->`QNi`

span is completely blocked by a
`lower notch`

to the right, we note that and use that as the right
edge of the subhole, and also note that any `falling corner`

in the
hole can't affect that subhole.

For the top, we collect upwards edges and downwards edges until we hit
the first `QNi`

vertex, then we only collect downwards edges that
cross lower than the `QNi`

vertex, stopping at any early right edge
detected while building bottom edge.

For example, in subhole 2 (`L2`

, green), the top edge follows `Q3`

and
`Q4`

, and end above `Q2`

, keeping part of the falling edge in the
darker extension. The bottom edge follows both sides of lower notch
`N1`

, and ends at `Q2`

, with extension only following the rising side
of lower notch `N2`

.

Note that we need to be careful at `p1`

, since anything supported by
`N1`

or `N2`

should be at `p2`

in subhole 3, since it can move
left. We still need to check the 2x7 space at `p1`

before `N1`

though,
since that is in subhole 2. At `p3`

, anything supported by `N2`

is
still in subhole 2, since it can't move left into subhole 4.
Similarly, we can't place anything in subhole 1 at `p4`

supported by
`N2`

, since it could move left to `p3`

(and possibly down from there,
depending on how wide it is). The `gap`

values are used to check for
that problem.

Subhole 3 (`L3`

, magenta) ends at or above `Q3`

, with top extension
skipping the falling edge, and lower extension raising at `N1`

and `N2`

.

I don't quite understand how the paper handles cases like `N2`

blocking placement into the `leftmost edge`

at `L3`

, since it sounds
like it stops at `QW2`

, and doesn't include `N2`

in subhole 3 at
all. We need to be able to place a 19x1 piece at L3, and fail to place
a 22x1 wide piece there, and also need to be able to place a 22x1
piece at `p2`

supported by `N2`

, which it seems would be missed with
`BOTTOM(B)`

as described, though i may be missing something.

##### Calculating D list for a given length

Actual placement uses 2 data structures `C`

and `D`

specialized for a
particular subhole and width `L`

, containing horizontal spans where
the upper or lower left corner of a box could be packed.

D is the list `FT`

of top edges, and mostly corresponds to the
upper-left corners of the top edge of the subhole.

###### Simple subholes

For subholes without a "falling edge", the calculation is simplified
to just return the horizontal edges bounded by `FT`

. This includes
some space that isn't actually a valid placement in the cases where
`L`

would extend past the right edge of the subhole. This doesn't
matter since the lower list `C`

is also bounded by the same edge, so
would prevent any placements at invalid positions.

The above shows examples of the simple case, with `L = 4`

, with D
shown in red above the subhole, and valid placements shown in green
inside the subhole. Orange lines extending past edge of subhole
indicate invalid placements that would be rejected by corresponding
`C`

data structure.

###### Subholes with a falling edge

For subholes with a "falling edge", we need to account for situations
where there isn't enough space to place something of width `L`

left of
the falling edge, while keeping the space under the falling edge
available.

The above example shows some of the cases we need to look at for the complex case, again with red lines above marking the edges in D (with vertical line indicating a 0-width segment), and green indicating the corresponding placement. Note that we sometimes have duplicate positions with different height. In the 3rd example on bottom row, note that it is 3 placements, with the first and last adjacent.

Bottom row is the examples from Fig 12. in the paper, with additional
examples of the special case where the falling edge exactly lines up
with a preceding edge with a gap equal to or narrower than `L`

, or
where there is an exact fit in a span.

Top row shows various simplified versions of them.

In the top row, we have the following cases:

- Doesn't fit at all.
- Hits falling edge before next span.
- exactly fits in next span, then hits falling edge (note 0-length span in output)
- fits in next span, with range of movement = 1, falling edge narrower than
`L`

- fits in next span, with range of movement = 1, falling edge equal to
`L`

- fits in next span, with range of movement = 1, falling edge wider than
`L`

In all cases, we can allow the span under the falling edge to extend
to the right edge of the subhole for the same reason as the simple
case, since the lower `C`

data structure will reject anything too far
to the right.

In the bottom row, we have the following cases:

- 12a fits in current span, hits falling edge before next span
- 12b fits in current span without hitting falling edge, doesn't fit in next span, but fits under falling edge
- fits in current span, which exactly lines up with falling edge with
gap
`L`

, exactly fits in next span. 3 spans in`D`

, middle one 0 width, first and 3d lined up in Y with 0-length gap. - fits in current span, which exactly lines up with falling edge, gap less than
`L`

. 1 span covering both, or 2 spans with 0-length gap, - 12a with exact fit in current span
- same thing with previous span shown

###### implementation

Input for procedure `TOP`

is the width `l`

of the block to be placed,
and the list of vertical edges `FT`

, as pairs `Hn`

,`Dn`

, where `n`

is
from `0`

to `p`

, `Hn`

is directly above `Dn`

, and `X`

values increase
with `n`

. We also pass a flag `falling`

indicating whether `FT`

has a
falling edge, and the X coordinate `end`

of the right edge of the
subhole if it is extended. Checking `end`

lets us avoid storing

For the simple case, on the left in image above, most edges `dn:hn`

(`n>=1`

) are included in output as horizontal edges `hn-1:dn`

. The
final edge is `hp-1:hp`

.

For the case with a falling edge, on right in image above, we have to
check for intersection with `dp-1:hp-1`

before adding a particular
`hn-1:dn`

pair.

To simplify the logic, we start by checking for `l`

not fitting in the
hole at all.

If `l`

fits between `d0`

and `dp`

, we have space for at least 1 span,
so we can add `h0`

, and start looping through points `dn`

(`n < p-1`

).
At each `dn`

, we test to see if `(<= (+ (x dn) l) (x dp-1))`

. If so,
we can fit a span at `dn+1`

, so we add `dn`

(as end of horizontal span
from `hn-1`

added previously) and add `hn`

as start of next span, and
continue loop.

If the next span doesn't fit, we need to check for following options:

falling edge is below current edge. (fig 12a)

In this case, we finish the current span at

`(- (x dp-1) l)`

,`(y dn)`

, and add a span under the falling edge from`(- (x dp-1) l)`

to`(x dp)`

.`(- (x dp-1) l)`

should be at least as large as`(x n)`

if we haven't made any mistakes, but they might be`=`

if the span's width is exactly`l`

.falling edge is exactly same height as current edge

In this case, the span can continue until

`(x dp)`

since the support continues from the current edge to the bottom of the falling edge.falling edge is above current edge. (fig 12b)

In this case, we finish this span as normal, then find the vertical edge

`dn2`

left of the falling edge, and if there is at least`l`

between that and`dp`

, add a span under the falling edge, from`(x dn2)`

,`(y dp-1)`

to`(x dp)`

##### Calculating C list for given length.

`C`

is the parts of list `FB`

of bottom edges which could support a
placement of width `l`

.

In addition to the details in the paper, we also store a flag indicating whether a given point is a "bottom left" corner, an "open" point, or "normal".

"Bottom left" is set for the first span, and when the preceding span
is higher than the current span. When set, we have a support to the
left of the span in `FB`

, and can place something at that exact
coordinate if there is enough vertical space.

"Open" is set at the beginning of spans that start `l`

before a
support, and at the end of spans that reach the end of the support. If
a point is marked "open", we can't place anything exactly at that
point since it isn't actually supported.

If a span isn't started with a "bottom left" point, we can't place
things along the span unless supported to the left by an edge from
`FT`

(taking into account that gaps left by subholes can't support the
left edge).

###### "horizontal edges" in `setup`

The paper describes the horizontal edges handled by `SETUP`

as "an
ordered list of its horizontal edges {(lk,rk}), with the
correspondence rk = hk+1". This isn't quite clear about what happens
to the edges followed by a rising vertical edge (`li-1`

in fig 11.c,
if there is a rising edge at `i`

, where `rk`

would have to be `di`

=
`dk+1`

).

It looks like "rk = hk+1" is true for all of the edges we care about, except for possibly the last one, so we may need to handle that one specially.

In Fig 11.d, if the edge at `end`

were falling, or further to the
right, we would need to add the span before it since it might be able
to fall from `s3`

in that case (and since setup doesn't pay attention
to `X`

values, it always needs to add it)

TODO: images for above?

TODO: figure out if there are any additional things to note about C.

##### Placing

Not sure if I changed other parts too much, or just don't understand
the algorithm for `PLACING`

in the paper. Doesn't look too hard to
rewrite from scratch though.

Our inputs are the height `h`

to be placed, and lists `C`

and `D`

containing places where the specified width fits in the bottom and top
respectively of the subhole.

Both should start at same `x`

value. Probably with `(y D) > (y C)`

depending on how `TOP`

and `BOTTOM`

were implemented, though we won't
rul out starting at same y value for now.

The first possible placement is at the left of the first segment of
`C`

, which is valid iff `(y D) - (y C) >= h`

.

If we place something there, any other placement on that span is
invalid since it could slide to the left (we know from proof in paper
that there are no `upper notch`

edges in the hole, so there can't be
an obstructions at the top that would allow it to sit on that span but
still be blocked from sliding left). In that case, we can move to the
next span on the bottom edge, skipping any spans from top edge with
lower `x`

value. From there we restart checking distance between `C`

and `D`

at that point.

If we can't place something at the left of the span, we need to follow the 2 edges until either we hit the end or there is enough space for the placement.

At that point, we need to do some extra checks to determine if that
placement is valid, since there can be gaps in the left edge
represented by the top edge (if there was a subhole removed from that
edge). If the entire `h`

fits within a gap, the placement is invalid,
otherwise we add the placement. In either case, we skip to next span
on bottom edge, advance top to match, and restart checking the
distance between `C`

and `D`

.

There are some edge cases we need to be careful about, due to `<`

vs
`<=`

and similar.

Given 3 spans `I`

,`J`

,`K`

on the bottom edge, consider placing at `J`

.

If

`I`

is lower than`J`

, we can't place something exactly at the start of the span. If`I`

doesn't exist or is higher, we can place something exactly at the start of the span.If

`K`

is higher than`J`

, we can place something exactly at the end of the span, but if`K`

is lower, we can't.

On the top edge, we only look at the left edge (`TOP`

doesn't
calculate right edges accurately), and can always place exactly at the
start of the span.

#### dynamic updates of data structures

I ended up skipping dynamic update of individual subholes for now, and
just rebuild all subholes for any hole that is modified. I think it is
still `O(N)`

, just tends towards the worst case compared to partial
updates. Seems to still perform reasonably well though.

If we rebuild the subholes and related data structures from scratch every time, that just leaves updates to the actual hole data structure.

Since I calculate the intersection of the placement and hole for the
placement heuristic, the intersection calculated there is stored and
used to update the hole geometry as well. The intersection is stored
as a set of contiguous `contact`

and `gap`

spans along the border of
the placement.

With that representation, there are 3 cases to consider:

If there is a single

`contact`

span with no`gap`

, we completely filled a hole and can remove it from the active list.If there is a single

`gap`

span (which means there is also a single`contact`

span), we have a simple contact that just shrinks the hole.In that case, we add vertices to the hole at the ends of the contact if needed, then remove any internal points in the

`contact`

span, then add the points from the`gap`

span.If there are multiple

`gap`

spans, we need to split the hole into multiple holes, adding 1 new hole for each gap after the first.Similarly to the single-gap case, we remove internal points in the

`contact`

spans, then swap the connections at the ends of the gaps so the`gap`

spans are closed and each corresponds to a separate hole, then add any intermediate points from`gap`

spans.