mgccirclefit.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#include "MgcCircleFit.h"

//----------------------------------------------------------------------------
bool MgcCircleFit (int iQuantity, const MgcVector2* akPoint,
    MgcVector2& rkCenter, MgcReal& rfRadius)
{
    // user-selected parameters
    const int iMaxIterations = 64;
    const MgcReal fTolerance = 1e-06;

    // compute the average of the data points
    MgcVector2 kAverage = akPoint[0];
    int i0;
    for (i0 = 1; i0 < iQuantity; i0++)
        kAverage += akPoint[i0];
    MgcReal fInvQuantity = 1.0/iQuantity;
    kAverage *= fInvQuantity;

    // initial guess
    rkCenter = kAverage;

    int i1;
    for (i1 = 0; i1 < iMaxIterations; i1++)
    {
        // update the iterates
        MgcVector2 kCurrent = rkCenter;

        // compute average L, dL/da, dL/db
        MgcReal fLAverage = 0.0;
        MgcVector2 kDerLAverage = MgcVector2::ZERO;
        for (i0 = 0; i0 < iQuantity; i0++)
        {
            MgcVector2 kDiff = akPoint[i0] - rkCenter;
            MgcReal fLength = kDiff.Length();
            if ( fLength > fTolerance )
            {
                fLAverage += fLength;
                MgcReal fInvLength = 1.0/fLength;
                kDerLAverage -= fInvLength*kDiff;
            }
        }
        fLAverage *= fInvQuantity;
        kDerLAverage *= fInvQuantity;

        rkCenter = kAverage + fLAverage*kDerLAverage;
        rfRadius = fLAverage;

        if ( MgcMath::Abs(rkCenter.x - kCurrent.x) <= fTolerance
        &&   MgcMath::Abs(rkCenter.y - kCurrent.y) <= fTolerance )
        {
            break;
        }
    }

    return i1 < iMaxIterations;
}
//----------------------------------------------------------------------------