c++ - 创建一个较小的凸包算法，可以用 1 个循环完成吗？

Question

我创建了一个可以工作的凸包程序，它能够绘制点和线以及使其具有视觉吸引力所需的一切。我的问题是，有没有一种方法可以设计成只需要一个 for 循环？而不是制作上下船体？似乎无法弄清楚一旦上层船体到达末端/开始较低时我将如何跟踪。

void computeConvexHull(QPainter * painter)
{
    int k = 0;
    std::vector<QPointF> vecLinePoints(2*vecPoints.size());

    // Sort points lexicographically
    std::sort(vecPoints.begin(),vecPoints.end(), xyCompare());

    //begin with far left, work our way to lower hull
    // Build upper hull
    for (int i = vecPoints.size()-2, j = k+1; i >= 0; i--)
    {
        while (k >= j && checkPoints(vecLinePoints[k-2], vecLinePoints[k-1], vecPoints[i]) <= 0)
            k--;
        vecLinePoints[k++] = vecPoints[i];
    }

    // Build lower hull
    for (int i = 0; i < vecPoints.size(); ++i)
    {
        while (k >= 2 && checkPoints(vecLinePoints[k-2], vecLinePoints[k-1], vecPoints[i]) <= 0)
            k--;
        vecLinePoints[k++] = vecPoints[i];
    }



    //reduce size of vector
    vecLinePoints.resize(k);

Answer 1

Sure, you could always do both upper and lower at the same time... but that's a waste. There exist more efficient algorithms than Andrew's monotone chain; see Wikipedia.

Hope this helps.