Bid*_*Roy 5 c++ algorithm geometry rotation computational-geometry
给定2D多边形的顶点,我必须找到多边形在X轴上的最小可能投影.
我被允许以任意角度旋转多边形.
起初我认为在最小的情况下,至少有一个多边形的边将与X轴对齐,这是不正确的.
多边形可以是凹的或凸的.
您正在寻找的是"旋转卡尺算法".
https://en.wikipedia.org/wiki/Rotating_calipers
关于此算法的维基百科页面甚至包含针对您的问题的伪代码.
https://en.wikipedia.org/wiki/Rotating_calipers#Minimum_width_of_a_convex_polygon
正如评论中所述，如果用凸包替换多边形，答案将不会改变。所以我们认为多边形已经是凸的。现在假设我们找到了最小角度。这意味着我们有一条平行于 Y 的条带来界定身体。很容易看出多边形的一条边可以位于条带边界上（如果不是，我们可以稍微旋转主体而不增加条带宽度）。
总结一下，我们得到一个算法：计算凸包，然后为凸包的每一侧选择一个使其平行于 Y 的角度并测试宽度。取分钟。0