algorithm - 需要算法来绘制重叠的矩形

Question

我需要帮助来有效地绘制/剔除一系列不透明的矩形，换句话说，这是 table 上的一堆索引卡。具体是:

• 没有旋转，所以一切都是简单的整数坐标，轴对齐
• 卡片完全不透明
• 卡片的 X,Y 位置可以是任意整数
• 所有卡片的大小都相同
• 我有一个 z 顺序的卡片列表

我认为我(基本上)有两个选择:

1) brute force painter 的方法，其中桌面视口(viewport)中的所有卡片都以反向 z 顺序完全绘制。优点:简单。缺点:a) 需要一个屏幕外缓冲区以避免闪烁，b) 可能会浪费大量时间来绘制每张卡片的昂贵区域，而该区域最终可能会被遮挡，最坏的情况是整个卡片都被覆盖。

2) 一种为每张卡片生成可见(或模糊)矩形列表的算法，以便仅绘制可见部分。

选项 2 是我需要建议的地方，尤其是在算法方面，以及“更智能”绘制周期的优缺点。

任何与语言/平台无关的建议都将受到赞赏。如果重要，这将在 MS Windows 上实现。

愿意接受任何建议，包括混合方法。我意识到一个精确的答案可能非常依赖于代码的细节，但即使是在这一点上，我也会很高兴有一般化的概念!

附加说明:可能会有数千张卡片相互堆叠，因此我非常有动力避免使用纯粹的暴力画家方法 - 至少不需要某种预处理来完全剔除被遮挡的卡片。这同样适用于许多紧密平铺的卡片，更糟糕的情况是只显示它们的边框 - 如果可能的话，我想在这些情况下跳过绘制复杂的内部结构。

Answer 1

如果只绘制每张卡片从最底部到最顶部的轮廓线呢？然后你可以做一个洪水填充来绘制轮廓内部。这样，您只需重新绘制与存在交叉点的边界相对应的几个像素。

编辑:上传图片以帮助我解释这个想法。

第一步是标记卡片的边界并指定其 Z 顺序(左上图)。这样，就有了覆盖，但只覆盖了少量像素的边界。

之后，您可以按照以下两个规则绘制卡片的纹理(首先是最低的 Z 顺序):

• 你从边界开始，在空白处涂色，直到到达边界；
• 如果边框的 Z 顺序是当前顺序，则绘制它；
• 如果找到的边框的 Z-order 小于当前的 Z-order，则继续绘制，就像它是空白的一样；
• 否则，您会发现一个具有更大 Z 顺序的边界，因此您会跳过该 block ；
• 下一张卡片。

希望对您有所帮助:)