简化二维网格上的路径

Question

我在二维网格上生成一条从 A 点到 B 点的路径，returns 我的单元要经过的点数组，数组中的每个元素都有一个 X 和 Y 坐标。

红色点是路径起点，蓝色点是终点，棕色点是数组中包含的点（数组也包括起点和终点），绿线是路径。

如何将这条路径简化为这样的东西？

Answer 1

如果我们考虑输入路径上的 3 个点 (p0,p1,p2) 我们希望在满足以下条件时删除中间点 p1：

(p1.x - p0.x)    (p2.x - p1.x)
------------- == -------------
(p1.y - p0.y)    (p2.y - p1.y)

或等效地，避免被零除的风险：

(p1.x - p0.x) * (p2.y - p1.y) == (p1.y - p0.y) * (p2.x - p1.x)

这里有一些 Java 代码来说明：

static List<Point> simplify(List<Point> poly)
{
    if(poly.size() < 3) return new ArrayList<>(poly);
    
    List<Point> spoly = new ArrayList<>();
    
    spoly.add(poly.get(0));
    for(int i = 0, dx = 0, dy = 0; i < poly.size()-1; i++)
    {
        Point p0 = poly.get(i);
        Point p1 = poly.get(i+1);
        
        int x = p1.x - p0.x;
        int y = p1.y - p0.y;
        
        if(i > 0 && (dx * y != dy * x)) 
            spoly.add(poly.get(i));
        
        dx = x;
        dy = y;
    }
    spoly.add(poly.get(poly.size()-1));
    
    return spoly;
}

测试：

List<Point> poly = 
   Arrays.asList(p(0, 0), p(1, 1), p(2, 2), p(3, 3), p(4, 3), p(5, 3), p(6, 3));

System.out.println(simplify(poly));

输出：

[(0, 0), (3, 3), (6, 3)]

简化二维网格上的路径

Simplifying a path on a two dimensional grid

arrays

algorithm

grid

optimization

path