1

私は、点と線、および視覚的に魅力的なものにするために必要なすべてを描画できる、実用的な凸包プログラムを作成しました。私の質問は、for ループが 1 つだけ必要になるように設計する方法はありますか? 上下の船体を作る代わりに？上部の船体が最後に到達する/低くなり始めると、どうすれば追跡できるのかわかりません。 

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);
4

1 に答える 1

0

確かに、いつでも上と下の両方を同時に行うことができます...しかし、それはもったいないです. Andrew のモノトーン チェーンよりも効率的なアルゴリズムが存在します。ウィキペディアを参照してください。

お役に立てれば。

于 2015-11-27T20:51:22.087 に答える