優化/簡化路徑

Question

假設我有一個包含150個節點/節點的路徑。我怎麼可以簡化，如果這樣，例如一個有3個頂點的直線會刪除中間的一個，因爲它不會添加到路徑中。另外我怎麼能避免摧毀尖角？我怎樣才能消除微小的變化，並保持平滑的曲線。

感謝

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個verticies一條直線，就因爲它什麼要補充的路徑中刪除中間的一個。

對於每組三個連續的頂點，測試它們是否都在一條直線上。如果是，則刪除中間頂點。

另外我怎樣才能避免摧毀尖角？

如果你只是刪除兩個人之間的直線上的頂點，那麼你不會有這個問題。

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是否處於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. 
} 

Answer 5

使用道格拉斯 - 普克方法簡化路徑。

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