algorithm - O(nlogn) 分而治之算法找到可见线

Question

我正在尝试解决所附图片中显示的问题。我得到了划分部分，您可以在其中递归地将线集分成两半，并且可以看到具有最小和最大斜率的线。

虽然我不知道如何进行合并部分，但我也不理解。

凭直觉，起初，我认为如果没有三条线相交于一点，所有线最终都会可见。

此外，征服部分是我将去除隐形线的时候......据我了解，在征服阶段之前不应该去除任何线。

如果有人能为我们这些脑子有点慢的人解释一下，我将不胜感激! :)

Answer 1

考虑一个 3 行示例。你有两个选择。 a) 只有 2 行可见 b) 所有 3 行都可见。

因此需要判断中间的是否可见。为此，您可以计算外部 2 条线(称为 A)的交点。如果A在中线以上则中间的隐藏，如果在下方则可见(画两个图就很明显了)。

要确定该点是在上方还是下方，请在线方程 (y = ax + b) 中代入它的坐标。如果y > ax + b如果y < ax + b，则该点在线上方点在下面，如果 y = ax + b点就上线了(按问题应该不会发生)

为了解决您的问题，我会按斜率的顺序取线，然后尝试将它们添加到解决方案中。每次添加新行时，检查前一行是否仍然可见，如果不可见则将其删除(根据需要重复多次，因为新行可能隐藏的不仅仅是前一行)。

如果您坚持要进行合并，则需要在合并行上应用此逻辑来计算从中间删除了多少行。