谷歌轨迹坐标压缩算法及变种

简介

谷歌的坐标压缩算法通常指的是Google Maps所使用的Polyline编码（也称为Google Maps Polyline Encoder），这是一种用于压缩一系列地理坐标的算法。该算法通过对坐标进行差值编码，然后将其转换为可变长度的ASCII字符串，从而减少数据的传输量，特别是在绘制地图路径时很有用。

主要步骤

加码

• 纬度和经度转化：首先，将每个纬度和经度乘以1e5（或10的5次方）并将结果四舍五入为整数。
• 差值编码：每个点（除了第一个点）记录的是当前点与前一个点的差值，而不是绝对值，从而减少冗余数据。
• 二进制转换：将这些差值转为二进制数。
• 负数处理：负数通过左移1位再取反操作编码，以适应变量长度的编码格式。
• 分块并转换为ASCII：对每个二进制数进行5位分块，将每个分块加上63（偏移量），然后转换为可打印的ASCII字符。
• 合并为字符串：所有编码后的ASCII字符串合并为一个完整的多折线（polyline）字符串。

解码

• 将每个字符转换为二进制：对字符串中的每个字符减去63，恢复之前的5位编码。
• 处理每个编码的位移值：通过按位与操作将位移值恢复成原来的值。
• 处理负数：检查最高位来确定是否为负数，然后使用取反操作恢复负数。
• 计算差值并还原坐标：将差值与之前的坐标累加，得到完整的地理坐标（纬度和经度）。

原版

示例代码

public class PolylineEncoder {
    
    public static String encodePolyline(List<LatLng> points) {
        StringBuilder encoded = new StringBuilder();
        long lastLat = 0;
        long lastLng = 0;

        for (LatLng point : points) {
            long lat = Math.round(point.lat * 1e5);
            long lng = Math.round(point.lng * 1e5);

            encoded.append(encodeCoordinate(lat - lastLat));
            encoded.append(encodeCoordinate(lng - lastLng));

            lastLat = lat;
            lastLng = lng;
        }

        return encoded.toString();
    }

    private static String encodeCoordinate(long coordinate) {
        coordinate <<= 1;
        if (coordinate < 0) {
            coordinate = ~coordinate;
        }

        StringBuilder encoded = new StringBuilder();
        while (coordinate >= 0x20) {
            encoded.append((char) ((0x20 | (coordinate & 0x1f)) + 63));
            coordinate >>= 5;
        }
        encoded.append((char) (coordinate + 63));

        return encoded.toString();
    }
    
    public static List<LatLng> decodePolyline(String encoded) {
        List<LatLng> polyline = new ArrayList<>();
        int index = 0, len = encoded.length();
        int lat = 0, lng = 0;

        while (index < len) {
            lat += decodeNextValue(encoded, index);
            index = advanceIndex(encoded, index);

            lng += decodeNextValue(encoded, index);
            index = advanceIndex(encoded, index);

            polyline.add(new LatLng(lat / 1e5, lng / 1e5));
        }

        return polyline;
    }

    private static int decodeNextValue(String encoded, int index) {
        int result = 0;
        int shift = 0;
        int b;
        do {
            b = encoded.charAt(index++) - 63;
            result |= (b & 0x1f) << shift;
            shift += 5;
        } while (b >= 0x20);
        return (result & 1) != 0 ? ~(result >> 1) : (result >> 1);
    }

    private static int advanceIndex(String encoded, int index) {
        while (encoded.charAt(index++) - 63 >= 0x20);
        return index;
    }
    
    public static class LatLng {
        public double lat;
        public double lng;

        public LatLng(double lat, double lng) {
            this.lat = lat;
            this.lng = lng;
        }
    }
}

使用示例

// 加码
List<PolylineEncoder.LatLng> points = new ArrayList<>();
points.add(new PolylineEncoder.LatLng(38.5, -120.2));
points.add(new PolylineEncoder.LatLng(40.7, -120.95));
points.add(new PolylineEncoder.LatLng(43.252, -126.453));

