libnest2d::nfp Namespace Reference

A collection of static methods for handling the no fit polygon creation. More...

Classes
struct	MaxNfpLevel
struct	NfpImpl
struct	NfpImpl< S, NfpLevel::CONVEX_ONLY >

Typedefs
template<class RawShape >
using	NfpResult = std::pair< RawShape, TPoint< RawShape > >
template<class RawShape >
using	Shapes = TMultiShape< RawShape >

Enumerations
enum class	NfpLevel : unsigned {   CONVEX_ONLY , ONE_CONVEX , BOTH_CONCAVE , ONE_CONVEX_WITH_HOLES ,   BOTH_CONCAVE_WITH_HOLES }
	The complexity level of a polygon that an NFP implementation can handle. More...

Functions
template<>
TMultiShape< PolygonImpl >	merge (const TMultiShape< PolygonImpl > &shapes)
template<class RawShapes >
RawShapes	merge (const RawShapes &)
template<class RawShape >
TMultiShape< RawShape >	merge (const TMultiShape< RawShape > &shc, const RawShape &sh)
template<class RawShape >
TPoint< RawShape >	leftmostDownVertex (const RawShape &sh)
template<class RawShape >
TPoint< RawShape >	rightmostUpVertex (const RawShape &sh)
template<class RawShape >
TPoint< RawShape >	referenceVertex (const RawShape &sh)
template<class RawShape , class Ratio = double>
NfpResult< RawShape >	nfpConvexOnly (const RawShape &sh, const RawShape &other)
template<NfpLevel nfptype, class RawShape >
NfpResult< RawShape >	noFitPolygon (const RawShape &sh, const RawShape &other)
	Helper function to get the NFP.

Variables
const double BP2D_CONSTEXPR	TwoPi = 2*Pi

Detailed Description

A collection of static methods for handling the no fit polygon creation.

Typedef Documentation

NfpResult

template<class RawShape >

using libnest2d::nfp::NfpResult = typedef std::pair<RawShape, TPoint<RawShape> >

Shapes

template<class RawShape >

using libnest2d::nfp::Shapes = typedef TMultiShape<RawShape>

Enumeration Type Documentation

NfpLevel

enum class libnest2d::nfp::NfpLevel : unsigned

strong

The complexity level of a polygon that an NFP implementation can handle.

Enumerator
CONVEX_ONLY
ONE_CONVEX
BOTH_CONCAVE
ONE_CONVEX_WITH_HOLES
BOTH_CONCAVE_WITH_HOLES

                   : unsigned {
    CONVEX_ONLY,
    ONE_CONVEX,
    BOTH_CONCAVE,
    ONE_CONVEX_WITH_HOLES,
    BOTH_CONCAVE_WITH_HOLES
};

Function Documentation

leftmostDownVertex()

template<class RawShape >

TPoint< RawShape > libnest2d::nfp::leftmostDownVertex ( const RawShape &  sh )

inline

Get the vertex of the polygon that is at the lowest values (bottom) in the Y axis and if there are more than one vertices on the same Y coordinate than the result will be the leftmost (with the highest X coordinate).

{
 
    // find min x and min y vertex
    auto it = std::min_element(shapelike::cbegin(sh), shapelike::cend(sh),
                               __nfp::_vsort<RawShape>);
 
    return it == shapelike::cend(sh) ? TPoint<RawShape>() : *it;;
}

References libnest2d::shapelike::cbegin(), and libnest2d::shapelike::cend().

Here is the call graph for this function:

merge() [1/3]

template<class RawShapes >

RawShapes libnest2d::nfp::merge ( const RawShapes &  )

inline

Merge a bunch of polygons with the specified additional polygon.

Template Parameters

RawShape

the Polygon data type.

Parameters

shc	The pile of polygons that will be unified with sh.
sh	A single polygon to unify with shc.

Returns

A set of polygons that is the union of the input polygons. Note that mostly it will be a set containing only one big polygon but if the input polygons are disjunct than the resulting set will contain more polygons.

{
    static_assert(always_false<RawShapes>::value,
                  "Nfp::merge(shapes, shape) unimplemented!");
}

merge() [2/3]

template<>

TMultiShape< PolygonImpl > libnest2d::nfp::merge ( const TMultiShape< PolygonImpl > &  shapes )

inline

{
    return Slic3r::union_ex(shapes);
}

References Slic3r::union_ex().

