static HRESULT GenerateAccumulationLines()

in UVAtlas/isochart/imtcomputation.cpp [860:1010]
132 lines of code
30 McCabe index (conditional complexity)

    static HRESULT GenerateAccumulationLines(
        std::vector<DOUBLEVECTOR2>& keyPointList, // all key points on the lines, composite a convex polygon
        std::vector<DOUBLEVECTOR2>& above, // above line when applying 2 times accumulation
        std::vector<DOUBLEVECTOR2>& below)// below line when applying 2 times accumulation
    {
        if (keyPointList.empty())
        {
            return S_OK;
        }

        for (size_t ii = 0; ii < keyPointList.size() - 1; ii++)
        {
            for (size_t jj = ii + 1; jj < keyPointList.size();)
            {
                if (IsInZeroRangeDouble(keyPointList[jj].x - keyPointList[ii].x) &&
                    IsInZeroRangeDouble(keyPointList[jj].y - keyPointList[ii].y))
                {
                    keyPointList.erase(keyPointList.begin() + ptrdiff_t(jj));
                }
                else
                {
                    jj++;
                }
            }
        }
        if (keyPointList.size() < 3)
        {
            return S_OK;
        }

        // 1. Find the left most point
        DOUBLEVECTOR2 leftMost = { DBL_MAX, DBL_MAX };
        DOUBLEVECTOR2 rightMost = { -DBL_MAX, -DBL_MAX };
        DOUBLEVECTOR2 tempV;
        double fTemp;

        std::unique_ptr<double[]> tanList(new (std::nothrow) double[keyPointList.size()]);
        if (!tanList)
        {
            return E_OUTOFMEMORY;
        }

        double* pTanList = tanList.get();

        uint32_t dwLeftMost = 0;
        for (uint32_t ii = 0; ii < keyPointList.size(); ii++)
        {
            if (leftMost.x > keyPointList[ii].x ||
                (leftMost.x == keyPointList[ii].x && leftMost.y > keyPointList[ii].y))
            {
                leftMost = keyPointList[ii];
                dwLeftMost = ii;
            }
            if (rightMost.x < keyPointList[ii].x ||
                (rightMost.x == keyPointList[ii].x && rightMost.y > keyPointList[ii].y))
            {
                rightMost = keyPointList[ii];
            }
        }
        keyPointList[dwLeftMost] = keyPointList[0];
        keyPointList[0] = leftMost;

        // 2. Sort points along the counter clock-wise direction.
        for (size_t ii = 1; ii < keyPointList.size(); ii++)
        {
            double fy = keyPointList[ii].y - leftMost.y;
            double fx = keyPointList[ii].x - leftMost.x;

            if (IsInZeroRangeDouble(fx))
            {
                if (IsInZeroRangeDouble(fy))
                {
                    pTanList[ii] = -DBL_MAX;
                }
                else if (fy > 0)
                {
                    pTanList[ii] = DBL_MAX;
                }
                else
                {
                    pTanList[ii] = -DBL_MAX;
                }
            }
            else
            {
                pTanList[ii] = fy / fx;
            }
        }

        for (size_t ii = 1; ii < keyPointList.size() - 1; ii++)
        {
            for (size_t jj = ii + 1; jj < keyPointList.size(); jj++)
            {
                if (pTanList[ii] > pTanList[jj])
                {
                    tempV = keyPointList[ii];
                    keyPointList[ii] = keyPointList[jj];
                    keyPointList[jj] = tempV;

                    fTemp = pTanList[ii];
                    pTanList[ii] = pTanList[jj];
                    pTanList[jj] = fTemp;
                }
            }
        }

        // 3. Get above & below lines.
        try
        {
            uint32_t dwCur = 0;
            do
            {
                below.push_back(keyPointList[dwCur]);
                dwCur++;
            } while (dwCur < keyPointList.size()
                && keyPointList[dwCur - 1].x < keyPointList[dwCur].x);

            assert(keyPointList[dwCur - 1].x == rightMost.x);
            assert(keyPointList[dwCur - 1].y == rightMost.y);

            if (keyPointList[keyPointList.size() - 1].x > leftMost.x)
            {
                above.push_back(leftMost);
            }

            for (size_t jj = keyPointList.size() - 1; jj > 0; jj--)
            {
                above.push_back(keyPointList[jj]);

                if (keyPointList[jj].x >= rightMost.x)
                {
                    break;
                }
            }
        }
        catch (std::bad_alloc&)
        {
            return E_OUTOFMEMORY;
        }

        for (size_t ii = 0; ii < above.size() - 1; ii++)
        {
            assert(above[ii].x <= above[ii + 1].x);
        }
        for (size_t ii = 0; ii < below.size() - 1; ii++)
        {
            assert(below[ii].x <= below[ii + 1].x);
        }

        return S_OK;
    }