Optimisation/simplification d'un chemin

Question

Dites que j'ai un chemin avec 150 nœuds/verticies. Comment pourrais-je simplifier si par exemple une ligne droite avec 3 verticies, supprimerait le milieu puisqu'il ne fait rien à ajouter au chemin. Aussi, comment pourrais-je éviter de détruire les angles aigus? Et comment pourrais-je supprimer de minuscules variations et avoir des courbes lisses restant.

Merci

Answer 1

L'approche plus simple. Prendre 3 vertecies a, b et c et calcule: L'angle/inclinaison entre les vertecies.

std::vector<VERTEX> path; 
//fill path 
std::vector<int> removeList; 
//Assure that the value is in the same unit as the return of angleOf function. 
double maxTinyVariation = SOMETHING; 

for (int i = 0; i < quantity-2; ++i) { 
    double a = path[i], b = path[i + 1] , c = path[i + 2] 
    double abAngle = angleOf(a, b); 
    double bcAngle = angleOf(b, c); 

    if (abs(ab - bc) <= maxTinyVariation) { 
    //a, b and c are colinear 
    //remove b later 
    removeList.push_back(i+1); 
    } 
} 
//Remove vertecies from path using removeList. 

Answer 2

Comment pourrais-je simplifier si oui que par exemple une ligne droite avec 3 vertices, supprimerait le milieu d'un, car il ne fait rien à ajouter au chemin.

Pour chaque ensemble de trois sommets consécutifs, testez s'ils sont tous en ligne droite. Si c'est le cas, supprimez le vertex central.

Comment également éviter de détruire les angles vifs?

Si vous supprimez uniquement les sommets qui tombent sur une ligne droite entre deux autres, cela ne pose aucun problème.

Answer 3

Pour tous les 3 sommets, choisissez le milieu et calculate its distance to the line segment entre les deux autres. Si la distance est inférieure à la tolérance que vous acceptez, supprimez-la.

Si le sommet du milieu est très proche de l'un des points d'extrémité, vous devez resserrer la tolérance pour éviter de supprimer des coins arrondis par exemple.

Answer 4

Soit A, B, C quelques points.

La manière la plus simple de vérifier qu'ils se trouvent sur la même ligne est de compter le produit croisé des vecteurs B-A, C-A.

Si elle est égale à zéro, ils se trouvent sur la même ligne:

// X_ab, Y_ab - coordinates of vector B-A. 
float X_ab = B.x - A.x 
float Y_ab = B.y - A.y 
// X_ac, Y_ac - coordinates of vector C-A. 
float X_ac = C.x - A.x 
float Y_ac = C.y - A.y 
float crossproduct = Y_ab * X_ac - X_ab * Y_ac 
if (crossproduct < EPS) // if crossprudct == 0 
{ 
    // on the same line. 
} else { 
    // not on the same line. 
} 

Une fois que vous savez que A, B, C sont situés sur la même ligne, il est facile de savoir si B se situe entre A et C jeter innerproduct des vecteurs BA et CA. Si B est entre A et C, puis (B-A) a la même direction que (C-A), et innerproduct> 0, sinon < 0:

float innerproduct = X_ab * X_ac + Y_ab * Y_ac; 
if (innerproduct > 0) { 
    // B is between A and C. 
} else { 
    // B is not between A and C. 
} 

Answer 5

utilisation méthode Douglas-Peucker pour simplifier un chemin.

paramètre définit epsilon niveau de "simplicité":

private List<Point> douglasPeucker (List<Point> points, float epsilon){ 
    int count = points.size(); 
    if(count < 3) { 
     return points; 
    } 

    //Find the point with the maximum distance 
    float dmax = 0; 
    int index = 0; 
    for(int i = 1; i < count - 1; i++) { 
     Point point = points.get(i); 
     Point lineA = points.get(0); 
     Point lineB = points.get(count-1); 
     float d = perpendicularDistance(point, lineA, lineB); 
     if(d > dmax) { 
      index = i; 
      dmax = d; 
     } 
    } 

    //If max distance is greater than epsilon, recursively simplify 
    List<Point> resultList; 
    if(dmax > epsilon) { 
     List<Point> recResults1 = douglasPeucker(points.subList(0,index+1), epsilon); 

     List<Point> recResults2 = douglasPeucker(points.subList(index, count), epsilon); 

     List<Point> tmpList = new ArrayList<Point>(); 
     tmpList.addAll(recResults1); 
     tmpList.remove(tmpList.size()-1); 
     tmpList.addAll(recResults2); 
     resultList = tmpList; 
    } else { 
     resultList = new ArrayList<Point>(); 
     resultList.add(points.get(0)); 
     resultList.add(points.get(count-1)); 
    } 

    return resultList; 
} 

private float perpendicularDistance(Point point, Point lineA, Point lineB){ 
    Point v1 = new Point(lineB.x - lineA.x, lineB.y - lineA.y); 
    Point v2 = new Point(point.x - lineA.x, point.y - lineA.y); 
    float lenV1 = (float)Math.sqrt(v1.x * v1.x + v1.y * v1.y); 
    float lenV2 = (float)Math.sqrt(v2.x * v2.x + v2.y * v2.y); 
    float angle = (float)Math.acos((v1.x * v2.x + v1.y * v2.y)/(lenV1 * lenV2)); 
    return (float)(Math.sin(angle) * lenV2); 
}