Оптимизация / упрощение пути
Скажите, что у меня есть путь с 150 узлами / verticies. Как я мог упростить раз так, что, например, прямая линия с 3 verticies, удалил бы средний, так как он не делает ничего для добавления к пути. Также, как я мог постараться не уничтожать острые углы? И как я мог удалить крошечные изменения и иметь остающиеся плавные кривые.
Спасибо
4 ответа
Более простой подход. Возьмите 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.
Пусть A, B, C - некоторые точки.
Самый простой способ проверить, что они лежат на одной линии, - это посчитать кросс-произведение векторов. Б-А, В-А.
Если он равен нулю, они лежат на одной прямой:
// 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, то (B-A) имеет то же направление, что и (C-A), и внутренний продукт> 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.
}
Для каждых трех вершин выберите среднюю и вычислите ее расстояние до отрезка между двумя другими. Если расстояние меньше допуска, который вы готовы принять, удалите его.
Если средняя вершина находится очень близко к одной из конечных точек, следует увеличить допуск, например, чтобы избежать удаления закругленных углов.
Как я могу упростить, если, например, прямая линия с 3 вершинами удаляла бы среднюю, поскольку она ничего не делает для добавить в путь.
Для каждого набора из трех последовательных вершин проверьте, все ли они находятся на прямой линии. Если они есть, удалите среднюю вершину.
Также как я могу избежать разрушения острых углов?
Если вы удаляете только вершины, которые попадают на прямую линию между двумя другими, тогда у вас не будет проблем с этим.