algorithm - 获取一组二维点的周长

Question

我有一组二维点（ x 和 y 的坐标），现在我需要丢弃所有对我没有意义的点，我的意思是我只对这个点的区域感兴趣正在追踪。

简而言之，这

它应该产生这个

问题：什么算法可以在这个点上做这种过滤？

Answer 1

您可以使用Graham Scan计算给定点的凸包。一旦你有了凸包上的所有点，你就可以消除其他点。

还有其他算法用于计算凸包，但格雷厄姆扫描很容易实现并且是 O(n logn)。

Answer 2

我相信您正在寻找凸包算法。我个人使用格雷厄姆扫描算法来实现凸包，因为它具有非常好的复杂性O(n*log(n))并且相对容易实现。