我有一组不同的二维向量(实数)，指向不同的方向。我们可以选择一对向量并构造它们的线性组合，使得系数为正且它们的和为 1。 简而言之，我们可以对任意两个向量进行“加权平均”。
我的目标是针对任意方向选择一对向量，其“加权平均值”在该方向上并最大化。 从代数上讲，给定向量 a 和 b 以及一个方向向量 n 我们有兴趣最大化这个值:
[ a 交叉 b ]/[ (a - b) 交叉 n]
即选择最大化此值的a 和b。
具体来说，这个问题的应用是帆船。对于每个明显的风向，船都会有一个由极坐标图给出的速度。这是此类图表的示例:
(图中的每条线对应一个特定的风力大小)。请注意每个方向上大约 30 度的“不可能”前扇区。
因此在某些方向上速度会很高，在某些方向上速度会很低，并且在某些方向上不可能直接航行(例如在完全与风相反的方向上)。
如果我们需要朝无法直接航行的方向前进(或者速度不是最佳的)——可以曲折前进。这称为定位。
现在，我的目标是重新计算一个新图表，该图表直接或间接表示任何方向的平均前进速度。例如，对于上图，更正后的图是这样的:
请注意，不再有“不可能”的方向。对于某些方向，图表类似于原始方向，最好直接前进，不需要机动。对于其他人 - 它显示了假设定期执行最佳机动时该方向上的最大平均前进速度。
计算这个的最佳算法是什么？假设该图是一组离散的方位角-速度对，我们可以从中计算矢量。
到目前为止，我只是检查所有向量对以选择最好的。好吧，有截止标准，例如只选择在前进方向上具有正投影和相反垂直投影的向量，但复杂度仍然是 O(N^2)。 我想知道是否有更高效的算法。
编辑
非常感谢@mcdowella。对于计算机科学和水手的答案!
我也从凸多边形的角度考虑过，发现只值得在该船体上探测向量(即，如果您在该船体上叠加 2 个向量，并尝试用一个向量替换其中一个，而该向量不是' t 在这个船体上，结果会更糟，因为新向量在所需方向上的投影比两个源向量都差)。
但是我没有意识到2个向量的任何“加权平均”实际上是连接这些向量的直线段，因此最终的图表确实是这个凸包!而且，正如我们所看到的，这也与我通过“暴力”算法计算出的结果一致。
最佳答案
现在是计算机科学答案
定位策略为您提供构成定位的腿部矢量的凸组合。
因此请考虑图表中仅由一个轮廓构成的轮廓。所有可能的最佳速度和方向的集合是通过将向量的所有凸组合到轮廓而形成的凸多边形。所以你想要做的是形成轮廓的凸包(https://en.wikipedia.org/wiki/Convex_hull)。要了解如何在任何特定方向上快速前进，请将该矢量与凸包相交，并使用与您相交的凸包边缘两侧的角相对应的大头钉。
看你的图表，等高线是凹的直上风和直下风，这是你所期望的。然而，还有另一个凹形部分，在 4 点钟和 5 点钟之间的某处，并且在 7 点钟和 8 点钟之间对称，在您更正的图表中显示为一条直线 - 所以我想有第三个方向可以插入，在风的同一侧使用两条河段，我从传统帆船中看不到这一点。
关于为最佳 "zigzag"配置文件选择一对向量的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48529693/