  We present a fast algorithm to solve nesting problems based on a
semi-discrete representation of both the 2D non-convex pieces and the strip.
The pieces and the strip are represented by a set of equidistant vertical line
segments. The discretization algorithm uses a sweep-line method and applies
minimal extensions to the line segments of a piece to ensure that
non-overlapping placement of the segments, representing two pieces, cannot
cause overlap of the original pieces. We implemented a bottom-left-fill greedy
placement procedure, using an optimized ordering of the segment overlap tests.
The C++ implementation of our algorithm uses appropriate data structures that
allow fast execution. It executes the bottom-left-fill algorithm for typical
ESICUPdata sets in a few milliseconds, even when the rotation of the pieces is
considered, and thus provides a suitable basis for integration in
metaheuristics. Moreover, we show that the algorithm scales well when the
number of pieces increases.
