mis*_*ish 8 algorithm geometry bounding-box
我正在努力计算一组点的最小封闭矩形(任意对齐).
我能够使用格雷厄姆算法计算凸包.
我陷入困境的是下一步.我想过使用旋转卡尺方法,但我似乎无法找到对算法的充分解释.
如果你有凸包,那么基本算法很容易.你只需要穿过凸包的每个边缘并旋转你的点,使边缘沿着一个主轴,比如说X轴.然后,您会找到这些点的轴对齐边界框.选择最小的边界框.
通过获取每个维度中的最小值和最大值,可以找到轴对齐的边界框.
如果以相反的量旋转边界框,它现在将包围原始点.
为了提高效率,请注意可以影响边界框的唯一点在凸包上.
为了使它真正有效,请注意凸壳周围只有四个点在任何时候都接触到边界框(这不是严格意义上的,但现在忽略它).如果旋转点足够使下一条边与边界框对齐,则其中三个点相同,其中一个点将替换为凸包周围的下一个点.这使您可以创建一个与凸包上的点数成线性关系的算法.
现在有两种边缘平行或垂直的特殊情况.这将导致任何时候超过四个点触及边界框,但实际上并不重要.如果您可以选择下一个使用的两个平行边缘中的哪一个,您可以随意选择一个.