algorithm - 变半径圆覆盖算法

Question

对于一个游戏，我正在绘制由数千个随机分布的圆圈组成的密集簇，这些圆圈具有不同的半径，由一系列 (x,y,r) 三元组定义。这是一个包含 14,000 个圆圈的示例图像:

我想到了一些动态效果，例如合并簇，但要实现这一点，我需要每帧重新绘制所有圆圈。

许多(可能是 80-90%)绘制的圆圈被后续绘制覆盖。因此我怀疑通过预处理我可以通过消除覆盖的圆来显着加快我的绘制循环。是否有一种算法能够以合理的效率识别它们？

我可以容忍相当多的漏报(即绘制一些实际被覆盖的圆圈)，只要数量不多到影响绘制效率即可。我也可以容忍误报，只要它们几乎是正的(例如，删除一些仅覆盖 99% 的圆圈)。我也愿意改变圆圈的分布方式，只要它看起来还不错。

Answer 1

这种剔除本质上就是隐藏面算法 (HSA) 所做的 - 特别是称为“对象空间”的变种。在您的情况下，圆圈的排序顺序为它们提供了有效的恒定深度坐标。它是常数的事实简化了问题。

关于 HSA 的经典引用是 here .我会阅读它以获取想法。

受这种想法启发的一个想法是用“扫线”算法来考虑每个圆，比如一条从上到下移动的水平线。扫描线包含它所接触的一组圆。通过按顶部坐标对圆的输入列表进行排序来初始化。

扫描在“事件”中前进，事件是每个圆的顶部和底部坐标。到达顶部后，将圆圈添加到扫描中。当它的底部出现时，将其移除(除非它已经如下所述消失)。当一个新的圈子进入扫描范围时，将它与已经存在的圈子进行比较。您可以将事件保存在最大(y 坐标)堆中，根据需要延迟添加它们:下一个输入圆的顶部坐标加上所有扫描线圆的底部坐标。

进入扫荡的新圈子可以做 3 件事中的任何一个或全部。

1. 扫描中的模糊圆圈具有更大的深度。 (由于我们正在识别不要绘制的圆，因此该决定的保守方面是使用新圆的最大包含轴对齐框 (BIALB) 来记录每个现有更深圆的遮挡区域.)

2. 被其他深度较小的圆圈遮挡。 (这里保守的做法是用彼此相关圈的BIALB记录新圈的遮挡区域。)

3. 有没有被遮挡的区域。

必须保持每个圆的遮挡区域(它通常会随着处理更多的圆而增长)，直到扫描线到达其底部。如果在任何时候遮挡区域覆盖了整个圆圈，则可以将其删除并且永远不会绘制。

遮挡区域的记录越详细，算法的效果就越好。矩形区域的联合是一种可能性(例如，参见 Android 的区域代码)。单个矩形是另一个，尽管这可能会导致许多误报。

同样，还需要一种快速的数据结构来查找扫描线中可能模糊和模糊的圆圈。包含 BIALB 的区间树可能是好的。

请注意，在实践中，如果基元数量很大，这样的算法只会产生胜利，因为快速图形硬件是如此……快速。