如何在任意角度旋转后，找到多边形在X轴上的最小投影？

Question

给定一个二维多边形的顶点，我需要找到该多边形在X轴上的最小投影。

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

起初，我认为至少有一条多边形的边会与X轴对齐，但这是不正确的。

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

- Bidhan Roy

---

@justhalf 是的，我的直觉很糟糕。 - john

为什么要踩这个问题？看起来很多人都能理解这个问题。 - cdoubleplusgood

我认为正确的直觉应该是“至少有一条边（在将凹多边形转换为凸多边形后）应该垂直于X轴”。 - justhalf

我怀疑 OP 的“最小可能投影”与多边形的最小宽度相同。如果该多边形是凸多边形，那么我认为“旋转卡尺法”会有所帮助。如果该多边形是非凸多边形，则我怀疑其凸包具有相同的最小可能投影。 - High Performance Mark

不是答案，而是简化：您只需要查看凸多边形。因为任何一个顶点在前一个和下一个顶点之间具有内角> 180°（也就是说，“缩进”）的情况永远不可能成为任何投影中的外部顶点。您可以跳过它们并从其余的“外部”顶点构建凸多边形。 - cdoubleplusgood

Answer 1

您要查找的是“旋转卡壳算法”。这个算法可以用于计算凸多边形的最小宽度。您可以在维基百科上了解更多信息，该页面还提供了伪代码以解决您的问题。

维基百科链接：https://en.wikipedia.org/wiki/Rotating_calipers 有关该算法的最小宽度的详细信息，请访问以下链接： https://en.wikipedia.org/wiki/Rotating_calipers#Minimum_width_of_a_convex_polygon

- Nils Pipenbrinck

Answer 2

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

总之，我们得到了一个算法：计算凸包，然后对于凸包的每条边选择使其与Y轴平行的角度并测试宽度。取最小值。

- Michael Simbirsky

Answer 3

设X(i, alpha)为顶点i绕alpha旋转后的X坐标。

我们始终假设-PI <= alpha <= PI。

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

让我们证明以下结论：如果X(i, alpha) >= X(j, alpha)，且X(i, beta) >= X(j, beta)，且beta-alpha < PI，则对于[alpha, beta]中的所有gamma，都有X(i, gamma) >= X(j, gamma)。实际上，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

现在我们有：

• 如果rightmost(alpha)=rightmost(beta)且beta-alpha < PI，则对于所有alpha < x < beta，rightmost(x)=rightmost(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])。

这足以通过二分搜索获得哪个区间中哪个点是最右边的。通过角度的符号反转，我们可以得到最左边的点区间。由于我们知道每个点在哪个区间是最左边的，也是最右边的，因此我们可以计算出区间之间的边界值，并选择最小值。

- user31264