我正在尝试解决附图中显示的问题。我完成了分割部分,在这一步中,您可以将线段集递归地分为两半,并且最小和最大斜率的线段将可见。 但我不知道如何进行合并,并且我还没有完全理解这一部分。 直觉上,起初,如果没有三条相交于一点的线段,那么所有线段最终都应该是可见的。 此外,征服部分是当我要去除看不见的线段时...据我理解,在征服阶段之前不应该去除任何线段。 如果有人能够为我们这些大脑反应稍慢的人解释一下,我将非常感激! :)
考虑一个三行的例子。你有两个选择。a) 只有2行可见 b) 所有3行都可见。因此,您需要确定中间一行是否可见。为了做到这一点,您可以计算外部2条线的交点(称之为A)。如果A在中线上方,则中间的那条被隐藏,如果在下方,则可见(绘制这两个图形将很明显)。要确定点是在上面还是下面,请在线方程中替换其坐标(y = ax + b)。如果 y > ax + b,则该点在线的上方,如果 y < ax + b,则该点在下方,如果 y = ax + b,则该点在线上(根据问题不应发生)。为解决您的问题,我只需按斜率的顺序取出线并尝试将它们添加到解决方案中。每次添加新线时,请检查前一条线是否仍然可见,并在不可见时删除它(重复多次,因为新线可能会隐藏多个先前的线)。如果您坚持进行合并操作,您需要在合并行上应用此逻辑,以确定从中间删除多少行。