5

Graham Scanを C++ で実装しようとしていますが、機能せず、その理由がわかりません。任意のリードをいただければ幸いです。いくつかの試行の後、私は常に持っているようm_M = 2で、2 ポイントが最高の y ポイントです。

外積で、右折か左折かがわかります。

qreal Interpolation::ccw(QPointF pt1, QPointF pt2, QPointF pt3)
{
    return (pt2.x()-pt1.x())*(pt3.y()-pt1.y()) - (pt2.y()-pt1.y())*(pt3.x()-pt1.x());
}

cos角度をソートすることは をソートすることと同じであるため、内積をノルムで割った値が になりcos in [0, Pi]ます。

qreal Interpolation::dp(QPointF pt1, QPointF pt2)
{
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
}

主な機能:

void Interpolation::ConvexHull()
{
    QPointF points[m_N+1]; // My number of points
    QPointF pt_temp(m_pt[0]);
    qreal angle_temp(0);
    int k_temp(0);

配列ポイントをpoints[1]下の y ポイントで埋めます。

    for (int i(1); i < m_N; ++i)
    {
        if (m_pt[i].y() < pt_temp.y())
        {
            points[i+1] = pt_temp;
            pt_temp = m_pt[i];
        }
        else
        {
            points[i+1] = m_pt[i];
        }
    }
    points[1] = pt_temp;

ポイント配列を角度で並べ替えて実行するpoints[m_N] = points[0]

    for (int i(2); i <= m_N; ++i)
    {
        pt_temp = points[i];
        angle_temp = dp(points[1], pt_temp);
        k_temp = i;
        for (int j(1); j <= m_N-i; ++j)
        {
            if (dp(points[1], points[i+j]) < angle_temp)
            {
                pt_temp = points[i+j];
                angle_temp = dp(points[1], points[i+j]);
                k_temp = i+j;
            }
        }
        points[k_temp] = points[i];
        points[i] = pt_temp;
    }
    points[0] = points[m_N];

グラハムスキャンの実行

    m_M = 1; // Number of points on the convex hull.

    for (int i(2); i <= m_N; ++i)
    {
        while (ccw(points[m_M-1], points[m_M], points[i]) <= 0)
        {
            if (m_M > 1)
            {
                m_M -= 1;
            }
            else if (i == m_N)
            {
                break;
            }
            else
            {
                i += 1;
            }
        }
        m_M += 1;
        pt_temp = points[m_M];
        points[m_M] = points[i];
        points[i] = points[m_M];
    }

m_convexHull船体上のポイントのリストになるはずのポイントを保存するConvexHull[m_M]=[ConvexHull[0]

    for (int i(0); i < m_M; ++i)
    {
        m_convexHull.push_back(points[i+1]);
    }
    m_convexHull.push_back(points[1]);
}
4

1 に答える 1

10

問題が見つかりました。それは次の文にあります。

角度をソートすることは [0, Pi] で cos をソートすることと同じであるため、ドット積をノルムで除算して cos を取得します。

角度が低いほど、cos が高くなるため、次のコード行を変更する必要がありました。

            if (dp(points[1], points[i+j]) < angle_temp)

に：

            if (dp(points[1], points[i+j]) > angle_temp)

そして今、それは完全に機能します！

于 2012-06-19T19:37:54.093 に答える