No-Fit Polygon (NFP)
A computational geometry construct used in nesting algorithms that defines all positions where one part can be placed relative to another without overlap. NFP calculation is the core of most true-shape nesting solvers.
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
Ready to try Lapas?
Start free — no credit card