Я реализовал алгоритм упрощения пути после прочтения статьи здесь:
http://losingfight.com / blog / 2011/05/30 / how-to-implementation-a-vector-brush /
У меня это неплохо сработало для создания оптимизированной геометрии уровней для моей игры. Но я использую его сейчас, чтобы очистить * пути поиска пути, и у него есть странный крайний случай, который с треском проваливается.
Вот скриншот его работы - оптимизация пути от красного круга к синему кругу. Слабая зеленая линия - это результат a *, а более светлая белая линия - это оптимизированный путь.
А вот скриншот, на котором он терпит неудачу:
Вот мой код. Я адаптировал код ObjC из статьи для c ++
. Примечание: vec2fvec
- это std :: vector
, а 'real' - это просто typedef ' d float.
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 );
}
}
Я действительно не понимаю, что идет не так. Мое паучье чутье говорит, что это в вызовах std :: copy ... В некоторых случаях я должен копировать мусор.
EDIT: Я переписал алгоритм, отказавшись от использования итераторов, 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 );
}
}