wmlconvexhull2.cpp

3D Game Engine Design Source Code非常棒

    GetTangent(rkLHull,rkRHull,iLLIndex,iLRIndex);

    // get upper tangent to hulls (UL = upper left, UR = upper right)
    int iULIndex = iLMax, iURIndex = iRMin;
    GetTangent(rkRHull,rkLHull,iURIndex,iULIndex);

    // Construct the counterclockwise-ordered merged-hull vertices.
    // TO DO.  If the hull is stored using linked lists, this block can be
    // improved by an O(1) detach, attach, and delete of the appropriate
    // sublists.
    i = iLRIndex;
    while ( true )
    {
        rkHull.push_back(rkRHull[i]);
        if ( i == iURIndex )
            break;

        if ( ++i == iRSize )
            i = 0;
    }

    i = iULIndex;
    while ( true )
    {
        rkHull.push_back(rkLHull[i]);
        if ( i == iLLIndex )
            break;

        if ( ++i == iLSize )
            i = 0;
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::MergeLinear (const SortedVertex& rkP, SVArray& rkHull)
{
    // hull = <Q0,Q1>

    switch ( CollinearTest(rkP.m_kV,rkHull[0].m_kV,rkHull[1].m_kV) )
    {
    case ORDER_POSITIVE:
        // merged hull is triangle <Q0,Q1,P>
        m_iHullType = HULL_PLANAR;
        rkHull.push_back(rkP);
        break;
    case ORDER_NEGATIVE:
    {
        // merged hull is triangle <Q1,Q0,P>
        m_iHullType = HULL_PLANAR;
        SortedVertex kSave = rkHull[0];
        rkHull[0] = rkHull[1];
        rkHull[1] = kSave;
        rkHull.push_back(rkP);
        break;
    }
    case ORDER_COLLINEAR_LEFT:
        // collinear order is <P,Q0,Q1>, merged hull is <P,Q1>
        rkHull[0] = rkP;
        break;
    case ORDER_COLLINEAR_RIGHT:
        // collinear order is <Q0,Q1,P>, merged hull is <Q0,P>
        rkHull[1] = rkP;
        break;
    //case ORDER_COLLINEAR_CONTAIN:
        // collinear order is <Q0,P,Q1>, merged hull is <Q0,Q1> (no change)
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::GetTangent (const SVArray& rkLHull,
    const SVArray& rkRHull, int& riL, int& riR)
{
    // In theory the loop terminates in a finite number of steps, but the
    // upper bound for the loop variable is used to trap problems caused by
    // floating point round-off errors that might lead to an infinite loop.

    int iLSize = (int)rkLHull.size(), iRSize = (int)rkRHull.size();
    int iLSizeM1 = iLSize-1, iRSizeM1 = iRSize-1;
    int i;
    for (i = 0; i < iLSize+iRSize; i++)
    {
        // end points of potential tangent
        const Vector2<Real>& rkL1 = rkLHull[riL].m_kV;
        const Vector2<Real>& rkR0 = rkRHull[riR].m_kV;

        // walk along left hull to find tangency
        int iLm1 = ( riL > 0 ? riL-1 : iLSizeM1 );
        const Vector2<Real>& rkL0 = rkLHull[iLm1].m_kV;
        int iCT = CollinearTest(rkR0,rkL0,rkL1);
        if ( iCT == ORDER_NEGATIVE || iCT == ORDER_COLLINEAR_LEFT )
        {
            riL = iLm1;
            continue;
        }

        // walk along right hull to find tangency
        int iRp1 = ( riR < iRSizeM1 ? riR+1 : 0 );
        const Vector2<Real>& rkR1 = rkRHull[iRp1].m_kV;
        iCT = CollinearTest(rkL1,rkR0,rkR1);
        if ( iCT == ORDER_NEGATIVE || iCT == ORDER_COLLINEAR_RIGHT )
        {
            riR = iRp1;
            continue;
        }

        // tangent segment has been found
        break;
    }

    // detect "infinite loop" caused by floating point round-off errors
    assert( i < iLSize+iRSize );
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// incremental hull
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::ByIncremental ()
{
    // Sort by x-component and store in contiguous array.  The sort is
    // O(N log N).
    SVArray kSVArray(m_iVQuantity);
    int i;
    for (i = 0; i < m_iVQuantity; i++)
    {
        kSVArray[i].m_kV = m_akVertex[i];
        kSVArray[i].m_iIndex = i;
    }
    sort(kSVArray.begin(),kSVArray.end());

    // remove duplicate points
    typename SVArray::iterator pkEnd =
        unique(kSVArray.begin(),kSVArray.end());
    kSVArray.erase(pkEnd,kSVArray.end());

    // Compute convex hull incrementally.  The first and second vertices in
    // the hull are managed separately until at least one triangle is formed.
    // At that time an array is used to store the hull in counterclockwise
    // order.
    m_iHullType = HULL_POINT;
    m_kHull.push_back(kSVArray[0]);
    for (i = 1; i < (int)kSVArray.size(); i++)
    {
        switch ( m_iHullType )
        {
        case HULL_POINT:
            m_iHullType = HULL_LINEAR;
            m_kHull.push_back(kSVArray[i]);
            break;
        case HULL_LINEAR:
            MergeLinear(kSVArray[i]);
            break;
        case HULL_PLANAR:
            MergePlanar(kSVArray[i]);
            break;
        }
    }

    // construct index array for ordered vertices of convex hull
    m_iHQuantity = (int)m_kHull.size();
    m_aiHIndex = new int[m_iHQuantity];
    for (i = 0; i < m_iHQuantity; i++)
        m_aiHIndex[i] = m_kHull[i].m_iIndex;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::MergeLinear (const SortedVertex& rkP)
{
    switch ( CollinearTest(rkP.m_kV,m_kHull[0].m_kV,m_kHull[1].m_kV) )
    {
    case ORDER_POSITIVE:
    {
        // merged hull is <P,Q0,Q1>
        m_iHullType = HULL_PLANAR;
        SortedVertex kCopy = m_kHull[1];
        m_kHull.push_back(kCopy);
        m_kHull[1] = m_kHull[0];
        m_kHull[0] = rkP;
        break;
    }
    case ORDER_NEGATIVE:
    {
        // merged hull is <P,Q1,Q0>
        m_iHullType = HULL_PLANAR;
        SortedVertex kCopy = m_kHull[0];
        m_kHull.push_back(kCopy);
        m_kHull[0] = rkP;
        break;
    }
    case ORDER_COLLINEAR_LEFT:
        // linear order is <P,Q0,Q1>, merged hull is <P,Q1>
        m_kHull[0] = rkP;
        break;
    case ORDER_COLLINEAR_RIGHT:
        // linear order is <Q0,Q1,P>, merged hull is <Q0,P>
        m_kHull[1] = rkP;
        break;
    // case ORDER_COLLINEAR_CONTAIN:  linear order is <Q0,P,Q1>, no change
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::MergePlanar (const SortedVertex& rkP)
{
    int iSize = (int)m_kHull.size();
    int i, iU, iL, iCT;

    // search counterclockwise for last visible vertex
    for (iU = 0, i = 1; iU < iSize; iU = i++)
    {
        if ( i == iSize )
            i = 0;

        iCT = CollinearTest(rkP.m_kV,m_kHull[iU].m_kV,m_kHull[i].m_kV);
        if ( iCT == ORDER_NEGATIVE )
            continue;
        if ( iCT == ORDER_POSITIVE || iCT == ORDER_COLLINEAR_LEFT )
            break;

        // iCT == ORDER_COLLINEAR_CONTAIN || iCT == ORDER_COLLINEAR_RIGHT
        return;
    }
    assert( iU < iSize );

    // search clockwise for last visible vertex
    for (iL = 0, i = iSize-1; i >= 0; iL = i--)
    {
        iCT = CollinearTest(rkP.m_kV,m_kHull[i].m_kV,m_kHull[iL].m_kV);
        if ( iCT == ORDER_NEGATIVE )
            continue;
        if ( iCT == ORDER_POSITIVE || iCT == ORDER_COLLINEAR_RIGHT )
            break;

        // iCT == ORDER_COLLINEAR_CONTAIN || iCT == ORDER_COLLINEAR_LEFT
        return;
    }
    assert( i >= 0 );

    if ( iU == iL )
    {
        // This probably occurs when CollinearTest should report collinearity,
        // but does not.  If it does occur, and you care about this code
        // block not occurring, try increasing the size of the collinear
        // epsilon.  When this block does occur, the conclusion is that the
        // input point is collinear with an edge of the hull, so just return.
        return;
    }

    // construct the counterclockwise-ordered merged-hull vertices
    SVArray kTmpHull;
    kTmpHull.push_back(rkP);
    while ( true )
    {
        kTmpHull.push_back(m_kHull[iU]);
        if ( iU == iL )
            break;

        if ( ++iU == iSize )
            iU = 0;
    }
    assert( kTmpHull.size() > 2 );

    m_kHull = kTmpHull;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
namespace Wml
{
template class WML_ITEM ConvexHull2<float>;
float ConvexHull2f::COLLINEAR_EPSILON = 1e-06f;

template class WML_ITEM ConvexHull2<double>;
double ConvexHull2d::COLLINEAR_EPSILON = 1e-06;
}
//----------------------------------------------------------------------------