geohash zmerge 算法

原创
2019/05/06 20:39
阅读数 210

geohash zmerge 算法


import ch.hsr.geohash.BoundingBox;
import ch.hsr.geohash.GeoHash;
import ch.hsr.geohash.WGS84Point;
import ch.hsr.geohash.queries.GeoHashQuery;

import java.util.*;

public class GeoHashBoundingBoxQuery2 implements GeoHashQuery {

    private final BoundingBox box;
    private final int precision;
    private final GeoHash topCommonGeoHash;
    private List<GeoHash> searchGeoHashes = new ArrayList<>();
    public GeoHashBoundingBoxQuery2(BoundingBox box, int precision) {
        this.box = box;
        this.precision = precision;

        WGS84Point upperLeft = box.getUpperLeft();
        WGS84Point lowerRight = box.getLowerRight();

        GeoHash upperLeftGeoHash = GeoHash.withBitPrecision(upperLeft.getLatitude(), upperLeft.getLongitude(), this.precision);
        GeoHash lowerRightGeoHash = GeoHash.withBitPrecision(lowerRight.getLatitude(), lowerRight.getLongitude(), this.precision);

        GeoHash commonGeoHash = getCommonGeoHash(upperLeftGeoHash, lowerRightGeoHash);
        this.topCommonGeoHash = commonGeoHash;
        coverBoxGeoHashes(this.topCommonGeoHash);
        searchGeoHashes = zMerge(this.searchGeoHashes);
    }

    private void coverBoxGeoHashes(GeoHash geoHashToSearch) {

        if (geoHashToSearch.significantBits() >= this.precision) {
            this.searchGeoHashes.add(geoHashToSearch);
            return;
        }

        // Get 4 children geoHash
        GeoHash[] children = GeoHashTools.children(geoHashToSearch);
        for (GeoHash child : children) {
            BoundingBox childBox = child.getBoundingBox();

            if (!GeoHashTools.intersects(this.box, childBox)) {
                // Is not intersects
                continue;
            }

            // Intersect

            boolean isULContain = this.box.contains(childBox.getUpperLeft());
            boolean isLRContain = this.box.contains(childBox.getLowerRight());

            if (isULContain && isLRContain) {
                // box cover childBox
                this.searchGeoHashes.add(child);
                continue;
            }
            coverBoxGeoHashes(child);
        }
    }

    public static List<GeoHash> zMerge(List<GeoHash> geoHashes) {

        Map<Integer, Set<GeoHash>> map = new HashMap<>();
        for (GeoHash geoHash : geoHashes) {
            int sigBits = geoHash.significantBits();
            Set<GeoHash> sameLenSet = map.get(sigBits);
            if (sameLenSet == null) {
                Set<GeoHash> _set = new TreeSet<>();
                _set.add(geoHash);
                map.put(sigBits, _set);
            } else {
                sameLenSet.add(geoHash);
            }
        }

        List<GeoHash> resGeoHashes = new ArrayList<>();
        for (Map.Entry<Integer, Set<GeoHash>> integerSetEntry : map.entrySet()) {
            Set<GeoHash> set = integerSetEntry.getValue();
            resGeoHashes.addAll(merge(set, integerSetEntry.getKey()));
        }

        if (geoHashes.size() == resGeoHashes.size()) {
            return geoHashes;
        }

        return zMerge(resGeoHashes);
    }

    public static List<GeoHash> merge(Set<GeoHash> sameSigBitsLenSet, int sigBits) {

        List<GeoHash> result = new ArrayList<>();

        long lastPrefix = 0L;
        boolean isFirst = true;

        List<GeoHash> geoHashesBuf = new ArrayList<>(4);
        for (GeoHash geoHash : sameSigBitsLenSet) {
            if (isFirst) {
                isFirst = false;
                lastPrefix = geoHash.ord() >>> 2;
                geoHashesBuf.add(geoHash);
                continue;
            }

            long curPrefix = geoHash.ord() >>> 2;
            if (curPrefix == lastPrefix) {
                geoHashesBuf.add(geoHash);
            } else {
                if (geoHashesBuf.size() == 4) {
                    result.add(GeoHash.fromOrd(lastPrefix, sigBits - 2));
                } else {
                    result.addAll(geoHashesBuf);
                }
                geoHashesBuf.clear();

                lastPrefix = curPrefix;
                geoHashesBuf.add(geoHash);
            }
        }

        if (geoHashesBuf.size() == 4) {
            result.add(GeoHash.fromOrd(lastPrefix, sigBits - 2));
        } else {
            result.addAll(geoHashesBuf);
        }

        return result;
    }

