找到最小角度以包含平面中的所有点

我想用python编写一个代码,该代码将求解最小角度(θ),该角度将在给定任意数量的点的情况下包括2D平面中的所有点。角度的顶点始终以原点(0,0)为中心。这些点是使用具有(x,y)值的笛卡尔坐标系定义的。下图显示了可视化。关于如何应对这个问题有任何想法吗?

Visualization

评论
保质期
保质期
  • 将每个笛卡尔表示形式转换为极坐标。
  • 按参考角度排序。
  • 减去相邻参考角以获得相邻向量之间的角度。确保将最后一个点和第一个点作为另一个角度进行计算。

确定相邻向量之间的最大角度。该角度的相对侧是包含所有点的最小角度。

For instance, using the canonical representation -- counter-clockwise from the x-positive ray -- you would find the reference angle for each polar vector. Sorted, you would have the list [d, c, b, a, e, f].

接下来,计算角度dOc,cOb,bOa,...和fOd。

您注意到,aOe是它们中最大的角度,都略大于整个弧度。

因此,eOa是所需角度。

点赞
评论