如何有效优化二维路径中的坐标数量？

Question

我在二维环境中处理大量坐标。坐标模拟一条路径。

这是一个例子：

path = [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (2,2), (1,2), (0,2)]

我想通过删除冗余坐标来优化这条路径。坐标通常沿 X 轴或 Y 轴上的直线移动。因此，"corner" 坐标之间的所有点都可以从路径中删除。

此路径等同于上面的路径：

path = [(0,0), (3,0), (3,2), (0,2)]

这是描述所需优化的图片：

坐标将始终在其中一个轴上直线排列。对角线可以忽略。

如果有人可以提示我如何以有效的方式实现这一点，那就太好了。由于路径是程序生成的，因此我需要多次运行优化算法。

Answer 1

在许多情况下，Rahmer-Douglas-Peucker 算法适用于减少沿 2D 路线的点数。

python中的示例：

#  pip install rdp

from rdp import rdp

path = [[0,0], [1,0], [2,0], [3,0], [3,1], [3,2], [2,2], [1,2], [0,2]]

rdp(path)

#  output: [[0, 0], [3, 0], [3, 2], [0, 2]]

rdp project home

Answer 2

所以我想到了以下解决方案：每次我向路径添加一个新点时，我检查 X 或 Y 值是否等于前两个点的值。如果这是真的，我可以删除中间的 3 个点。

private void RedundancyCheck()
{
    if (this.Points.Length < 3)
    {
        return;
    }
    var last = this.Points[this.Points.Length-1];
    var secondLast = this.Points[this.Points.Length-2];
    var thirdLast = this.Points[this.Points.Length-3];

    if ( (last.x == secondLast.x && last.x == thirdLast.x)
        || (last.y == secondLast.y && last.y == thirdLast.y) )
    {
        RemovePoint(this.Points.Length-2);
    }
}

这个算法似乎运行相当快，我能够将坐标数量从 ~450'000 减少到 ~3300。（当然这要看坐标）

如何有效优化二维路径中的坐标数量？

How can I efficiently optimize the number of coordinates in a 2D path?

algorithm

optimization

game-development