    /**
     * Merge 4 geoHashes to one parent
     * @param _4geoHashes   4 GeoHashes, must have same significantBits
     * @return
     */
    public static GeoHash merge(GeoHash[] _4geoHashes) {
        if (_4geoHashes.length < 4) {
            return null;
        }

        if (_4geoHashes[0].significantBits() <= 0) {
            return null;
        }

        long lastOrd = 0L;
        long lastTail2BitsSum = 0L;
        for (int i = 0; i < _4geoHashes.length; i++) {
            if (i == 0) {
                lastOrd = _4geoHashes[i].ord();
                lastTail2BitsSum += _4geoHashes[i].ord() & 0x03L;
                continue;
            }

            long curOrd = _4geoHashes[i].ord();
            if ( !(((lastOrd ^ curOrd) & 0xfffffffffffffffcL) == 0x0L) ) {
                // prefix not eq
                return null;
            }

            lastTail2BitsSum += curOrd & 0x03L;
            lastOrd = curOrd;
        }

        if (lastTail2BitsSum != 6) {
            return null;
        }

        return GeoHash.fromOrd(lastOrd >>> 2, _4geoHashes[0].significantBits() - 2);
    }

    public static String getCommonPrefix(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return null;
        }

        StringBuilder result = new StringBuilder();

        char[] s1Chars = s1.toCharArray();
        char[] s2Chars = s2.toCharArray();

        int len = Math.min(s1Chars.length, s2Chars.length);
        for (int i = 0; i < len; i++) {
            if (s1Chars[i] == s2Chars[i]) {
                result.append(s1Chars[i]);
            } else {
                break;
            }
        }

        return result.toString();
    }

    public static GeoHash getCommonGeoHash(GeoHash geoHash1, GeoHash geoHash2) {
        long resValue = 0;
        int resSignificantBits = 0;

        int len = Math.min(geoHash1.significantBits(), geoHash2.significantBits());

        if (len % 2 != 0) {
            len -= 1;
        }

        len = len / 2;

        long geoHashVal1 = geoHash1.longValue();
        long geoHashVal2 = geoHash2.longValue();

        for (int i = 0; i < len; i++) {
            long v1 = (geoHashVal1 >>> (64 - (i + 1) * 2)) & 0x03L;
            long v2 = (geoHashVal2 >>> (64 - (i + 1) * 2)) & 0x03L;

            if (v1 == v2) {
                resValue |= (v1 << (64 - resSignificantBits - 2));
                resSignificantBits += 2;
            } else {
                break;
            }
        }

        return GeoHash.fromLongValue(resValue, resSignificantBits);
    }

    @Override
    public boolean contains(GeoHash hash) {
        return this.searchGeoHashes.contains(hash);
    }

    @Override
    public boolean contains(WGS84Point point) {
        return this.box.contains(point);
    }

    @Override
    public List<GeoHash> getSearchHashes() {
        return this.searchGeoHashes;
    }

    @Override
    public String getWktBox() {
        return "BOX(" + this.box.getMinLon() + " " + this.box.getMinLat() + "," + this.box.getMaxLon() + " "
                + this.box.getMaxLat() + ")";
    }

    public BoundingBox getBox() {
        return box;
    }

    public int getPrecision() {
        return precision;
    }

    public GeoHash getTopCommonGeoHash() {
        return topCommonGeoHash;
    }

    public static void main(String[] args) {
        System.out.println(GeoHash.fromBinaryString("1011").compareTo(GeoHash.fromBinaryString("1010")));
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部