wmlconvexhull2.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlConvexHull2.h"
using namespace Wml;

#include <algorithm>
#include <set>
using namespace std;

//----------------------------------------------------------------------------
template <class Real>
ConvexHull2<Real>::ConvexHull2 (int iVQuantity, const Vector2<Real>* akVertex,
    bool bIncremental)
{
    m_iVQuantity = iVQuantity;
    m_akVertex = akVertex;

    if ( bIncremental )
        ByIncremental();
    else
        ByDivideAndConquer();

    if ( m_iHQuantity >= 3 )
        RemoveCollinear();
}
//----------------------------------------------------------------------------
template <class Real>
ConvexHull2<Real>::~ConvexHull2 ()
{
    delete[] m_aiHIndex;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexHull2<Real>::GetQuantity () const
{
    return m_iHQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
const int* ConvexHull2<Real>::GetIndices () const
{
    return m_aiHIndex;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexHull2<Real>::ContainsPoint (const Vector2<Real>& rkP) const
{
    for (int i1 = 0, i0 = m_iHQuantity-1; i1 < m_iHQuantity; i0 = i1++)
    {
        const Vector2<Real>& rkV0 = m_akVertex[m_aiHIndex[i0]];
        const Vector2<Real>& rkV1 = m_akVertex[m_aiHIndex[i1]];
        Vector2<Real> kDir = rkV1 - rkV0;
        Vector2<Real> kNormal = kDir.Perp();  // outer normal
        if ( kNormal.Dot(rkP-rkV0) > (Real)0.0 )
            return false;
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexHull2<Real>::CollinearTest (const Vector2<Real>& rkP,
    const Vector2<Real>& rkQ0, const Vector2<Real>& rkQ1) const
{
    Vector2<Real> kD = rkQ1 - rkQ0;
    Vector2<Real> kA = rkP - rkQ0;
    Real fDdD = kD.Dot(kD);
    Real fAdA = kA.Dot(kA);
    Real fDet = kD.Kross(kA);
    Real fRelative = fDet*fDet - COLLINEAR_EPSILON*fDdD*fAdA;

    if ( fRelative > (Real)0.0 )
    {
        if ( fDet > (Real)0.0 )
        {
            // points form counterclockwise triangle <P,Q0,Q1>
            return ORDER_POSITIVE;
        }
        else if ( fDet < (Real)0.0 )
        {
            // points form clockwise triangle <P,Q1,Q0>
            return ORDER_NEGATIVE;
        }
    }

    // P is on line of <Q0,Q1>
    Real fDdA = kD.Dot(kA);
    if ( fDdA < (Real)0.0 )
    {
        // order is <P,Q0,Q1>
        return ORDER_COLLINEAR_LEFT;
    }

    if ( fDdA > fDdD )
    {
        // order is <Q0,Q1,P>
        return ORDER_COLLINEAR_RIGHT;
    }

    // order is <Q0,P,Q1>
    return ORDER_COLLINEAR_CONTAIN;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::RemoveCollinear ()
{
    if ( m_iHQuantity <= 2 )
        return;

    vector<int> kHull;
    kHull.reserve(m_iHQuantity);
    for (int i0 = m_iHQuantity-1, i1 = 0, i2 = 1; i1 < m_iHQuantity; /**/)
    {
        int iCT = CollinearTest(m_akVertex[m_aiHIndex[i0]],
            m_akVertex[m_aiHIndex[i1]],m_akVertex[m_aiHIndex[i2]]);

        if ( iCT == ORDER_POSITIVE || iCT == ORDER_NEGATIVE )
        {
            // points are not collinear
            kHull.push_back(m_aiHIndex[i1]);
        }

        i0 = i1++;
        if ( ++i2 == m_iHQuantity )
            i2 = 0;
    }

    // construct index array for ordered vertices of convex hull
    m_iHQuantity = (int)kHull.size();
    delete[] m_aiHIndex;
    m_aiHIndex = new int[m_iHQuantity];
    memcpy(m_aiHIndex,&kHull.front(),m_iHQuantity*sizeof(int));
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// divide-and-conquer hull
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::ByDivideAndConquer ()
{
    // 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 using divide-and-conquer
    SVArray kHull;
    kHull.reserve(kSVArray.size());
    m_iHullType = HULL_POINT;
    GetHull(0,(int)kSVArray.size()-1,kSVArray,kHull);

    // construct index array for ordered vertices of convex hull
    m_iHQuantity = (int)kHull.size();
    m_aiHIndex = new int[m_iHQuantity];
    for (i = 0; i < m_iHQuantity; i++)
        m_aiHIndex[i] = kHull[i].m_iIndex;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::GetHull (int i0, int i1, const SVArray& rkSVArray,
    SVArray& rkHull)
{
    int iQuantity = i1 - i0 + 1;
    if ( iQuantity > 1 )
    {
        // middle index of input range
        int iMid = (i0+i1)/2;

        // find hull of subsets (iMid-i0+1 >= i1-iMid)
        SVArray kLHull, kRHull;
        kLHull.reserve(iMid-i0+1);
        kRHull.reserve(i1-iMid);

        GetHull(i0,iMid,rkSVArray,kLHull);
        GetHull(iMid+1,i1,rkSVArray,kRHull);

        // merge the convex hulls into a single convex hull
        Merge(kLHull,kRHull,rkHull);
    }
    else
    {
        // convex hull is a single point
        rkHull.push_back(rkSVArray[i0]);
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull2<Real>::Merge (SVArray& rkLHull, SVArray& rkRHull,
    SVArray& rkHull)
{
    // merge small sets, handle cases when sets are collinear
    int iLSize = (int)rkLHull.size(), iRSize = (int)rkRHull.size();
    if ( iLSize == 1 )
    {
        if ( iRSize == 1 )
        {
            rkHull.push_back(rkLHull[0]);
            rkHull.push_back(rkRHull[0]);
            if ( m_iHullType != HULL_PLANAR )
                m_iHullType = HULL_LINEAR;
            return;
        }
        else if ( iRSize == 2 )
        {
            MergeLinear(rkLHull[0],rkRHull);
            rkHull = rkRHull;
            return;
        }
    }
    else if ( iLSize == 2 )
    {
        if ( iRSize == 1 )
        {
            MergeLinear(rkRHull[0],rkLHull);
            rkHull = rkLHull;
            return;
        }
        else if ( iRSize == 2 )
        {
            MergeLinear(rkRHull[1],rkLHull);

            if ( rkLHull.size() == 2 )
            {
                MergeLinear(rkRHull[0],rkLHull);
                rkHull = rkLHull;
                return;
            }

            // fall-through, LHull is a triangle, RHull is a point
            iLSize = 3;
            iRSize = 1;
            rkRHull.pop_back();
        }
    }

    // find rightmost point of left hull
    Real fMax = rkLHull[0].m_kV.X();
    int i, iLMax = 0;
    for (i = 1; i < iLSize; i++)
    {
        if ( rkLHull[i].m_kV.X() > fMax )
        {
            fMax = rkLHull[i].m_kV.X();
            iLMax = i;
        }
    }

    // find leftmost point of right hull
    Real fMin = rkRHull[0].m_kV.X();
    int iRMin = 0;
    for (i = 1; i < iRSize; i++)
    {
        if ( rkRHull[i].m_kV.X() < fMin )
        {
            fMin = rkRHull[i].m_kV.X();
            iRMin = i;
        }
    }

    // get lower tangent to hulls (LL = lower left, LR = lower right)
    int iLLIndex = iLMax, iLRIndex = iRMin;