凸包可以用一组点简要的描绘轮廓的形状,在计算机视觉中有广泛的应用。解算凸包最大内接N边形也是常见的问题。这篇博客介(摘)绍(抄)这一问题的一种解法。

算法出处

很老的一篇文章,算法在文章最后

https://ieeexplore.ieee.org/document/4567996?tp=&arnumber=4567996&url=http:%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4567996

算法伪代码

凸包的最大内接N边形

算法说明

凸包N边形的顶点一定再凸包上,N边形顶点一定是凸包点。计算最大N边形的过程,需要不断移动和改变顶点,不断比较面积。

移动点的策略就是,首先移动最末尾P(n)(这里的最末尾指N变形顺时针方向的最后一个点),当移动后比移动前N边形面积更大时,就可以移动P(n-1)了。然后同样的策略移动P(n-1),每次移动P(n-1)之后都需要再移动P(n),这样一直向上到P(1)。多重循环退出的含义是,不再有任何顶点的移动,导致凸包N边形面积更大。

代码实现

对于四边形来说,代码实现是这样子的。其中Area为凸包面积函数,可以对应于opencv中的ContourArea函数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注