Оптимизация/упрощение пути

Question

Скажем, у меня есть путь с 150 узлами/вершинами. Как я мог бы упростить, если бы это так, например, прямая линия с тремя вершинами, удаляла бы среднюю, так как она ничего не добавляет к пути. И как я мог избежать разрушения острых углов? И как я могу удалить крошечные вариации и оставить гладкие кривые.

Благодаря

Answer 1

Чем проще подход. Возьмите 3 вершины a, b и c и calcule: угол/угол между вершинами.

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

Как я мог бы упростить, если так, что, например, прямая линия с 3-х вершин,, устранило бы средний, так как он не делает ничего, чтобы добавить к пути.

Для каждого набора из трех последовательных вершин проверьте, все ли они в прямой линии. Если они есть, удалите среднюю вершину.

Также как можно избежать разрушения острых углов?

Если вы только удаляете вершины, которые падают на прямую линию между двумя другими, тогда у вас не будет проблемы с этим.

Answer 3

Для каждых 3 вершин выберите средний и calculate its distance to the line segment между двумя другими. Если расстояние меньше допуска, которое вы готовы принять, удалите его.

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

Answer 4

Пусть A, B, C - некоторые точки.

Самый простой способ проверить, что они лежат на одной линии, - считать кросспродукт векторов B-A, C-A.

Если он равен нулю, то они лежат на одной и той же линии:

// 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. 
} 

После вы знаете, что A, B, C лежат на одной и той же линии, что легко знать, находится ли B между точками А и С броском innerproduct векторов BA и CA. Если B лежит между А и С, а затем (В-А) имеет такое же направление, как (С-А), и innerproduct> 0, в противном случае < 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

Использование Дуглас-Peucker метод для упрощения пути.

epsilon параметр определяет уровень "простоты":

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