geometry - 如何计算边界多边形？

Question

我有一堆 2D 点，我想计算包含所有这些点的多边形的周长。

这个数学过程有名字吗，我可以用谷歌搜索一下，或者有人可以告诉我如何开始思考这个问题吗？

Answer 1

您可能正在寻找凸包和凸包算法。

最简单的二维算法之一是礼品包装算法。引用维基百科：

它具有 O( nh ) 时间复杂度，其中n是点数，h是凸包上的点数。与其他凸包算法相比，它的实际性能在n较小或h相对于n非常小时是有利的。在一般情况下，该算法的性能优于许多其他算法。

因此，根据问题的大小，您可能需要查看上面链接的算法页面以找到更高级的方法。

Answer 2

一个定义明确的多边形是凸包。有几种经过充分研究的算法来寻找凸包。