Referenced by libnest2d::placers::_NofitPolyPlacer< RawShape, TBin >::calcnfp(), merge(), and libnest2d::placers::_NofitPolyPlacer< RawShape, TBin >::preload().

Here is the call graph for this function:

Here is the caller graph for this function:

merge() [3/3]

template<class RawShape >

TMultiShape< RawShape > libnest2d::nfp::merge ( const TMultiShape< RawShape > &  shc, const RawShape &  sh  )

inline

Merge a bunch of polygons with the specified additional polygon.

Template Parameters

RawShape

the Polygon data type.

Parameters

shc	The pile of polygons that will be unified with sh.
sh	A single polygon to unify with shc.

Returns

A set of polygons that is the union of the input polygons. Note that mostly it will be a set containing only one big polygon but if the input polygons are disjunct than the resulting set will contain more polygons.

{
    auto m = nfp::merge(shc);
    m.emplace_back(sh);
    return nfp::merge(m);
}

References merge().

Here is the call graph for this function:

nfpConvexOnly()

template<class RawShape , class Ratio = double>

NfpResult< RawShape > libnest2d::nfp::nfpConvexOnly ( const RawShape &  sh, const RawShape &  other  )

inline

The "trivial" Cuninghame-Green implementation of NFP for convex polygons.

You can use this even if you provide implementations for the more complex cases (Through specializing the the NfpImpl struct). Currently, no other cases are covered in the library.

Complexity should be no more than nlogn (std::sort) in the number of edges of the input polygons.

Template Parameters

RawShape

the Polygon data type.

Parameters

sh	The stationary polygon
cother	The orbiting polygon

Returns

Returns a pair of the NFP and its reference vertex of the two input polygons which have to be strictly convex. The resulting NFP is proven to be convex as well in this case.

{
    using Vertex = TPoint<RawShape>; using Edge = _Segment<Vertex>;
    namespace sl = shapelike;
 
    RawShape rsh;   // Final nfp placeholder
    Vertex top_nfp;
    std::vector<Edge> edgelist;
 
    auto cap = sl::contourVertexCount(sh) + sl::contourVertexCount(other);
 
    // Reserve the needed memory
    edgelist.reserve(cap);
    sl::reserve(rsh, static_cast<unsigned long>(cap));
    auto add_edge = [&edgelist](const Vertex &v1, const Vertex &v2) {
        Edge e{v1, v2};
        if (e.sqlength() > 0)
            edgelist.emplace_back(e);
    };
 
    { // place all edges from sh into edgelist
        auto first = sl::cbegin(sh);
        auto next = std::next(first);
 
        while(next != sl::cend(sh)) {
            add_edge(*(first), *(next));
 
            ++first; ++next;
        }
 
        if constexpr (ClosureTypeV<RawShape> == Closure::OPEN)
            add_edge(*sl::rcbegin(sh), *sl::cbegin(sh));
    }
 
    { // place all edges from other into edgelist
        auto first = sl::cbegin(other);
        auto next = std::next(first);
 
        while(next != sl::cend(other)) {
            add_edge(*(next), *(first));
 
            ++first; ++next;
        }
 
        if constexpr (ClosureTypeV<RawShape> == Closure::OPEN)
            add_edge(*sl::cbegin(other), *sl::rcbegin(other));
    }
   
    std::sort(edgelist.begin(), edgelist.end(),
              [](const Edge& e1, const Edge& e2)
    {
        const Vertex ax(1, 0); // Unit vector for the X axis
        
        // get cectors from the edges
        Vertex p1 = e1.second() - e1.first();
        Vertex p2 = e2.second() - e2.first();
 
        // Quadrant mapping array. The quadrant of a vector can be determined
        // from the dot product of the vector and its perpendicular pair
        // with the unit vector X axis. The products will carry the values
        // lcos = dot(p, ax) = l * cos(phi) and
        // lsin = -dotperp(p, ax) = l * sin(phi) where
        // l is the length of vector p. From the signs of these values we can
        // construct an index which has the sign of lcos as MSB and the
        // sign of lsin as LSB. This index can be used to retrieve the actual
        // quadrant where vector p resides using the following map:
        // (+ is 0, - is 1)
        // cos | sin | decimal | quadrant
        //  +  |  +  |    0    |    0
        //  +  |  -  |    1    |    3
        //  -  |  +  |    2    |    1
        //  -  |  -  |    3    |    2
        std::array<int, 4> quadrants {0, 3, 1, 2 };
 
        std::array<int, 2> q {0, 0}; // Quadrant indices for p1 and p2
 
        using TDots = std::array<TCompute<Vertex>, 2>;
        TDots lcos { pl::dot(p1, ax), pl::dot(p2, ax) };
        TDots lsin { -pl::dotperp(p1, ax), -pl::dotperp(p2, ax) };
 
        // Construct the quadrant indices for p1 and p2
        for(size_t i = 0; i < 2; ++i)
            if(lcos[i] == 0) q[i] = lsin[i] > 0 ? 1 : 3;
            else if(lsin[i] == 0) q[i] = lcos[i] > 0 ? 0 : 2;
            else q[i] = quadrants[((lcos[i] < 0) << 1) + (lsin[i] < 0)];
            
        if(q[0] == q[1]) { // only bother if p1 and p2 are in the same quadrant
            auto lsq1 = pl::magnsq(p1);     // squared magnitudes, avoid sqrt
            auto lsq2 = pl::magnsq(p2);     // squared magnitudes, avoid sqrt
 
            // We will actually compare l^2 * cos^2(phi) which saturates the
            // cos function. But with the quadrant info we can get the sign back
            int sign = q[0] == 1 || q[0] == 2 ? -1 : 1;
            
            // If Ratio is an actual rational type, there is no precision loss
            auto pcos1 = Ratio(lcos[0]) / lsq1 * sign * lcos[0];
            auto pcos2 = Ratio(lcos[1]) / lsq2 * sign * lcos[1];
 
            if constexpr (is_clockwise<RawShape>())
                return q[0] < 2 ? pcos1 < pcos2 : pcos1 > pcos2;
            else
                return q[0] < 2 ? pcos1 > pcos2 : pcos1 < pcos2;
        }
        
        // If in different quadrants, compare the quadrant indices only.
        if constexpr (is_clockwise<RawShape>())
            return q[0] > q[1];
        else
            return q[0] < q[1];
    });
 
    __nfp::buildPolygon(edgelist, rsh, top_nfp);
 
    return {rsh, top_nfp};
}

