如何简化/优化3d路径？

Question

我在3d中有一堆点（一个包含具有x，y，z属性的对象的数组）。

我的问题是有很多不必要的点，如下图所示：

（来源：lifesine.eu）

我该如何清理这条路？

目前首先想到的是

• 为优化路径创建一个数组
• 循环遍历以索引1而不是0开头的所有点，并获得路径的“方向”。如果方向改变，则将两个点中的最后一个（当前而不是前一个）添加到优化的阵列。

优点是点以绘图顺序存储，因此使它们成为路径，而不仅仅是随机（未分类）点。

注意：我正在使用actionscript 3，但我可以理解其他语言或伪代码的语法。

谢谢！

Answer 1

看看Ramer-Douglas-Peucker algorithm

Answer 2

循环遍历以索引1而不是0开头的所有点，并获得路径的“方向”。如果方向改变，则将两个点中的最后一个（当前而不是前一个）添加到优化的阵列。

如果你认为它会有所帮助，你应该认为地球是平的;-)

试试这个：如果路径略有变化，则跳过每一秒，从而减少两倍的点数。如果路径明显改变，请保持节点不变。然后重复一半阈值的“稍微（你的长度加倍，所以你的灵敏度必须增加），直到你在运行后没有做任何改变。

Answer 3

我会考虑你的建议，但在方向改变时保持当前和之前的点。

这样，您最终得到每个线段的第一个和最后一个点。

Answer 4

我认为你最初的想法很棒。我会添加/更改两件事：

1）我会在你的算法中输入一个距离阈值：只有当前测试的点离你最后一个“好”点有一些最小距离时，你是否应该测试它。根据路径数据的来源（可能是磁跟踪器？），由于测量噪声，原始数据中的平稳性可能无法很好地反映出来。这可能导致在非常小的区域中相对大的方向变化，这基本上没有意义。

2）当您检测到足够大的更改时，请不要添加当前测试的点（如您所建议的），而是添加前一个点。否则你最终可能会误导路径。示例（在2D中）：路径由（0,0） - >（1,0） - >（2,0） - >（3,0） - >（4,0） - >（5,5）组成）最终将使用您的方法作为（0,0） - >（5,5），我不认为这是路径的良好表示。更好的是（0,0） - >（4,0） - >（5,5）。