GeoSpark源码解析（四）
上节我们讲了GeoSpark如何根据已经分好的格网（Grid）来进行分块（partition）操作。对于GeoSpark来说，格网的生成算法实际上是决定了并行计算的关键，在上一节中，我们讲到了SpatialRDD的spatialPartitioning方法，他需要一个SpatialPartitioner类型的参数，这个参数有三种类型：
image.png
这三种SpatialPartitioner其实是在public void spatialPartitioning(GridType gridType, int numPartitions)这个函数中构造的。我们先看下GridType：
public enum GridType{
/**
* The equalgrid.
*/
EQUALGRID,
/**
* The hilbert.
*/
HILBERT,
/**
* The rtree.
*/
RTREE,
/**
* The voronoi.
*/
VORONOI,
/**
* The voronoi.
*/
QUADTREE,
/**
* K-D-B-tree (k-dimensional B-tree)
*/
KDBTREE;
}
代码中共有6种，我们分别介绍下：
-
EQUALGRID，这个我们从名字上就可以看出他是等分，就是等分为多少行多少列。
public EqualPartitioning(Envelope boundary, int partitions)
{
//Local variable should be declared here
Double root = Math.sqrt(partitions);
int partitionsAxis;
double intervalX;
double intervalY;
//Calculate how many bounds should be on each axis
partitionsAxis = root.intValue();
intervalX = (boundary.getMaxX() - boundary.getMinX()) / partitionsAxis;
intervalY = (boundary.getMaxY() - boundary.getMinY()) / partitionsAxis;
//System.out.println("Boundary: "+boundary+"root: "+root+" interval: "+intervalX+","+intervalY);
for (int i = 0; i < partitionsAxis; i++) {
for (int j = 0; j < partitionsAxis; j++) {
Envelope grid = new Envelope(boundary.getMinX() + intervalX * i, boundary.getMinX() + intervalX * (i + 1), boundary.getMinY() + intervalY * j, boundary.getMinY() + intervalY * (j + 1));
//System.out.println("Grid: "+grid);
grids.add(grid);
}
//System.out.println("Finish one column/one certain x");
}
}
代码的第11、12行首先根据要分块的长宽计算X、Y间隔，然后第14、15行for循环遍历生成网格。
-
HILBERT:Hilbert其实是最近很流行的一种新型NoSQL空间索引，就是利用这个算法生成key-Value格式的空间索引，存储在HBase、Accumulo等分布式非关系型数据库中，目前LocationTech下的GeoWave、GeoMesa就是采用了这个思路。 -
RTREE，下面这张图很好的展示R树的工作原理，其实就是对整个空间建立索引关系，加快搜索效率。然后GeoSpark是将RTree的最后一级叶子节点作为网格建立。
image.png
-
VORONOI，这个不了解。 -
QUADTREE，GIS中很经典的一种索引算法，就是数据结构中的四叉树，其原理就是将一个空间每次四等分下去，分到某个级别后停止。 -
KDBTREE，这个我也不是特别理解，感觉和RTREE大致上差不多的，可能具体针对特别的空间分布下的空间数据有相应的优势吧。
image.png
当Grid构建好之后，就可以构造SpatialPartitioner，然后进行分块操作。
public void spatialPartitioning(GridType gridType, int numPartitions)
throws Exception{
// 省略部分代码
switch (gridType) {
case EQUALGRID: {
EqualPartitioning EqualPartitioning = new EqualPartitioning(paddedBoundary, numPartitions);
grids = EqualPartitioning.getGrids();
partitioner = new FlatGridPartitioner(grids);
break;
}
case HILBERT: {
HilbertPartitioning hilbertPartitioning = new HilbertPartitioning(samples, paddedBoundary, numPartitions);
grids = hilbertPartitioning.getGrids();
partitioner = new FlatGridPartitioner(grids);
break;
}
case RTREE: {
RtreePartitioning rtreePartitioning = new RtreePartitioning(samples, numPartitions);
grids = rtreePartitioning.getGrids();
partitioner = new FlatGridPartitioner(grids);
break;
}
case VORONOI: {
VoronoiPartitioning voronoiPartitioning = new VoronoiPartitioning(samples, numPartitions);
grids = voronoiPartitioning.getGrids();
partitioner = new FlatGridPartitioner(grids);
break;
}
case QUADTREE: {
QuadtreePartitioning quadtreePartitioning = new QuadtreePartitioning(samples, paddedBoundary, numPartitions);
partitionTree = quadtreePartitioning.getPartitionTree();
partitioner = new QuadTreePartitioner(partitionTree);
break;
}
case KDBTREE: {
final KDBTree tree = new KDBTree(samples.size() / numPartitions, numPartitions, paddedBoundary);
for (final Envelope sample : samples) {
tree.insert(sample);
tree.assignLeafIds();
partitioner = new KDBTreePartitioner(tree);
break;
}
}
this.spatialPartitionedRDD = partition(partitioner);
}
到这里，基本上GeoSpark基本代码就介绍完了，也算是对前期自己工作的一个总结，后续根据时间、项目再来进行探讨。
