Games202 Lecture3-4之SAT: Summed Area Table
SAT: Summed Area Table
- 一维
- 二维
- 分析
一种可以准确进行范围查询的方式。
数据结构： Summed Area Table (SAT)
算法：prefix sum 前缀和
一维
对于一个存放texture的一维数组，构建一个等大的summed area table，这个table中每个元素的值是texture数组中该位置元素以及其左侧所有元素的总和。
SAT(i)=∑j≤iTexture(j)SAT(i) = \sum_{\mathclap{j\le i}} Texture(j) SAT(i)=j≤i∑Texture(j)
示意：
在(a,b]范围内元素和的计算方式：
RQ((a,b])=SAT(b)−SAT(a)RQ((a,b]) = SAT(b) - SAT(a) RQ((a,b])=SAT(b)−SAT(a)
二维
对于一个存放texture的二维数组，构建一个等大的summed area table。
每个元素的值记录的是texture数组中该元素以及其左侧和上方的所有元素的总和。
SAT(x,y)=∑x′≤x,y′≤yTexture(x′,y′)SAT(x,y)=\sum_{x'\le x, y'\le y} Texture(x',y') SAT(x,y)=x′≤x,y′≤y∑Texture(x′,y′)
示意：
图中蓝色部分元素和的计算方式：
RQ(D)=SAT(D)−SAT(C)−SAT(B)+SAT(A)RQ(D) = SAT(D) - SAT(C) - SAT(B) + SAT(A) RQ(D)=SAT(D)−SAT(C)−SAT(B)+SAT(A)
其中，
SAT(A)=SAT(Ax′,Ay′)SAT(A) = SAT(A_{x'},A_{y'}) SAT(A)=SAT(Ax′,Ay′)
分析
时间复杂度O(M*N)
空间复杂度O(M*N)
数据精度会稍有损失，但是影响不大。
二维SAT进行计算时，行与行之间是独立的，可以并行计算。
总结
以上是生活随笔为你收集整理的Games202 Lecture3-4之SAT: Summed Area Table的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 10月重磅程序员新书上架7本，每一本都很
- 下一篇： 大数据之flink数据一致性