时间戳

首页 > 解决方案 > 简化二维网格上的路径

arrays - 简化二维网格上的路径

问题描述

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

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

在此处输入图像描述

我怎样才能简化这条路径到这样的事情？ 在此处输入图像描述

标签： arraysalgorithmoptimizationpathgrid

解决方案

如果我们考虑输入路径上的 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)]

推荐阅读