六角形階層的地理空間索引システムH3に関するメモ

概要

Uberの六角形階層的地理空間索引システム「H3」が気になりました。
H3については「H3: Uber’s Hexagonal Hierarchical Spatial Index」に詳細が説明されています。 eng.uber.com

何に使うか、使えるかを考えるのはこれからですが、とりあえず、行政区域のGeoJsonから六角形グリッドを生成するプログラムを試作してみたので、メモしておきます。

Mavenプロジェクトの準備

今回はH3-Javaを使ってプログラムを作成しています。 github.com pom.xmlのdependenciesに以下を加えてMavenプロジェクトを作成しました。

<dependency>
    <groupId>com.uber</groupId>
    <artifactId>h3</artifactId>
    <version>3.4.1</version>
</dependency>

ソースコード

　とりあえず、H3の使い方を理解するため、以下のようなユーティリティクラスを作りました。

import java.awt.geom.AffineTransform;
import java.awt.geom.GeneralPath;
import java.awt.geom.PathIterator;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.google.gson.Gson;
import com.uber.h3core.AreaUnit;
import com.uber.h3core.H3Core;
import com.uber.h3core.util.GeoCoord;

public class H3Util {
    private static final H3Core H3=getH3Core();
    private static final AffineTransform af=AffineTransform.getScaleInstance(1.0, 1.0);

    public static long getHexIdAtLonlat(int zoom,double lon,double lat){
        return H3.geoToH3(lat, lon, zoom);
    }

    public static List<Long> getHexAtPoligon(List<GeoCoord> list,int zoom){
        List<Long> ret=H3.polyfill(list, new ArrayList<List<GeoCoord>>(),zoom);
        return ret;
    }

    public static List<Long> getHexAtPoligon(List<GeoCoord> polygon,List<List<GeoCoord>> hole,int zoom){
        List<Long> ret=H3.polyfill(polygon,hole,zoom);
        return ret;
    }

    public static List<GeoCoord> rectToGeoCoords(double lon_1,double lat_1,double lon_2,double lat_2){
        List<GeoCoord> ret=new ArrayList<GeoCoord>();
        ret.add(new GeoCoord(lat_1,lon_1));
        ret.add(new GeoCoord(lat_1,lon_2));
        ret.add(new GeoCoord(lat_2,lon_2));
        ret.add(new GeoCoord(lat_1,lon_1));
        ret.add(new GeoCoord(lat_1,lon_1));
        return ret;
    }

    public static List<GeoCoord> polyToGeoCoords(GeneralPath gp){
        List<GeoCoord> ret=new ArrayList<GeoCoord>();
        PathIterator pi=gp.getPathIterator(af);
        double[] c = new double[6];
        while(!pi.isDone()){
            switch (pi.currentSegment(c)) {
                case PathIterator.SEG_MOVETO:
                case PathIterator.SEG_LINETO:
                    ret.add(new GeoCoord(c[0],c[1]));
                    break;
             default:
            }
            pi.next();
        }
        return ret;
    }

    public static List<Long> getChaildrenHex(long hexId,int zoom){
        return H3.h3ToChildren(hexId, zoom);
    }

    public static long getParentHex(long hexId,int zoom){
        return H3.h3ToParent(hexId, zoom);
    }

    public static List<Long> getSurroundHexId(long hexId,int distance){
        return H3.kRing(hexId, distance);
    }

    public static GeneralPath getHexAtId(long hexId){
        List<GeoCoord> gl = H3.h3ToGeoBoundary(hexId);
        GeneralPath ret=null;
        for(GeoCoord g : gl){
            if(ret!=null){
                ret.lineTo(g.lng, g.lat);
            }else{
                ret=new GeneralPath();
                ret.moveTo(g.lng, g.lat);
            }
        }
        ret.closePath();
        return ret;
    }

    public static float[][] getCoordinates(long hexId){
        List<GeoCoord> gc = H3.h3ToGeoBoundary(hexId);
        float[][] coord=new float[gc.size()+1][];
        for(int i=0;i<gc.size();i++){
            GeoCoord g=gc.get(i);
            coord[i]=new float[]{(float)g.lng,(float)g.lat};
        }
        coord[coord.length-1]=new float[]{coord[0][0],coord[0][1]};
        return coord;
    }

