algorithm - 分层图像的快速子矩形

Question

我有这个 2d 栅格，其上有 1 到 20 个其他 2d 栅格(具有随机大小和偏移)。我正在寻找访问子矩形 View (具有随机大小和偏移量)的快速方法。 View 应返回每个 X 和 Y 坐标的所有分层像素。

我想这就是 GIMP 或其他 2d 绘图应用程序相互绘制图层的方式，除了我想让所有像素相互叠加，而不仅仅是顶部像素隐藏另一个的投影在它下面。

我以前和现在都遇到过这个问题，已经花了很多时间在互联网上搜索类似的问题，但找不到任何问题。我将描述两种可能的解决方案，但我对这两种解决方案都不满意:

1. 有一个预先分配大小的基本 3d 数组。这很容易管理，但存储空间浪费和内存开销确实很大。对于 4k 光栅，比如 16 个插槽，每个插槽 4 个字节，就像 1 GiB 的内存？而在应用案例中，大部分空间将被浪费，而不是被使用。

2. 我之前做的解决方案。有两个二维数组，一个带有索引，另一个带有实际值。第一个的每个“像素”表示在第二个数组中的哪个像素范围内，您可以找到所有层贡献的实际像素。这在大小上压缩得很好，但任何请求都在两个内存区域之间跳动，设置起来有点麻烦，更不用说更新了(一个很好的功能，但不是强制性的)。

那么……对此类问题有什么诀窍吗？提前致谢!

忘记补充一点，我的目标是自给自足，最好是单线程 CPU 解决方案。这些层很可能是带 alpha 的灰度(也就是说，某些像素数据将不存在)。查找操作优先，添加/删除图层等更新可能会更慢。

由马克添加(见评论): 在该图像中，如果取红色矩形的左上角，查找应该报告红色、绿色、蓝色和黑色。如果取右下角，则只报告红色和黑色。

Answer 1

1. 我会将偏移量和大小存储在与像素数据分开的数据结构中。这样你就不会在计算每一层的相对坐标时在内存中跳来跳去(或者即使你可以忽略一些层)。

2. 如果您想访问单个像素或小区域而不是迭代大区域 Quad-Tree在访问彼此靠近(在 x 或 y 方向)的像素或区域时，使用更多本地内存访问来存储数据可能是个好主意。