Google

的

S2

算法原理以及使⽤

Java

版本

--

部分参考⾃《⾼效的多维空间点索引算法》

⽂章⽬录

相关资料

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

S2jar:使⽤Maven⼯具

1.S2

算法是什么？

S2其实是来⾃⼏何数学中的⼀个数学符号 S

²

，它表⽰的是单位球。S2 这个库其实是被设计⽤来解决球⾯上各种⼏何问题的。

2.

为什么要使⽤

S2

算法？

S2 来解决多维空间点的问题的

1. 

s2有30级，geohash只有12级。s2的层级变化较平缓，⽅便选择。

2. 

s2功能强⼤，解决了向量计算，⾯积计算，多边形覆盖，距离计算等问题，减少了开发⼯作量。

3. 

s2解决了多边形覆盖问题。

这是其与geohash功能上最本质的不同。给定不规则范围，s2可以计算出⼀个多边形近似覆盖这个范围。其覆盖⽤的格⼦数量根据精确度可控。geohash在这⽅⾯⼗分不

友好，划定⼀个⼤⼀点的区域，其格⼦数可能达到数千，若减少格⼦数则丢失精度，查询区域过⼤。

如下，在min level和max level不变的情况下，只需设置可接受的max cells数值，即可控制覆盖精度。⽽且其cell的region⼤⼩⾃动适配。geohash要在如此⼤范围实现

⾼精度覆盖则会产⽣极为庞⼤的⽹格数。

另外需要注意的是,在minLevel,maxLevel,maxCells这3个参数中,不⼀定能完全满⾜.⼀般⽽⾔是优先满⾜maxLevel即最精细的⽹格⼤⼩,再尽可能控制cell数量在

maxCells⾥⾯.⽽minLevel由于会合并⽹格,所以很难满⾜(在查询⼤区域的时候可能会出现⼀个⼤⽹格和很多个⼩⽹格,导致⽊桶效应.这个时候可能将⼤⽹格划分为指定等

级的⼩⽹格,即最终效果为,严格遵循minLevel和maxLevel,为此牺牲maxCells)