    public static List<Long> compact(List<Long> ll){
        return H3.compact(ll);
    }

    private static float[][] getCoordinates(GeneralPath gp){
        List<float[]> list=new ArrayList<float[]>();
        PathIterator pi=gp.getPathIterator(af);
        float[] c = new float[6];
        while(!pi.isDone()){
            switch (pi.currentSegment(c)) {
                case PathIterator.SEG_MOVETO:
                case PathIterator.SEG_LINETO:
                    list.add(new float[]{c[0],c[1]});
                    break;
             default:
            }
            pi.next();
        }
        return list.toArray(new float[list.size()][]);
    }

    public static Map<String,Object> createpoligonFeature(GeneralPath gp,Map<String,Object> prop){
        Map<String,Object> ret=new HashMap<String,Object>();
        ret.put("type", "Feature");
        Map<String,Object> geo=new HashMap<String,Object>();
        ret.put("geometry", geo);
        geo.put("type", "Polygon");
        geo.put("coordinates", new float[][][]{getCoordinates(gp)});
        if(prop!=null){
            ret.put("properties", prop);
        }else{
            ret.put("properties", new HashMap<String,Object>());
        }
        return ret;
    }

    public static double getArea(int zoom){
        return H3.hexArea(zoom, AreaUnit.m2);
    }

