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

Question

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

Спасибо

Answer 1

Более простой подход. Возьмите 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 2

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

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

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 - некоторые точки.

Самый простой способ проверить, лежат ли они на одной и той же линии, - это подсчитать перекрестное произведение векторов BA, CA.

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

// 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 и выбрасывает внутренний продукт векторов BA и CA. Если B лежит между A и C, то (BA) имеет то же направление, что и (CA), и 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.
}