algorithm - 创建一个“不透明”的正方形

Question

我正在编写一个程序，该程序根据用户为每个正方形给出的边的坐标和长度将正方形的周长打印到屏幕上。

如果正方形重叠，则它们应该在彼此的顶部，以便底部的正方形被顶部的隐藏。

方块的顺序是根据它们进入程序的顺序设置的（​​首先是底部）。

例如：

&&&&
& &
& &$$$
&&&& $
    $ $
    $ $
    $$$$$

我想出的最佳算法是每个正方形的时间复杂度为 O(n^2)。

关于如何使正方形“不透明”的任何建议？

Answer 1

您提到的O(n^2)算法可能是经典的“画家算法”，您可以在其中简单地从底部到顶部一个接一个地渲染（“光栅化”）正方形。这是一个非常好的算法，广泛用于计算机图形学。O(n^2)但是，任何“光栅”算法都将具有相同的每平方时间复杂度。

但是如果你想要一个渐近更快的算法，你必须寻找一个“向量”算法，即适用于正方形边缘的算法，但不会浪费时间处理它们的内部。构建这种算法的一种方法是预先计算矢量形式的最终可见边缘布局，然后仅在屏幕上绘制可见边缘。

为了实现类似的东西，每个正方形最初必须由一组四个边表示。然后单遍扫描线算法将消除不可见的边缘。然后您可以在屏幕上渲染剩余的可见边缘。该算法将比“画家算法”复杂得多，因为您必须实现扫描和边缘消除逻辑。但是对于这个特殊的问题（特别是考虑到它涉及正交几何），它一点也不难。

PS这里的一个关键点是，后一种方法只有在预先知道所有方格的情况下才能工作，即它只适用于离线问题。如果您正在处理在线问题，即您必须在从输入接收到正方形时立即绘制正方形，而不是事先知道所有正方形，那么在一般情况下，没有理由尝试在这里改进任何东西。只需使用画家的算法。