What is the No-Fit Polygon (NFP)?

The No-Fit Polygon (NFP) is a geometric region that encodes all positions where one shape (part A) would overlap with another shape (part B) if part A’s reference point were placed inside the NFP.

Equivalently, the complement of the NFP gives all positions where part A can be placed without overlapping part B. This makes NFP the foundational tool for collision-free placement in 2D irregular bin packing and nesting problems.

Intuition

Imagine sliding part A around the perimeter of part B, keeping the two shapes always touching but never overlapping. The path traced by a reference point on part A forms the No-Fit Polygon. Any position inside this polygon would cause the two parts to overlap.

Why NFP matters for nesting software

Computing NFPs efficiently allows a nesting algorithm to:

Quickly determine all valid non-overlapping positions for a new part relative to already-placed parts
Combine multiple NFPs to handle a sheet with many placed parts
Find tight-fitting arrangements that maximize material utilization

Without NFP or an equivalent approach, a nesting algorithm would need to test collision at every pixel — computationally infeasible for real-world jobs.

Inner Fit Polygon (IFP)

A related concept is the Inner Fit Polygon (IFP), which defines all valid positions where part A fits entirely within a containing boundary (the sheet or bin). The feasible placement region for a part is the intersection of the IFP with the complement of all NFPs from already-placed parts.

NFP in practice

Exact NFP calculation is complex for arbitrary polygon shapes and becomes especially challenging with:

Concave (non-convex) polygons
Parts with holes
Non-integer rotation angles

Most production nesting tools — including Lapas — use a combination of exact NFP for convex parts and approximate/rasterized methods for complex concave geometries, balancing solution quality against computation time.

Open source NFP implementations

SVGNest (JavaScript) — the most-cited open reference implementation, uses NFP with a genetic algorithm optimizer
Deepnest — also NFP-based, offline application
Lapas’s Sparrow engine uses an advanced metaheuristic on top of NFP-based feasibility checking

NFP computation methods

Minkowski difference method

The classic NFP for two convex polygons A and B is computed as the Minkowski difference of B with the reflection of A:

NFP(A, B) = B ⊕ (−A)

Where ⊕ is the Minkowski sum and −A is A reflected through its reference point. This produces an exact result in polynomial time for convex polygons.

For concave polygons, exact NFP computation is significantly more complex and may require decomposing the polygon into convex sub-parts, computing individual NFPs, and combining the results.

Orbital method

An intuitive alternative: translate part A around the perimeter of part B while keeping them in contact (but not overlapping). The locus of a reference point on A traces the NFP boundary. This works for convex and some concave shapes but has edge cases around concavities.

Rasterized (pixel-based) approximation

For highly irregular geometry or parts with smooth curves, many practical implementations approximate the NFP by discretizing part outlines into a pixel grid. Collision detection becomes a bitwise AND operation on two bitmaps — fast and general, but introduces approximation error proportional to grid resolution.

Most commercial nesting software uses rasterization for complex geometry, with exact NFP for convex primitives.

NFP vs. no-NFP approaches

Some simpler nesting tools avoid NFP entirely and use point sampling — testing many discrete positions for each part and checking pairwise overlap. This is computationally expensive and doesn’t scale well, but is easier to implement for arbitrary geometry including splines and arcs.

The NFP approach is generally preferred for production nesting because:

The feasibility region is computed once per pair of shapes (not once per candidate position)
The NFP is reusable across different placement attempts for the same parts
It enables exact collision avoidance rather than probabilistic checking

Inner Fit Polygon and feasible placement region

For a part being placed on a sheet with already-placed parts, the feasible placement region (FPR) is:

FPR = IFP(sheet, new_part) ∩ complement(NFP(placed_1, new_part)) ∩ … ∩ complement(NFP(placed_n, new_part))

Finding a valid position is equivalent to finding any point inside the FPR. This formulation allows the optimizer to efficiently filter candidate positions without explicit overlap testing.

FAQ

Is NFP the same as a bounding box?

No. A bounding box is a coarse rectangular approximation. NFP captures the exact geometry of valid placements — including concavities and all rotation angles. Using bounding boxes instead of NFP is what distinguishes rectangular nesting from true-shape nesting.

Does rotating a part change its NFP?

Yes — the NFP between two parts is rotation-dependent. If part A can rotate freely, the nesting algorithm must compute (or approximate) an NFP for each distinct orientation angle. Most tools precompute a set of discrete rotation angles (e.g., every 5° or 10°) and build an NFP cache. Free-rotation nesting is more expensive to compute than fixed-angle nesting for this reason.

Why do some nesting tools produce overlapping parts?

Usually a bug in NFP computation or polygon decomposition for concave shapes. NFP bugs are common edge cases in nesting algorithm implementations — concave polygons with narrow passages or self-intersecting outlines can confuse NFP computation and result in placements that appear valid but actually overlap. Lapas validates placements geometrically as a safeguard against this.