O(nlogn) 分治算法寻找可见线的解决方案

Question

我正在尝试解决附图中显示的问题。我完成了分割部分，在这一步中，您可以将线段集递归地分为两半，并且最小和最大斜率的线段将可见。

但我不知道如何进行合并，并且我还没有完全理解这一部分。

直觉上，起初，如果没有三条相交于一点的线段，那么所有线段最终都应该是可见的。

此外，征服部分是当我要去除看不见的线段时...据我理解，在征服阶段之前不应该去除任何线段。

如果有人能够为我们这些大脑反应稍慢的人解释一下，我将非常感激！ :)

- user1869735

---

没有插图，我们只能猜测...在计算机图形中，未见线条的移除通常是通过计算表面法线来完成的（如果网格是凸的）。在此之前，凹面网格被细分为凸面网格。可能存在其他算法利用了有关其所使用的情况的已知信息，但是如果没有更多信息，很难说您的示例是指什么。如果您的网格是实体的（而不仅仅是线框），则可以使用Z排序或Z缓冲，但我想这不是您想听到的。 - Spektre

Answer 1

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

因此，您需要确定中间一行是否可见。为了做到这一点，您可以计算外部2条线的交点（称之为A）。如果A在中线上方，则中间的那条被隐藏，如果在下方，则可见（绘制这两个图形将很明显）。

要确定点是在上面还是下面，请在线方程中替换其坐标（y = ax + b）。如果 y > ax + b，则该点在线的上方，如果 y < ax + b，则该点在下方，如果 y = ax + b，则该点在线上（根据问题不应发生）。

为解决您的问题，我只需按斜率的顺序取出线并尝试将它们添加到解决方案中。每次添加新线时，请检查前一条线是否仍然可见，并在不可见时删除它（重复多次，因为新线可能会隐藏多个先前的线）。

如果您坚持进行合并操作，您需要在合并行上应用此逻辑，以确定从中间删除多少行。

- Sorin

---

如果我没错的话，这将需要O(n^2)的运行时间。我们能不能用nlgn完成它？ - Riken Shah

由于排序，它是NlogN。添加和删除是O(N)，因为您只会添加一行代码，也许稍后会将其删除（但仅限一次）。 - Sorin

@Sorin，我认为我没有正确理解你的解决方案，因为我想象了一种情况，即没有删除任何行（所有行都可见），在这种情况下，当添加一行时，您将不得不将其与先前添加的所有行进行比较，结果，您将需要O(n^2)。如果您可以更详细地解释您的解决方案，我将不胜感激。 - ganjim

@Sorin 拦截怎么办？以斜率排序的四条线如下：L1=-x; L2=1; L3=x+1;L4=2x+6 在这种情况下，第二行将一直可见，直到第四行将其移除，然而，在您的算法中，当添加第四行时，我们只检查第三行并通过，因此未能删除第二行，而这条线毕竟是不可见的。 - ganjim

@Sorin 抱歉，我的意思是举一个例子，其中对于三行L1、L2、L3，所有三行都是可见的，但是添加第四行后，L2被隐藏了。我意识到这种情况不可能发生，因为如果L4想要移除L2，那么L3和L4的交点将在L2和L4的交点之后，而且由于L4的斜率> L3的斜率，这意味着L4也会移除L3。所以我的反例情况有些无效。我想不出任何其他特殊情况，但我没有理解为什么这样能正常工作。非常感谢你的耐心和解释。 - ganjim