    private static H3Core getH3Core(){
        try{
            return H3Core.newInstance();
        }catch(IOException e){
            return null;
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static List<List<List<GeoCoord>>> parseGeoJson(String json){
        Gson gson=new Gson();
        Map obj=gson.fromJson(json, Map.class);
        List list=(List)obj.get("features");
        List<List<List<GeoCoord>>> coords=new ArrayList<List<List<GeoCoord>>>();
        for(Object mm : list){
            Map<String,Object> ff=(Map<String,Object>)mm;
            Map<String,Object> geo=(Map<String,Object>)ff.get("geometry");
            String type=((String)geo.get("type")).toLowerCase();
            if(!type.equals("polygon"))continue;
            List co=(List)geo.get("coordinates");
            List<List<GeoCoord>> tp=new ArrayList<List<GeoCoord>>();
            for(int i=0;i<co.size();i++){
                List p=(List)co.get(i);
                List<GeoCoord> fea=new ArrayList<GeoCoord>();
                for(int j=0;j<p.size();j++){
                    List px=(List)p.get(j);
                    GeoCoord g=new GeoCoord((double)px.get(1),(double)px.get(0));
                    fea.add(g);
                }
                tp.add(fea);

            }
            coords.add(tp);
        }
        return coords;
    }
}

ついで、GeoJsonのポリゴン領域に対応した六角形グリッドを生成するプログラムを作成しました。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.google.gson.Gson;
import com.google.gson.GsonBuilder;
import com.uber.h3core.util.GeoCoord;

public class HexGrid {
    private int zoom;
    private List<Long> hexs;
    private double area;

    private HexGrid(){}

    public HexGrid(List<GeoCoord> gc,int zoom){
        this.zoom=(zoom<15) ? zoom : 15;
        hexs=H3Util.getHexAtPoligon(gc, zoom);
        area=H3Util.getArea(zoom);
    }

    public HexGrid(List<GeoCoord> poly,List<List<GeoCoord>> hole ,int zoom){
        this.zoom=(zoom<15) ? zoom : 15;
        hexs=H3Util.getHexAtPoligon(poly,hole, zoom);
        area=H3Util.getArea(zoom);
    }

    public static HexGrid createHexsForGeoJson(File geoJson,int zoom)throws IOException{
        BufferedReader br=null;
        StringBuffer buf=new StringBuffer();
        try{
            br=new BufferedReader(new FileReader(geoJson));
            String line=null;
            while((line=br.readLine())!=null){
                buf.append(line);
            }
        }catch(IOException e){
            throw e;
        }finally{
            br.close();
        }
        List<List<List<GeoCoord>>> list=H3Util.parseGeoJson(buf.toString());
        HexGrid ret=new HexGrid();
        ret.zoom=(zoom<15) ? zoom : 15;
        ret.hexs=new ArrayList<Long>();
        for(List<List<GeoCoord>> ll : list){
            List<GeoCoord> p=ll.remove(0);
            List<Long> tmp=H3Util.getHexAtPoligon(p,ll, zoom);
            ret.hexs.addAll(tmp);
        }
        ret.area=H3Util.getArea(zoom);
        return ret;
    }

    public void children(){
        zoom=zoom+1;
        area=H3Util.getArea(zoom);
        List<Long> tmp=new ArrayList<Long>();
        for(Long ll : hexs){
            List<Long> t=H3Util.getChaildrenHex(ll, zoom);
            tmp.addAll(t);
        }
        hexs=tmp;
    }

    public void parent(){
        zoom=zoom-1;
        area=H3Util.getArea(zoom);
        List<Long> tmp=new ArrayList<Long>();
        Set<Long> ss=new HashSet<Long>();
        for(Long ll : hexs){
            long t=H3Util.getParentHex(ll, zoom);
            ss.add(t);
        }
        tmp.addAll(ss);
        hexs=tmp;
    }

    public void compact(){
        this.hexs=H3Util.compact(this.hexs);
    }

    public Map<String,Object> getPolyJson(){
        List<Map<String,Object>> list=getFeatuers();
        Map<String,Object> root=new HashMap<String,Object>();
        root.put("type","FeatureCollection");
        root.put("features", list);
        return root;
    }

    public List<Map<String,Object>> getFeatuers(){
        List<Map<String,Object>> ret=new ArrayList<Map<String,Object>>();
        for(Long id : hexs){
            ret.add(getFeature(id));
        }
        return ret;
    }

    private Map<String,Object> getFeature(Long id){
        Map<String,Object> ret=new HashMap<String,Object>();
        ret.put("type", "Feature");
        Map<String,Object> geo=new HashMap<String,Object>();
        ret.put("geometry", geo);
        geo.put("type", "Polygon");
        geo.put("coordinates", new float[][][]{H3Util.getCoordinates(id)});
        HashMap<String,Object> mm=new HashMap<String,Object>();
        mm.put("id", id);
        mm.put("zoom", zoom);
        mm.put("area", area);
        mm.put("parent", H3Util.getParentHex(id, zoom-1));
        mm.put("neighbors", H3Util.getSurroundHexId(id, 1));
        if(zoom<15){
            mm.put("children", H3Util.getChaildrenHex(id, zoom+1));
        }
        ret.put("properties",mm);
        return ret;
    }

    public static void main(String[] args){
        File input=new File("C:/toyohashi.geojson");
        HexGrid hh=null;
        try{
            hh=HexGrid.createHexsForGeoJson(input, 9);
        }catch(IOException e){
            e.printStackTrace();
        }
        if(hh==null)return;
        Gson gson=new GsonBuilder().setPrettyPrinting().create();
        File out=new File("C:/toyohashi_09.geojson");
        try{
            BufferedWriter bw=new BufferedWriter(new FileWriter(out));
            bw.write(gson.toJson(hh.getFeatuers()));
            bw.flush();
            bw.close();
        }catch(IOException e){
            e.printStackTrace();
        }
    }
}

処理結果

総務省国勢調査の豊橋市のShapeファイルからGeoJsonを生成し、H3グリッドを生成してみました。
■豊橋市の行政区域（GeoJson） ■H3グリッド（解像度7） ■H3グリッド（解像度8） ■H3グリッド（解像度10） ■H3グリッド（Compact処理を行ったもの）

感想

高解像度グリッドはグリッド数が非常に多くなるため、処理時間がかかり、データ数も大きくなります。
Leaflet等で使うとなると、サーバーサイドで動的にGeoJsonを生成するのはキツそうなので、あらかじめH3グリッドのGeoJsonを生成しておき、ElasticSearchにマッピングして使用するかたちを考えています。