5

给定二维多边形的顶点，我必须找到多边形在X轴上的最小可能投影。

我可以以任意角度旋转多边形。

起初我认为对于最小的情况，多边形的至少一个边将与X轴对齐，这是不正确的。

多边形可以是凹的或凸的。

4

3 回答 3

6

您正在寻找的是所谓的“旋转卡尺算法”。

https://en.wikipedia.org/wiki/Rotating_calipers

关于这个算法的维基百科页面甚至有你的问题的伪代码。

https://en.wikipedia.org/wiki/Rotating_calipers#Minimum_width_of_a_convex_polygon

于 2013-11-06T09:59:47.440 回答
2

如评论中所述，如果您用凸包替换多边形，答案将不会改变。所以让我们认为多边形已经是凸的。现在假设我们找到了最小角度。这意味着我们有一条平行于 Y 的条带包围身体。很容易看出，多边形边之一可以位于条带边界上（如果不是，我们可以稍微旋转主体而不增加条带宽度）。

总而言之，我们得到一个算法：计算凸包，然后为包的每一侧选择一个使其平行于 Y 的角度并测试宽度。采取分钟。0

于 2013-11-06T09:09:25.980 回答
0

令 X(i, alpha) 为顶点 i 在旋转角度 alpha 后的 X 坐标。

我们总是假设 -PI <= alpha <= PI 。

如果所有 j 的 X(i, alpha)>=X(j, alpha)，则令 i=rightmost(alpha)。令 i=second_rightmost(alpha) 如果 X(i, alpha)>=X(j,alpha) 对于除一个之外的所有 j 。类似地定义 leftmost() 和 second_leftmost()。

让我们证明以下内容：如果 X(i, alpha) >= X(j, alpha)，并且 X(i, beta) >= X(j, beta)，并且 beta-alpha < PI，那么 X(i, gamma) >= X(j, gamma) 对于所有 gamma 中的 alpha, beta]。实际上，X(i, alpha)=x[i]*cos(alpha)-y[i] * sin(alpha)，其中 (x[i], y[i]) 是顶点 i 的初始位置。因此，X(i, a) - X(j, a) = c1*cos(a)-c2*sin(a)，其中 c1=x[i]-x[j],c2=y[i]- y[j]。令 f(a)=X(i,a)-Y(i,a)。函数f是连续的，当tan(a)=c1/c2时符号改变，即a=atan2(c1,c2)+PI*n。如果 beta-alpha

现在我们有：

  • 如果最右（alpha）=最右（beta）并且 beta-alpha < PI，那么对于所有 alpha < x < beta，最右（x）=最右（alpha）。
  • 如果 i=rightmost(alpha)=second_rightmost(beta)，并且 j=rightmost(beta)=second_rightmost(alpha)，并且 beta-alpha < PI，则对于 alpha 和 beta 之间的所有 x，rightnost(x) 是 i 或j，变化点为 atan2(y[i]-y[j], x[i]-x[j])。

这足以通过二分查找在哪个间隔获得最右边的点。通过角度的符号反转，我们得到最左边的点间隔。由于我们知道每个点在哪个区间最左边，每个点在最右边，我们可以计算区间边界处的值，并选择最小的那个。

于 2013-11-06T09:38:45.000 回答