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

Question

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

Спасибо

Answer 1

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

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

Answer 2

Более простой подход. Возьмите 3 вершины a, b и c и рассчитайте: угол / наклон между вершинами.

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 3

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

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

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

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

Answer 4

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

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

Answer 5

Пусть 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 между A и C, бросая внутренний продукт векторов B-A и C-A. Если B лежит между A и C, то (B-A) имеет то же направление, что и (C-A), и внутренний продукт> 0, в противном случае <0: </p>

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