算法 select 一对最佳 "zigzag" 配置文件的向量
algorithm to select a pair of vectors for the best "zigzag" profile
我有一组不同的二维向量（实数），指向不同的方向。我们可以选择一对向量并构造它们的线性组合，使得系数为正且它们的和为 1。
简单来说，我们可以取任意两个向量的 "weighted average"。
我的目标是任意方向选取一对"weighted average"在这个方向上并且最大化的向量。
从代数上讲，给定向量 a 和 b 以及一个方向向量 n 我们有兴趣最大化这个值：
[ a 交叉 b ] / [ (a - b) 交叉 n ]
即选择 a 和 b 来最大化这个值。
具体来说，这个问题的应用是 sailing 船。对于每个明显的风向，船都会有一个由极坐标图给出的速度。这是此类图表的示例：
（图中每条线对应一个特定的风力大小）。请注意 "impossible" 每个方向大约 30 度的前扇区。
因此在某些方向上速度会很高，在某些方向上速度会很低，并且对于某些方向来说不可能直接sail（例如在与风完全相反的方向上）。
如果我们需要朝无法直接 sail 的方向前进（或者速度不是最佳的）- 可以曲折前进。这就是所谓的跟踪。
现在，我的目标是重新计算一个新图表，该图表直接或间接表示任何方向的平均前进速度。例如，对于上图，更正后的图是这样的：
请注意，没有更多 "impossible" 方向。对于某些方向，图表类似于原始方向，最好直接前进，不需要机动。对于其他人 - 它显示了假设定期执行最佳机动时该方向上的最大平均前进速度。
计算这个的最佳算法是什么？假设该图是一组离散的 azimuth-velocity 对，我们可以从中计算向量。
到目前为止，我只是检查了所有向量对，以 select 最好。好吧，有 cut-off 标准，例如只选择在前进方向上具有正投影和相反垂直投影的向量，但复杂度仍然为 O(N^2)。
请问有没有更高效的算法
编辑
非常感谢@mcdowella。对于 computer-science 和 sail 或答案！
我也考虑过凸多边形，发现只值得在该船体上探测向量（即，如果您在该船体上叠加 2 个向量，并尝试用一个向量替换其中一个不在这个船体上，结果会更糟，因为新向量在所需方向上的投影比两个源向量都差。
然而我没有意识到2个向量中的任何"weighted average"实际上是连接这些向量的直线段，因此最终的图表确实是这个凸包！而且，正如我们所看到的，这也与我通过 "brute-force" 算法计算出的一致。
首先是前激光水手的回答
至少对于逆风或顺风直行，明显的猜测是调整风向，使每条腿的长度相同，并且对风的方位相同。如果极坐标图围绕逆风-顺风轴对称，这是正确的。假设逆风是 Y 轴，可能的航段是 (A, B)、(-A, B)、(a, b) 和 (-a, b)。对称定位移动 (A, B)/2 + (-A, B)/2 = (0, B)，另一个对称定位移动 (0, b)。不对称跟踪是 (-A, B)a/(a+A) + (a, b)A/(a+A) = (0, (a/(a+A))B + (A/(a+ A))b) 并且如果 b!=B 位于 b 和 B 之间，因此不如 b 或 B 中最好的那个好。
对于位于左舷和右舷之间的任何方向，您将采取逆风航行，明显的策略是改变这些腿的长度而不是它们的方向，以便行进的平均矢量在需要的方向。这是最好的策略吗？如果不是，更好的策略是逆风前进，而不是逆风前进，我认为这是一个矛盾 - 所以对于位于左舷和右舷之间的任何方向，逆风前进我认为最好的策略确实是做这些大头钉，但改变腿的长度以朝着所需的方向前进。同样的事情也适用于顺风顺风航行，如果你有一艘船，顺风顺风航行是个好主意。
现在计算机科学答案
大头钉策略为您提供构成大头钉的腿部矢量的凸组合。
因此请考虑图表中仅由一个等高线构成的轮廓。所有可能的最佳速度和方向的集合是通过将向量的所有凸组合到轮廓而形成的凸多边形。所以你想要做的是形成轮廓的凸包（https://en.wikipedia.org/wiki/Convex_hull）。要了解如何在任何特定方向上快速前进，请将该矢量与凸包相交，并使用与您相交的凸包边缘两侧的角相对应的大头钉。
看你的图，轮廓是凹直的上风和直下风，这是你所期望的。然而，还有另一个凹形部分，在 4 点钟和 5 点钟之间的某处，并且在 7 点钟和 8 点钟之间对称，在您更正的图表中显示为一条直线 - 所以我想有第三个方向可以插入，在风的同一侧使用两条河段，我在传统航行中无法识别。
我有一组不同的二维向量（实数），指向不同的方向。我们可以选择一对向量并构造它们的线性组合，使得系数为正且它们的和为 1。 简单来说，我们可以取任意两个向量的 "weighted average"。
我的目标是任意方向选取一对"weighted average"在这个方向上并且最大化的向量。 从代数上讲，给定向量 a 和 b 以及一个方向向量 n 我们有兴趣最大化这个值：
[ a 交叉 b ] / [ (a - b) 交叉 n ]
即选择 a 和 b 来最大化这个值。
具体来说，这个问题的应用是 sailing 船。对于每个明显的风向，船都会有一个由极坐标图给出的速度。这是此类图表的示例：
（图中每条线对应一个特定的风力大小）。请注意 "impossible" 每个方向大约 30 度的前扇区。
因此在某些方向上速度会很高，在某些方向上速度会很低，并且对于某些方向来说不可能直接sail（例如在与风完全相反的方向上）。
如果我们需要朝无法直接 sail 的方向前进（或者速度不是最佳的）- 可以曲折前进。这就是所谓的跟踪。
现在，我的目标是重新计算一个新图表，该图表直接或间接表示任何方向的平均前进速度。例如，对于上图，更正后的图是这样的：
请注意，没有更多 "impossible" 方向。对于某些方向，图表类似于原始方向，最好直接前进，不需要机动。对于其他人 - 它显示了假设定期执行最佳机动时该方向上的最大平均前进速度。
计算这个的最佳算法是什么？假设该图是一组离散的 azimuth-velocity 对，我们可以从中计算向量。
到目前为止，我只是检查了所有向量对，以 select 最好。好吧，有 cut-off 标准，例如只选择在前进方向上具有正投影和相反垂直投影的向量，但复杂度仍然为 O(N^2)。 请问有没有更高效的算法
编辑
非常感谢@mcdowella。对于 computer-science 和 sail 或答案！
我也考虑过凸多边形，发现只值得在该船体上探测向量（即，如果您在该船体上叠加 2 个向量，并尝试用一个向量替换其中一个不在这个船体上，结果会更糟，因为新向量在所需方向上的投影比两个源向量都差。
然而我没有意识到2个向量中的任何"weighted average"实际上是连接这些向量的直线段，因此最终的图表确实是这个凸包！而且，正如我们所看到的，这也与我通过 "brute-force" 算法计算出的一致。
首先是前激光水手的回答
至少对于逆风或顺风直行，明显的猜测是调整风向，使每条腿的长度相同，并且对风的方位相同。如果极坐标图围绕逆风-顺风轴对称，这是正确的。假设逆风是 Y 轴，可能的航段是 (A, B)、(-A, B)、(a, b) 和 (-a, b)。对称定位移动 (A, B)/2 + (-A, B)/2 = (0, B)，另一个对称定位移动 (0, b)。不对称跟踪是 (-A, B)a/(a+A) + (a, b)A/(a+A) = (0, (a/(a+A))B + (A/(a+ A))b) 并且如果 b!=B 位于 b 和 B 之间，因此不如 b 或 B 中最好的那个好。
对于位于左舷和右舷之间的任何方向，您将采取逆风航行，明显的策略是改变这些腿的长度而不是它们的方向，以便行进的平均矢量在需要的方向。这是最好的策略吗？如果不是，更好的策略是逆风前进，而不是逆风前进，我认为这是一个矛盾 - 所以对于位于左舷和右舷之间的任何方向，逆风前进我认为最好的策略确实是做这些大头钉，但改变腿的长度以朝着所需的方向前进。同样的事情也适用于顺风顺风航行，如果你有一艘船，顺风顺风航行是个好主意。
现在计算机科学答案
大头钉策略为您提供构成大头钉的腿部矢量的凸组合。
因此请考虑图表中仅由一个等高线构成的轮廓。所有可能的最佳速度和方向的集合是通过将向量的所有凸组合到轮廓而形成的凸多边形。所以你想要做的是形成轮廓的凸包（https://en.wikipedia.org/wiki/Convex_hull）。要了解如何在任何特定方向上快速前进，请将该矢量与凸包相交，并使用与您相交的凸包边缘两侧的角相对应的大头钉。
看你的图，轮廓是凹直的上风和直下风，这是你所期望的。然而，还有另一个凹形部分，在 4 点钟和 5 点钟之间的某处，并且在 7 点钟和 8 点钟之间对称，在您更正的图表中显示为一条直线 - 所以我想有第三个方向可以插入，在风的同一侧使用两条河段，我在传统航行中无法识别。