寻找一种旋转方式，使得该形状在x轴上的宽度最小。

Question

我正在思考一个形状问题，希望找到比我目前想出的更精巧的解决方案。

问题如下：

在笛卡尔坐标系中，我有一组点形成了一个封闭的图形，例如A（-1,0），B（1,0）和C（0,4），它们形成一个锐角三角形。

我稍微简化了一下这个问题。想象一下上面的形状可以自由旋转。 我正在寻找的是旋转方式，只考虑x轴，西侧和东侧最远点之间的距离最小。

在考虑上述形状时，该距离将是A和B之间的距离。而对于更有趣的形状，可能存在更短的点之间距离，但我相信没有办法旋转上述形状，使西侧和东侧的最远点之间的距离小于A和B之间的距离。

我的唯一解决方案是绘制点，旋转1度，存储由旋转键入的最大距离。反复操作并取最小值。这似乎有些笨拙，我知道肯定有更数学合理的方法来解决这个问题。

有什么想法吗？

- nsfyn55

Answer 1

执行主成分分析并将主成分与y轴对齐。这将优化每个点到y轴的“平均”平方距离（即x轴上的宽度）。也许根据您的标准，这也是最优解或接近最优解。

参见：http://en.wikipedia.org/wiki/Principal_component_analysis 替代方案（最优解）：

首先计算点的凸包。请注意，具有最大x宽度的两个点始终位于凸包中。

现在，对于凸包中的每个线段，找到最远的顶点并记录距离。找到具有最小距离的（线段，最远顶点）对。最佳旋转是将该线段与垂直方向对齐。

复杂度：凸包部分为O（nlogn），第二部分为O（m ^ 2），其中m是凸包上的点数。

- ElKamina

---

@BlueRaja-DannyPflughoeft 是的！这就是为什么我说“也许根据您的标准，这也是最优或接近最优的”。 - ElKamina

原始答案既不是最优的，也不是“接近最优的”。想象一堆点紧密聚集在一起，还有几个离得比较远；最小化平均值将会把簇放在y轴附近，而OP问题的解决方案可能会让簇更靠近中间。现在，也许PCA也可以用来找到OP问题的解决方案*(我对此了解不够)*，但如果是这样的话，应该在您的答案中进行解释——因为目前而言，这只是针对完全不同问题的答案。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft，我不理解你与倾斜的平行四边形的争论。ElKamina是正确的，最优解会与凸包中的线段与y轴对齐。三角形中最小的距离始终是三角形的高度，因此我们需要将相应的边与y轴对齐。 - Szabolcs

@BlueRaja-DannyPflughoeft 同时，对于凸包的主成分分析（PCA）将会给出一个相当不错的近似。楼主应该评论一下他为什么需要这个以及优先权是什么（实现简易性，性能，精度等）。 - Szabolcs

@Szabolcs：啊，我明白了——我错误地认为倒数第二段中的“那条线段”指的是跨越对踵点*(线段、顶点)的线段。我相信*你们两个都是对的，这将起作用。请注意，通过在对偶图上进行二分搜索，最长的对踵点实际上可以在O(m log m)内找到。 - BlueRaja - Danny Pflughoeft

Answer 2

设{N}为定义包含您的形状的最小凸多边形的点集，按顺时针顺序排序。对于每条边(N-1，N)：确定该边到最远点的距离。取这些距离中的最短距离，并旋转您的形状，使相应的边垂直于X轴。

- gcbenison

---

这与ElKamina所说的相同。可能表述得更清晰一些。 - Szabolcs

Answer 3

旋转卡壳是解决这个问题的好工具。

更具体地说，需要构建凸包，然后找到凸多边形的宽度。

- MBo

Answer 4

我不确定您对数学的掌握程度，如果这超出了您的理解范围，或者解释过于简单，请接受我的道歉。但是，我立即想到的解决方案是，在固定角度下对多边形宽度的离散采样使用傅里叶分析。

您的方法是通过旋转一小部分并进行测试来考虑连续函数的离散采样。

我们知道，对于每个可能的旋转，都存在一个定义所需测量的连续函数，您只是在设置点上评估它。也就是说，已知角度到多边形宽度函数存在，并且我们可以在足够的时间内评估有限数量的角度的多边形宽度。

因此，假设我们能够找到一个用基本函数表示这个角度到宽度函数的表达式，我们就可以通过解方程来确定所有可能产生最小宽度的角度。

我们知道，因为您旋转了2PI弧度，所以宽度函数将是2PI周期性的，因此，通过应用傅里叶分析，您可以完美地重构函数，只要采样足够的角度。

问题是，需要多少样本才能产生函数的完美重构？

我认为这取决于边界点之间的最小距离。

ceil(perimiterLength/smallestDistanceBetweenPoints);

简而言之，我正在通过沿着边界放置均匀间隔的样本来重新采样边界的周长，使用的间距等于或小于最小距离。让我们称这个数字为n。（老实说，我不太确定这是否正确）

在2PI弧度中通过n个均匀间隔的角度对东西方向的点进行采样，并将它们的差作为n点角度到宽度函数进行绘制。

对此图形进行傅里叶变换，以给出定义距离函数所需的一组实傅里叶级数系数集合。

使用您喜欢的任何方法来识别函数的最小值。

因此，我想对于您的三角形示例，您需要确定您需要ceil（3 + root（3））= 5个样本。在0 2pi / 5 4pi / 5 6pi / 6和8pi / 5处计算距离，对此结果进行傅里叶变换并重构信号，创建类似的公式。

a0 + a1 sin (t) + a2 sin (2t)

然后你必须确定这个函数的最小值（有很多选项可供选择）

- Matt Esch