查找形状在x轴上宽度可能最小的旋转
我正在玩弄一个形状问题，我正在寻找一个比我所能想到的更聪明的解决方案。
以下是问题所在：
我有一组点，它们在笛卡尔网格上形成一个封闭的形状，比如A(-1,0)，B(1,0)和C(0,4)，它们形成了一个锐角三角形。
我已经以一种稍微不那么令人困惑的方式重写了这一点。以上面的形状为例，想象你可以自由地旋转它。我正在寻找我们只考虑x轴的旋转，并且最西点和最东点之间的距离是最小的。
当考虑到上面的形状时，这个距离是A和B之间的距离。而对于更有趣的形状，点之间的距离可能更短，我相信没有办法旋转上面的形状，使得西部和东部大多数点的距离小于A和B之间的距离。
到目前为止，我唯一的解决方案是绘制点，旋转1度，存储旋转关键的最大距离。重复冲洗，然后取最小的。这看起来有点笨拙，我知道必须有一种更合理的数学方法来解决这个问题。
有什么想法吗？
回答 4
Stack Overflow用户
发布于 2012-03-15 16:34:09
进行主成分分析，并将主成分与y轴对齐。这将优化从每个点到y轴的“平均”平方距离(即x轴上的宽度)。也许根据您的标准，这也是最优或接近最优的。
请参阅：http://en.wikipedia.org/wiki/Principal_component_analysis
备选方案(最优解)：
首先计算点的凸包。请注意，具有最大x宽度的两个点始终位于凸包中。
现在，对于凸包中的每个线段，找到最远的顶点并记下距离。找到距离最小的(线段，最远的顶点)对。最佳旋转是将直线段在垂直方向上对齐的旋转。
复杂度：O(nlogn)表示凸包部分，O(m^2)表示第二部分，其中m是凸包上的点数。
Stack Overflow用户
发布于 2012-03-16 00:39:24
设{N}是定义包含形状的最小凸多边形的点集，按顺时针顺序排序。对于每条边(N - 1，N)：确定从该边到最远点的距离。取这些距离中最短的一个，旋转您的形状，使相应的边垂直于X轴。
Stack Overflow用户
发布于 2012-03-16 11:50:53
Rotating Calipers是解决这一问题的好工具。
更具体地说，需要构造凸包，然后求出凸多边形的宽度。
https://stackoverflow.com/questions/9723772
复制
相似问题
如何使用设计为不同的用户模型配置路由？
以作用域为不同类的别名Rails模型
为域模型设计类图
不同模型上的条件作用域
Spring Prototype作用域bean，配置的设计模式
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
