Ramer-Douglas-Peucker algoritmo del camino simplificación

Question

he implementado un algoritmo de simplificación ruta después de leer el artículo aquí:

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

Ha funcionado para mí bastante bien para generar la geometría optimizada nivel de mi juego. Pero lo estoy usando ahora para limpiar los caminos * pathfinding y tiene un caso raro que falla miserablemente.

Aquí hay una captura de pantalla de su funcionamiento, optimizando la ruta del círculo rojo al círculo azul. La débil línea verde es la salida a *, y la línea blanca más clara es la ruta optimizada.

Y aquí está una captura de pantalla de la misma en su defecto:

Aquí está mi código. Adapte el código ObjC del artículo a C++

Nota: vec2fvec es std::vector< vec2<float> >, y 'real' es simplemente un tipo de flotador.

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

Estoy realmente perdido en cuanto a lo que está pasando mal. Mi sentido spidey dice que está en las llamadas de copia estándar ... Debo copiar basura en algunas circunstancias.

EDIT: He reescrito el algoritmo eliminando cualquier uso de iterators y std :: copy, y similares. Todavía falla de la misma manera.

 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

No he encontrado ningún error en su código.

Algunas cosas para probar:

• añadir un poco de declaraciones de impresión de depuración para comprobar lo maxDist es en el caso de fallar. Debería ser realmente bajo, pero si sale alto, entonces sabrá que hay un problema con el código de distancia de su segmento de línea.
• Compruebe que la ruta que está viendo en realidad coincide con la ruta que devuelve su algoritmo. Si no, ¿tal vez hay algo mal con su representación de ruta? ¿Tal vez un error cuando el camino solo tiene dos puntos?
• Compruebe que su ruta de entrada es la que espera que sea imprimiendo todas sus coordenadas al comienzo del algoritmo.

No debería tomar demasiado tiempo encontrar la causa del problema si solo investiga un poco. Después de unos minutos, mirar el código es una forma muy pobre de depurar.