References libnest2d::shapelike::cbegin(), libnest2d::shapelike::cend(), libnest2d::shapelike::contourVertexCount(), libnest2d::pointlike::dot(), libnest2d::pointlike::dotperp(), libnest2d::pointlike::magnsq(), libnest2d::OPEN, libnest2d::shapelike::rcbegin(), libnest2d::shapelike::reserve(), and sign().

Referenced by libnest2d::nfp::NfpImpl< RawShape, nfptype >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

noFitPolygon()

template<NfpLevel nfptype, class RawShape >

NfpResult< RawShape > libnest2d::nfp::noFitPolygon ( const RawShape &  sh, const RawShape &  other  )

inline

Helper function to get the NFP.

{
    NfpImpl<RawShape, nfptype> nfps;
    return nfps(sh, other);
}

References noFitPolygon().

Referenced by noFitPolygon().

Here is the call graph for this function:

Here is the caller graph for this function:

referenceVertex()

template<class RawShape >

TPoint< RawShape > libnest2d::nfp::referenceVertex ( const RawShape &  sh )

inline

A method to get a vertex from a polygon that always maintains a relative position to the coordinate system: It is always the rightmost top vertex.

This way it does not matter in what order the vertices are stored, the reference will be always the same for the same polygon.

{
    return rightmostUpVertex(sh);
}

References rightmostUpVertex().

Here is the call graph for this function:

rightmostUpVertex()

template<class RawShape >

TPoint< RawShape > libnest2d::nfp::rightmostUpVertex

(

const RawShape &

sh

)

Get the vertex of the polygon that is at the highest values (top) in the Y axis and if there are more than one vertices on the same Y coordinate than the result will be the rightmost (with the lowest X coordinate).

{
 
    // find max x and max y vertex
    auto it = std::max_element(shapelike::cbegin(sh), shapelike::cend(sh),
                               __nfp::_vsort<RawShape>);
 
    return it == shapelike::cend(sh) ? TPoint<RawShape>() : *it;
}

References libnest2d::shapelike::cbegin(), and libnest2d::shapelike::cend().

Referenced by libnest2d::placers::correctNfpPosition(), and referenceVertex().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

TwoPi

const double BP2D_CONSTEXPR libnest2d::nfp::TwoPi = 2*Pi