String encodedPolyline = PolylineEncoder.encodePolyline(points);
System.out.println(encodedPolyline);

// 解码
String encodedPolyline = "gfo}EtohhUxD@bAxJmGF";
List<LatLng> decodedPoints = decodePolyline(encodedPolyline);

for (LatLng point : decodedPoints) {
    System.out.println(point);
}

变种:在经纬度基础上添加时间

原理

在基础的Google Polyline编码中，已经处理了纬度和经度。要在此基础上添加时间戳，可以将时间戳视为与经纬度类似的数据点，并用同样的编码方式处理。需要注意的是，秒级时间戳的数据范围较大，因此编码时也需要考虑长度限制问题。我们可以将时间戳的增量（类似于经纬度的增量）同样使用差值方式进行编码，从而进一步压缩数据。

示例代码

// 类1
public class PolylineEncoder {

    private static final double DEFAULT_PRECISION = 1e5;

    public static String encode(List<CoordinateWithTimestampBo> coordinates, long prevTimestamp) {
        StringBuilder encoded = new StringBuilder();

        long prevLat = 0;
        long prevLng = 0;

        for (CoordinateWithTimestampBo c : coordinates) {
            long lat = Math.round(c.getLatitude() * DEFAULT_PRECISION);
            long lng = Math.round(c.getLongitude() * DEFAULT_PRECISION);
            long timestamp = c.getTimestamp();

            encodePoint(lat - prevLat, encoded);
            encodePoint(lng - prevLng, encoded);
            encodePoint(timestamp - prevTimestamp, encoded);

            prevLat = lat;
            prevLng = lng;
            prevTimestamp = timestamp;
        }

        return encoded.toString();
    }

    private static void encodePoint(long v, StringBuilder result) {
        v = v < 0 ? ~(v << 1) : v << 1;
        while (v >= 0x20) {
            result.append(Character.toChars((int) ((0x20 | (v & 0x1f)) + 63)));
            v >>= 5;
        }
        result.append(Character.toChars((int) (v + 63)));
    }

    public static List<CoordinateWithTimestampBo> decodeFlatPoints(final String encodePath, long prevTimestamp) {
        int len = encodePath.length();
        final List<CoordinateWithTimestampBo> path = new ArrayList<>();
        int index = 0;
        int lat = 0;
        int lng = 0;
        int currentTimestamp = 0;
        while (index < len) {
            int result = 1;
            int shift = 0;
            int b;
            do {
                b = encodePath.charAt(index++) - 63 - 1;
                result += b << shift;
                shift += 5;
            } while (b >= 0x1f);
            lat += (result & 1) != 0 ? ~(result >> 1) : (result >> 1);

            result = 1;
            shift = 0;
            do {
                b = encodePath.charAt(index++) - 63 - 1;
                result += b << shift;
                shift += 5;

            } while (b >= 0x1f);

            lng += (result & 1) != 0 ? ~(result >> 1) : (result >> 1);

            result = 1;
            shift = 0;
            do {
                b = encodePath.charAt(index++) - 63 - 1;
                result += b << shift;
                shift += 5;

            } while (b >= 0x1f);

            currentTimestamp += (result & 1) != 0 ? ~(result >> 1) : (result >> 1);
            path.add(new CoordinateWithTimestampBo(lat * 1e-5, lng * 1e-5, currentTimestamp + prevTimestamp));
        }
        return path;
    }
}

// 类2
@Data
@AllArgsConstructor
public class CoordinateWithTimestampBo {
    private double latitude;
    private double longitude;
    private long timestamp;
}

上述代码通过传入 prevTimestamp（开始的秒级时间戳）来编码和解码包含时间戳的地理坐标。这样处理能够将时间点与坐标位置一起压缩，从而适合用于记录轨迹或带有时间信息的路径。