Алгоритм упрощения пути Рамера-Дугласа-Пекера

Question

Я реализовал алгоритм упрощения пути после прочтения статьи здесь:

http://losingfight.com/blog/2011/05/30/how-to-implement-a-vector-brush/

Он очень хорошо сработал для меня, чтобы генерировать оптимизированную геометрию уровней для моей игры.Но сейчас я использую его для очистки * путей поиска путей, и у него есть странный крайний случай, который с треском проваливается.

Вот скриншот того, как он работает - оптимизация пути от красного круга до синего круга.Слабая зеленая линия - это вывод a *, а более светлая белесая линия - оптимизированный путь.

А вот скриншот с ошибкой:

Вот мой код.Я адаптировал код ObjC из статьи для c ++

Примечание: vec2fvec - это std::vector< vec2<float> >, а 'real' - просто float typedef'd.

       void rdpSimplify( const vec2fvec &in, vec2fvec &out, real threshold )
{
    if ( in.size() <= 2 )
    {
        out = in;
        return;
    }

    //
    //  Find the vertex farthest from the line defined by the start and and of the path
    //

    real maxDist = 0;
    size_t maxDistIndex = 0;      
    LineSegment line( in.front(), in.back() );

    for ( vec2fvec::const_iterator it(in.begin()),end(in.end()); it != end; ++it )
    {
        real dist = line.distance( *it );
        if ( dist > maxDist )
        {
            maxDist = dist;
            maxDistIndex = it - in.begin();
        }
    }

    //
    //  If the farhtest vertex is greater than our threshold, we need to
    //  partition and optimize left and right separately
    //

    if ( maxDist > threshold )
    {
        //
        //  Partition 'in' into left and right subvectors, and optimize them
        //

        vec2fvec left( maxDistIndex+1 ),
                 right( in.size() - maxDistIndex ),
                 leftSimplified,
                 rightSimplified;

        std::copy( in.begin(), in.begin() + maxDistIndex + 1, left.begin() );
        std::copy( in.begin() + maxDistIndex, in.end(), right.begin() );

        rdpSimplify(left, leftSimplified, threshold );
        rdpSimplify(right, rightSimplified, threshold );

        //
        //  Stitch optimized left and right into 'out'
        //

        out.resize( leftSimplified.size() + rightSimplified.size() - 1 );
        std::copy( leftSimplified.begin(), leftSimplified.end(), out.begin());
        std::copy( rightSimplified.begin() + 1, rightSimplified.end(), out.begin() + leftSimplified.size() );
    }
    else
    {
        out.push_back( line.a );
        out.push_back( line.b );
    }
}

I 'Я действительно в растерянности относительно того, что идет не так.Мое чувство пауков говорит, что это в вызовах std :: copy ... В некоторых случаях я должен копировать мусор.

РЕДАКТИРОВАТЬ: я переписал алгоритм, отбрасывая любое использование итераторов и std :: copy, иподобное, аналогичное, похожее.Он все равно терпит неудачу точно так же.

       void rdpSimplify( const vec2fvec &in, vec2fvec &out, real threshold )
{
    if ( in.size() <= 2 )
    {
        out = in;
        return;
    }

    //
    //  Find the vertex farthest from the line defined by the start and and of the path
    //

    real maxDist = 0;
    size_t maxDistIndex = 0;      
    LineSegment line( in.front(), in.back() );

    for ( size_t i = 0, N = in.size(); i < N; i++ )
    {
        real dist = line.distance( in[i] );
        if ( dist > maxDist )
        {
            maxDist = dist;
            maxDistIndex = i;
        }
    }


    //
    //  If the farthest vertex is greater than our threshold, we need to
    //  partition and optimize left and right separately
    //

    if ( maxDist > threshold )
    {
        //
        //  Partition 'in' into left and right subvectors, and optimize them
        //


        vec2fvec left, right, leftSimplified, rightSimplified;
        for ( size_t i = 0; i < maxDistIndex + 1; i++ ) left.push_back( in[i] );
        for ( size_t i = maxDistIndex; i < in.size(); i++ ) right.push_back( in[i] );


        rdpSimplify(left, leftSimplified, threshold );
        rdpSimplify(right, rightSimplified, threshold );

        //
        //  Stitch optimized left and right into 'out'
        //

        out.clear();
        for ( size_t i = 0, N = leftSimplified.size(); i < N; i++ ) out.push_back(leftSimplified[i]);
        for ( size_t i = 1, N = rightSimplified.size(); i < N; i++ ) out.push_back( rightSimplified[i] );
    }
    else
    {
        out.push_back( line.a );
        out.push_back( line.b );
    }
}

Answer 1

Я не могу найти ошибки в вашем коде.

Некоторые вещи попробовать:

• Добавьте несколько операторов отладочной печати, чтобы проверить, что означает maxDist в случае ошибки. Оно должно быть очень низким, но если оно получается высоким, то вы знаете, что есть проблема с кодом расстояния вашего отрезка.
• Убедитесь, что путь, который вы видите, действительно совпадает с путем, который возвращает ваш алгоритм. Если нет, то, возможно, что-то не так с вашим рендерингом пути? Может быть, ошибка, когда путь имеет только две точки?
• Убедитесь, что ваш входной путь соответствует ожидаемому, распечатав все его координаты в начале алгоритма.

Это не займет много времени, чтобы найти причину проблемы, если вы просто немного исследуете. Через несколько минут просмотр кода - очень плохой способ отладки.