2021-09-10 00:46:20 +00:00
|
|
|
/* ****************************************************************
|
2021-04-25 11:42:13 +00:00
|
|
|
* Licensed to the Apache Software Foundation (ASF) under one
|
|
|
|
* or more contributor license agreements. See the NOTICE file
|
|
|
|
* distributed with this work for additional information
|
|
|
|
* regarding copyright ownership. The ASF licenses this file
|
|
|
|
* to you under the Apache License, Version 2.0 (the
|
|
|
|
* "License"); you may not use this file except in compliance
|
|
|
|
* with the License. You may obtain a copy of the License at
|
|
|
|
*
|
|
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
*
|
|
|
|
* Unless required by applicable law or agreed to in writing,
|
|
|
|
* software distributed under the License is distributed on an
|
|
|
|
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
|
|
|
|
* KIND, either express or implied. See the License for the
|
|
|
|
* specific language governing permissions and limitations
|
|
|
|
* under the License.
|
|
|
|
****************************************************************/
|
2021-12-23 10:42:24 +00:00
|
|
|
package com.onthegomap.planetiler;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
|
|
|
import com.carrotsearch.hppc.IntArrayList;
|
|
|
|
import com.google.common.primitives.Ints;
|
2021-04-29 10:22:41 +00:00
|
|
|
import com.google.protobuf.InvalidProtocolBufferException;
|
2021-12-23 10:42:24 +00:00
|
|
|
import com.onthegomap.planetiler.collection.FeatureGroup;
|
|
|
|
import com.onthegomap.planetiler.geo.GeoUtils;
|
|
|
|
import com.onthegomap.planetiler.geo.GeometryException;
|
|
|
|
import com.onthegomap.planetiler.geo.GeometryType;
|
|
|
|
import com.onthegomap.planetiler.geo.MutableCoordinateSequence;
|
2023-09-27 00:56:04 +00:00
|
|
|
import com.onthegomap.planetiler.util.Hilbert;
|
2023-12-15 00:26:27 +00:00
|
|
|
import com.onthegomap.planetiler.util.LayerAttrStats;
|
2021-04-25 11:42:13 +00:00
|
|
|
import java.util.ArrayList;
|
2021-04-30 10:31:56 +00:00
|
|
|
import java.util.Arrays;
|
2021-04-25 11:42:13 +00:00
|
|
|
import java.util.HashMap;
|
|
|
|
import java.util.LinkedHashMap;
|
|
|
|
import java.util.List;
|
2023-09-24 12:10:47 +00:00
|
|
|
import java.util.Locale;
|
2021-04-25 11:42:13 +00:00
|
|
|
import java.util.Map;
|
2024-01-11 13:42:16 +00:00
|
|
|
import java.util.TreeMap;
|
2023-09-24 12:10:47 +00:00
|
|
|
import java.util.function.Consumer;
|
2021-05-31 11:16:44 +00:00
|
|
|
import java.util.stream.Collectors;
|
|
|
|
import java.util.stream.Stream;
|
2021-09-10 00:46:20 +00:00
|
|
|
import javax.annotation.concurrent.NotThreadSafe;
|
2021-04-25 11:42:13 +00:00
|
|
|
import org.locationtech.jts.algorithm.Orientation;
|
2023-09-27 00:56:04 +00:00
|
|
|
import org.locationtech.jts.geom.Coordinate;
|
2021-04-25 11:42:13 +00:00
|
|
|
import org.locationtech.jts.geom.CoordinateSequence;
|
|
|
|
import org.locationtech.jts.geom.Geometry;
|
|
|
|
import org.locationtech.jts.geom.GeometryFactory;
|
|
|
|
import org.locationtech.jts.geom.LineString;
|
|
|
|
import org.locationtech.jts.geom.LinearRing;
|
|
|
|
import org.locationtech.jts.geom.MultiLineString;
|
|
|
|
import org.locationtech.jts.geom.MultiPoint;
|
|
|
|
import org.locationtech.jts.geom.MultiPolygon;
|
|
|
|
import org.locationtech.jts.geom.Point;
|
|
|
|
import org.locationtech.jts.geom.Polygon;
|
2021-04-25 19:52:24 +00:00
|
|
|
import org.locationtech.jts.geom.Puntal;
|
2021-04-25 11:42:13 +00:00
|
|
|
import org.locationtech.jts.geom.impl.CoordinateArraySequence;
|
|
|
|
import org.locationtech.jts.geom.impl.PackedCoordinateSequence;
|
2021-04-25 19:52:24 +00:00
|
|
|
import org.slf4j.Logger;
|
|
|
|
import org.slf4j.LoggerFactory;
|
2021-09-10 00:46:20 +00:00
|
|
|
import vector_tile.VectorTileProto;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
|
|
|
/**
|
2021-09-10 00:46:20 +00:00
|
|
|
* Encodes a single output tile containing JTS {@link Geometry} features into the compact binary Mapbox Vector Tile
|
|
|
|
* format.
|
2021-04-25 11:42:13 +00:00
|
|
|
* <p>
|
2022-03-09 02:08:03 +00:00
|
|
|
* This class is copied from <a href=
|
|
|
|
* "https://github.com/ElectronicChartCentre/java-vector-tile/blob/master/src/main/java/no/ecc/vectortile/VectorTileEncoder.java">VectorTileEncoder.java</a>
|
|
|
|
* and <a href=
|
|
|
|
* "https://github.com/ElectronicChartCentre/java-vector-tile/blob/master/src/main/java/no/ecc/vectortile/VectorTileDecoder.java">VectorTileDecoder.java</a>
|
2021-09-10 00:46:20 +00:00
|
|
|
* and modified to decouple geometry encoding from vector tile encoding so that encoded commands can be stored in the
|
2022-03-09 02:08:03 +00:00
|
|
|
* sorted feature map prior to encoding vector tiles. The internals are also refactored to improve performance by using
|
2021-04-25 11:42:13 +00:00
|
|
|
* hppc primitive collections.
|
2021-09-10 00:46:20 +00:00
|
|
|
*
|
|
|
|
* @see <a href="https://github.com/mapbox/vector-tile-spec/tree/master/2.1">Mapbox Vector Tile Specification</a>
|
2021-04-25 11:42:13 +00:00
|
|
|
*/
|
2021-09-10 00:46:20 +00:00
|
|
|
@NotThreadSafe
|
|
|
|
public class VectorTile {
|
2024-01-15 11:22:30 +00:00
|
|
|
public static final long NO_FEATURE_ID = 0;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
private static final Logger LOGGER = LoggerFactory.getLogger(VectorTile.class);
|
2021-04-25 19:52:24 +00:00
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
// TODO make these configurable
|
2021-04-25 11:42:13 +00:00
|
|
|
private static final int EXTENT = 4096;
|
|
|
|
private static final double SIZE = 256d;
|
2024-01-11 13:42:16 +00:00
|
|
|
// use a treemap to ensure that layers are encoded in a consistent order
|
|
|
|
private final Map<String, Layer> layers = new TreeMap<>();
|
2023-12-15 00:26:27 +00:00
|
|
|
private LayerAttrStats.Updater.ForZoom layerStatsTracker = LayerAttrStats.Updater.ForZoom.NOOP;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
private static int[] getCommands(Geometry input, int scale) {
|
|
|
|
var encoder = new CommandEncoder(scale);
|
2021-04-25 11:42:13 +00:00
|
|
|
encoder.accept(input);
|
|
|
|
return encoder.result.toArray();
|
|
|
|
}
|
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
/**
|
|
|
|
* Scales a geometry down by a factor of {@code 2^scale} without materializing an intermediate JTS geometry and
|
|
|
|
* returns the encoded result.
|
|
|
|
*/
|
|
|
|
private static int[] unscale(int[] commands, int scale, GeometryType geomType) {
|
|
|
|
IntArrayList result = new IntArrayList();
|
|
|
|
int geometryCount = commands.length;
|
|
|
|
int length = 0;
|
|
|
|
int command = 0;
|
|
|
|
int i = 0;
|
|
|
|
int inX = 0, inY = 0;
|
|
|
|
int outX = 0, outY = 0;
|
|
|
|
int startX = 0, startY = 0;
|
|
|
|
double scaleFactor = Math.pow(2, -scale);
|
|
|
|
int lengthIdx = 0;
|
|
|
|
int moveToIdx = 0;
|
|
|
|
int pointsInShape = 0;
|
|
|
|
boolean first = true;
|
|
|
|
while (i < geometryCount) {
|
|
|
|
if (length <= 0) {
|
|
|
|
length = commands[i++];
|
|
|
|
lengthIdx = result.size();
|
|
|
|
result.add(length);
|
|
|
|
command = length & ((1 << 3) - 1);
|
|
|
|
length = length >> 3;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (length > 0) {
|
|
|
|
if (command == Command.MOVE_TO.value) {
|
|
|
|
// degenerate geometry, remove it from output entirely
|
|
|
|
if (!first && pointsInShape < geomType.minPoints()) {
|
|
|
|
int prevCommand = result.get(lengthIdx);
|
|
|
|
result.elementsCount = moveToIdx;
|
|
|
|
result.add(prevCommand);
|
|
|
|
// reset deltas
|
|
|
|
outX = startX;
|
|
|
|
outY = startY;
|
|
|
|
}
|
|
|
|
// keep track of size of next shape...
|
|
|
|
pointsInShape = 0;
|
|
|
|
startX = outX;
|
|
|
|
startY = outY;
|
|
|
|
moveToIdx = result.size() - 1;
|
|
|
|
}
|
|
|
|
first = false;
|
|
|
|
if (command == Command.CLOSE_PATH.value) {
|
|
|
|
pointsInShape++;
|
|
|
|
length--;
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
int dx = commands[i++];
|
|
|
|
int dy = commands[i++];
|
|
|
|
|
|
|
|
length--;
|
|
|
|
|
|
|
|
dx = zigZagDecode(dx);
|
|
|
|
dy = zigZagDecode(dy);
|
|
|
|
|
|
|
|
inX = inX + dx;
|
|
|
|
inY = inY + dy;
|
|
|
|
|
|
|
|
int nextX = (int) Math.round(inX * scaleFactor);
|
|
|
|
int nextY = (int) Math.round(inY * scaleFactor);
|
|
|
|
|
|
|
|
if (nextX == outX && nextY == outY && command == Command.LINE_TO.value) {
|
|
|
|
int commandLength = result.get(lengthIdx) - 8;
|
|
|
|
if (commandLength < 8) {
|
|
|
|
// get rid of lineto section if empty
|
|
|
|
result.elementsCount = lengthIdx;
|
|
|
|
} else {
|
|
|
|
result.set(lengthIdx, commandLength);
|
|
|
|
}
|
|
|
|
} else {
|
|
|
|
pointsInShape++;
|
|
|
|
int dxOut = nextX - outX;
|
|
|
|
int dyOut = nextY - outY;
|
|
|
|
result.add(
|
|
|
|
zigZagEncode(dxOut),
|
|
|
|
zigZagEncode(dyOut)
|
|
|
|
);
|
|
|
|
outX = nextX;
|
|
|
|
outY = nextY;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
// degenerate geometry, remove it from output entirely
|
|
|
|
if (pointsInShape < geomType.minPoints()) {
|
|
|
|
result.elementsCount = moveToIdx;
|
|
|
|
}
|
|
|
|
return result.toArray();
|
|
|
|
}
|
|
|
|
|
2023-09-24 12:10:47 +00:00
|
|
|
static int zigZagEncode(int n) {
|
2021-04-25 11:42:13 +00:00
|
|
|
// https://developers.google.com/protocol-buffers/docs/encoding#types
|
|
|
|
return (n << 1) ^ (n >> 31);
|
|
|
|
}
|
|
|
|
|
|
|
|
private static int zigZagDecode(int n) {
|
|
|
|
// https://developers.google.com/protocol-buffers/docs/encoding#types
|
|
|
|
return ((n >> 1) ^ (-(n & 1)));
|
|
|
|
}
|
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
private static Geometry decodeCommands(GeometryType geomType, int[] commands, int scale) throws GeometryException {
|
2021-05-23 19:06:26 +00:00
|
|
|
try {
|
|
|
|
GeometryFactory gf = GeoUtils.JTS_FACTORY;
|
2021-10-20 01:57:47 +00:00
|
|
|
double SCALE = (EXTENT << scale) / SIZE;
|
2021-05-23 19:06:26 +00:00
|
|
|
int x = 0;
|
|
|
|
int y = 0;
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
List<MutableCoordinateSequence> allCoordSeqs = new ArrayList<>();
|
|
|
|
MutableCoordinateSequence currentCoordSeq = null;
|
2021-05-23 19:06:26 +00:00
|
|
|
|
|
|
|
int geometryCount = commands.length;
|
|
|
|
int length = 0;
|
|
|
|
int command = 0;
|
|
|
|
int i = 0;
|
|
|
|
while (i < geometryCount) {
|
|
|
|
|
|
|
|
if (length <= 0) {
|
|
|
|
length = commands[i++];
|
|
|
|
command = length & ((1 << 3) - 1);
|
|
|
|
length = length >> 3;
|
2023-09-24 12:10:47 +00:00
|
|
|
assert geomType != GeometryType.POINT || i == 1 : "Invalid multipoint, command found at index %d, expected 0"
|
|
|
|
.formatted(i);
|
|
|
|
assert geomType != GeometryType.POINT ||
|
|
|
|
(length * 2 + 1 == geometryCount) : "Invalid multipoint: int[%d] length=%d".formatted(geometryCount,
|
|
|
|
length);
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
if (length > 0) {
|
|
|
|
|
|
|
|
if (command == Command.MOVE_TO.value) {
|
2021-09-10 00:46:20 +00:00
|
|
|
currentCoordSeq = new MutableCoordinateSequence();
|
|
|
|
allCoordSeqs.add(currentCoordSeq);
|
2021-05-23 19:06:26 +00:00
|
|
|
} else {
|
2021-09-10 00:46:20 +00:00
|
|
|
assert currentCoordSeq != null;
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
if (command == Command.CLOSE_PATH.value) {
|
2021-09-10 00:46:20 +00:00
|
|
|
if (geomType != GeometryType.POINT && !currentCoordSeq.isEmpty()) {
|
|
|
|
currentCoordSeq.closeRing();
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
|
|
|
length--;
|
|
|
|
continue;
|
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
int dx = commands[i++];
|
|
|
|
int dy = commands[i++];
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
length--;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
dx = zigZagDecode(dx);
|
|
|
|
dy = zigZagDecode(dy);
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
x = x + dx;
|
|
|
|
y = y + dy;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
currentCoordSeq.forceAddPoint(x / SCALE, y / SCALE);
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
Geometry geometry = null;
|
|
|
|
boolean outerCCW = false;
|
|
|
|
|
|
|
|
switch (geomType) {
|
2021-09-10 00:46:20 +00:00
|
|
|
case LINE -> {
|
|
|
|
List<LineString> lineStrings = new ArrayList<>(allCoordSeqs.size());
|
|
|
|
for (MutableCoordinateSequence coordSeq : allCoordSeqs) {
|
|
|
|
if (coordSeq.size() <= 1) {
|
2021-05-23 19:06:26 +00:00
|
|
|
continue;
|
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
lineStrings.add(gf.createLineString(coordSeq));
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2021-05-23 19:06:26 +00:00
|
|
|
if (lineStrings.size() == 1) {
|
2023-10-28 00:29:26 +00:00
|
|
|
geometry = lineStrings.getFirst();
|
2021-05-23 19:06:26 +00:00
|
|
|
} else if (lineStrings.size() > 1) {
|
|
|
|
geometry = gf.createMultiLineString(lineStrings.toArray(new LineString[0]));
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
}
|
|
|
|
case POINT -> {
|
|
|
|
CoordinateSequence cs = new PackedCoordinateSequence.Double(allCoordSeqs.size(), 2, 0);
|
|
|
|
for (int j = 0; j < allCoordSeqs.size(); j++) {
|
|
|
|
MutableCoordinateSequence coordSeq = allCoordSeqs.get(j);
|
|
|
|
cs.setOrdinate(j, 0, coordSeq.getX(0));
|
|
|
|
cs.setOrdinate(j, 1, coordSeq.getY(0));
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2021-05-23 19:06:26 +00:00
|
|
|
if (cs.size() == 1) {
|
|
|
|
geometry = gf.createPoint(cs);
|
|
|
|
} else if (cs.size() > 1) {
|
|
|
|
geometry = gf.createMultiPoint(cs);
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
}
|
|
|
|
case POLYGON -> {
|
2021-05-23 19:06:26 +00:00
|
|
|
List<List<LinearRing>> polygonRings = new ArrayList<>();
|
|
|
|
List<LinearRing> ringsForCurrentPolygon = new ArrayList<>();
|
|
|
|
boolean first = true;
|
2021-09-10 00:46:20 +00:00
|
|
|
for (MutableCoordinateSequence coordSeq : allCoordSeqs) {
|
2021-05-23 19:06:26 +00:00
|
|
|
// skip hole with too few coordinates
|
2021-09-10 00:46:20 +00:00
|
|
|
if (ringsForCurrentPolygon.size() > 0 && coordSeq.size() < 2) {
|
2021-05-23 19:06:26 +00:00
|
|
|
continue;
|
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
LinearRing ring = gf.createLinearRing(coordSeq);
|
|
|
|
boolean ccw = Orientation.isCCW(coordSeq);
|
2021-05-23 19:06:26 +00:00
|
|
|
if (first) {
|
|
|
|
first = false;
|
|
|
|
outerCCW = ccw;
|
2021-06-02 11:54:21 +00:00
|
|
|
assert outerCCW : "outer ring is not counter-clockwise";
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
|
|
|
if (ccw == outerCCW) {
|
|
|
|
ringsForCurrentPolygon = new ArrayList<>();
|
|
|
|
polygonRings.add(ringsForCurrentPolygon);
|
|
|
|
}
|
|
|
|
ringsForCurrentPolygon.add(ring);
|
|
|
|
}
|
|
|
|
List<Polygon> polygons = new ArrayList<>();
|
|
|
|
for (List<LinearRing> rings : polygonRings) {
|
2023-10-28 00:29:26 +00:00
|
|
|
LinearRing shell = rings.getFirst();
|
2021-05-23 19:06:26 +00:00
|
|
|
LinearRing[] holes = rings.subList(1, rings.size()).toArray(new LinearRing[rings.size() - 1]);
|
|
|
|
polygons.add(gf.createPolygon(shell, holes));
|
|
|
|
}
|
|
|
|
if (polygons.size() == 1) {
|
2023-10-28 00:29:26 +00:00
|
|
|
geometry = polygons.getFirst();
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
|
|
|
if (polygons.size() > 1) {
|
|
|
|
geometry = gf.createMultiPolygon(GeometryFactory.toPolygonArray(polygons));
|
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
}
|
|
|
|
default -> {
|
|
|
|
}
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
if (geometry == null) {
|
2021-10-20 01:57:47 +00:00
|
|
|
geometry = GeoUtils.EMPTY_GEOMETRY;
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-05-23 19:06:26 +00:00
|
|
|
return geometry;
|
|
|
|
} catch (IllegalArgumentException e) {
|
2021-06-06 12:00:04 +00:00
|
|
|
throw new GeometryException("decode_vector_tile", "Unable to decode geometry", e);
|
2021-05-23 19:06:26 +00:00
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* Parses a binary-encoded vector tile protobuf into a list of features.
|
|
|
|
* <p>
|
|
|
|
* Does not decode geometries, but clients can call {@link VectorGeometry#decode()} to decode a JTS {@link Geometry}
|
|
|
|
* if needed.
|
|
|
|
* <p>
|
|
|
|
* If {@code encoded} is compressed, clients must decompress it first.
|
|
|
|
*
|
|
|
|
* @param encoded encoded vector tile protobuf
|
|
|
|
* @return list of features on that tile
|
|
|
|
* @throws IllegalStateException if decoding fails
|
|
|
|
* @throws IndexOutOfBoundsException if a tag's key or value refers to an index that does not exist in the keys/values
|
|
|
|
* array for a layer
|
|
|
|
*/
|
2021-04-30 10:31:56 +00:00
|
|
|
public static List<Feature> decode(byte[] encoded) {
|
2021-04-29 10:22:41 +00:00
|
|
|
try {
|
2021-09-10 00:46:20 +00:00
|
|
|
VectorTileProto.Tile tile = VectorTileProto.Tile.parseFrom(encoded);
|
2021-04-30 10:31:56 +00:00
|
|
|
List<Feature> features = new ArrayList<>();
|
2021-09-10 00:46:20 +00:00
|
|
|
for (VectorTileProto.Tile.Layer layer : tile.getLayersList()) {
|
2021-04-29 10:22:41 +00:00
|
|
|
String layerName = layer.getName();
|
2021-04-30 10:31:56 +00:00
|
|
|
assert layer.getExtent() == 4096;
|
2021-04-29 10:22:41 +00:00
|
|
|
List<String> keys = layer.getKeysList();
|
|
|
|
List<Object> values = new ArrayList<>();
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
for (VectorTileProto.Tile.Value value : layer.getValuesList()) {
|
2021-04-29 10:22:41 +00:00
|
|
|
if (value.hasBoolValue()) {
|
|
|
|
values.add(value.getBoolValue());
|
|
|
|
} else if (value.hasDoubleValue()) {
|
|
|
|
values.add(value.getDoubleValue());
|
|
|
|
} else if (value.hasFloatValue()) {
|
|
|
|
values.add(value.getFloatValue());
|
|
|
|
} else if (value.hasIntValue()) {
|
|
|
|
values.add(value.getIntValue());
|
|
|
|
} else if (value.hasSintValue()) {
|
|
|
|
values.add(value.getSintValue());
|
|
|
|
} else if (value.hasUintValue()) {
|
|
|
|
values.add(value.getUintValue());
|
|
|
|
} else if (value.hasStringValue()) {
|
|
|
|
values.add(value.getStringValue());
|
|
|
|
} else {
|
|
|
|
values.add(null);
|
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
for (VectorTileProto.Tile.Feature feature : layer.getFeaturesList()) {
|
2021-04-29 10:22:41 +00:00
|
|
|
int tagsCount = feature.getTagsCount();
|
2023-10-28 00:29:26 +00:00
|
|
|
Map<String, Object> attrs = HashMap.newHashMap(tagsCount / 2);
|
2021-04-29 10:22:41 +00:00
|
|
|
int tagIdx = 0;
|
|
|
|
while (tagIdx < feature.getTagsCount()) {
|
|
|
|
String key = keys.get(feature.getTags(tagIdx++));
|
|
|
|
Object value = values.get(feature.getTags(tagIdx++));
|
|
|
|
attrs.put(key, value);
|
|
|
|
}
|
2021-09-10 00:46:20 +00:00
|
|
|
features.add(new Feature(
|
|
|
|
layerName,
|
|
|
|
feature.getId(),
|
2021-10-20 01:57:47 +00:00
|
|
|
new VectorGeometry(Ints.toArray(feature.getGeometryList()), GeometryType.valueOf(feature.getType()), 0),
|
2021-09-10 00:46:20 +00:00
|
|
|
attrs
|
|
|
|
));
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
2021-04-29 10:22:41 +00:00
|
|
|
return features;
|
|
|
|
} catch (InvalidProtocolBufferException e) {
|
|
|
|
throw new IllegalStateException(e);
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
2022-03-09 02:08:03 +00:00
|
|
|
* Encodes a JTS geometry according to
|
|
|
|
* <a href="https://github.com/mapbox/vector-tile-spec/tree/master/2.1#43-geometry-encoding">Geometry Encoding
|
|
|
|
* Specification</a>.
|
2021-09-10 00:46:20 +00:00
|
|
|
*
|
|
|
|
* @param geometry the JTS geometry to encoded
|
|
|
|
* @return the geometry type and command array for the encoded geometry
|
|
|
|
*/
|
2021-04-30 10:31:56 +00:00
|
|
|
public static VectorGeometry encodeGeometry(Geometry geometry) {
|
2021-10-20 01:57:47 +00:00
|
|
|
return encodeGeometry(geometry, 0);
|
|
|
|
}
|
|
|
|
|
|
|
|
public static VectorGeometry encodeGeometry(Geometry geometry, int scale) {
|
2022-09-23 10:49:09 +00:00
|
|
|
return new VectorGeometry(getCommands(geometry, scale), GeometryType.typeOf(geometry), scale);
|
2021-04-25 19:52:24 +00:00
|
|
|
}
|
|
|
|
|
2023-09-24 12:10:47 +00:00
|
|
|
/**
|
|
|
|
* Returns a new {@link VectorGeometryMerger} that combines encoded geometries of the same type into a merged
|
|
|
|
* multipoint, multilinestring, or multipolygon.
|
|
|
|
*/
|
|
|
|
public static VectorGeometryMerger newMerger(GeometryType geometryType) {
|
|
|
|
return new VectorGeometryMerger(geometryType);
|
|
|
|
}
|
|
|
|
|
2023-09-27 00:56:04 +00:00
|
|
|
/**
|
|
|
|
* Returns the hilbert index of the zig-zag-encoded first point of {@code geometry}.
|
|
|
|
* <p>
|
|
|
|
* This can be useful for sorting geometries to minimize encoded vector tile geometry command size since smaller
|
|
|
|
* offsets take fewer bytes using protobuf varint encoding.
|
|
|
|
*/
|
|
|
|
public static int hilbertIndex(Geometry geometry) {
|
|
|
|
Coordinate coord = geometry.getCoordinate();
|
|
|
|
int x = zigZagEncode((int) Math.round(coord.x * 4096 / 256));
|
|
|
|
int y = zigZagEncode((int) Math.round(coord.y * 4096 / 256));
|
|
|
|
return Hilbert.hilbertXYToIndex(15, x, y);
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns the number of internal geometries in this feature including points/lines/polygons inside multigeometries.
|
|
|
|
*/
|
|
|
|
public static int countGeometries(VectorTileProto.Tile.Feature feature) {
|
|
|
|
int result = 0;
|
|
|
|
int idx = 0;
|
|
|
|
int geomCount = feature.getGeometryCount();
|
|
|
|
while (idx < geomCount) {
|
|
|
|
int length = feature.getGeometry(idx);
|
|
|
|
int command = length & ((1 << 3) - 1);
|
|
|
|
length = length >> 3;
|
|
|
|
if (command == Command.MOVE_TO.value) {
|
|
|
|
result += length;
|
|
|
|
}
|
|
|
|
idx += 1;
|
|
|
|
if (command != Command.CLOSE_PATH.value) {
|
|
|
|
idx += length * 2;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return result;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* Adds features in a layer to this tile.
|
|
|
|
*
|
|
|
|
* @param layerName name of the layer in this tile to add the features to
|
|
|
|
* @param features features to add to the tile
|
|
|
|
* @return this encoder for chaining
|
|
|
|
*/
|
2023-09-24 12:10:47 +00:00
|
|
|
public VectorTile addLayerFeatures(String layerName, List<Feature> features) {
|
2021-04-25 11:42:13 +00:00
|
|
|
if (features.isEmpty()) {
|
|
|
|
return this;
|
|
|
|
}
|
|
|
|
Layer layer = layers.get(layerName);
|
|
|
|
if (layer == null) {
|
|
|
|
layer = new Layer();
|
|
|
|
layers.put(layerName, layer);
|
|
|
|
}
|
2023-12-15 00:26:27 +00:00
|
|
|
var statsTracker = layerStatsTracker.forLayer(layerName);
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-04-30 10:31:56 +00:00
|
|
|
for (Feature inFeature : features) {
|
2021-07-16 10:16:58 +00:00
|
|
|
if (inFeature != null && inFeature.geometry().commands().length > 0) {
|
2021-04-25 11:42:13 +00:00
|
|
|
EncodedFeature outFeature = new EncodedFeature(inFeature);
|
|
|
|
|
|
|
|
for (Map.Entry<String, ?> e : inFeature.attrs().entrySet()) {
|
|
|
|
// skip attribute without value
|
2021-09-10 00:46:20 +00:00
|
|
|
if (e.getValue() != null) {
|
2023-12-15 00:26:27 +00:00
|
|
|
String key = e.getKey();
|
|
|
|
Object value = e.getValue();
|
|
|
|
outFeature.tags.add(layer.key(key));
|
|
|
|
outFeature.tags.add(layer.value(value));
|
|
|
|
statsTracker.accept(key, value);
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
layer.encodedFeatures.add(outFeature);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return this;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
2023-09-22 01:44:09 +00:00
|
|
|
* Returns a vector tile protobuf object with all features in this tile.
|
2021-09-10 00:46:20 +00:00
|
|
|
*/
|
2023-09-22 01:44:09 +00:00
|
|
|
public VectorTileProto.Tile toProto() {
|
2021-09-10 00:46:20 +00:00
|
|
|
VectorTileProto.Tile.Builder tile = VectorTileProto.Tile.newBuilder();
|
2021-04-25 11:42:13 +00:00
|
|
|
for (Map.Entry<String, Layer> e : layers.entrySet()) {
|
|
|
|
String layerName = e.getKey();
|
|
|
|
Layer layer = e.getValue();
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
VectorTileProto.Tile.Layer.Builder tileLayer = VectorTileProto.Tile.Layer.newBuilder()
|
|
|
|
.setVersion(2)
|
|
|
|
.setName(layerName)
|
|
|
|
.setExtent(EXTENT)
|
|
|
|
.addAllKeys(layer.keys());
|
2021-04-25 11:42:13 +00:00
|
|
|
|
|
|
|
for (Object value : layer.values()) {
|
2021-09-10 00:46:20 +00:00
|
|
|
VectorTileProto.Tile.Value.Builder tileValue = VectorTileProto.Tile.Value.newBuilder();
|
2023-10-28 00:29:26 +00:00
|
|
|
switch (value) {
|
|
|
|
case String stringValue -> tileValue.setStringValue(stringValue);
|
|
|
|
case Integer intValue -> tileValue.setSintValue(intValue);
|
|
|
|
case Long longValue -> tileValue.setSintValue(longValue);
|
|
|
|
case Float floatValue -> tileValue.setFloatValue(floatValue);
|
|
|
|
case Double doubleValue -> tileValue.setDoubleValue(doubleValue);
|
|
|
|
case Boolean booleanValue -> tileValue.setBoolValue(booleanValue);
|
|
|
|
case Object other -> tileValue.setStringValue(other.toString());
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
tileLayer.addValues(tileValue.build());
|
|
|
|
}
|
|
|
|
|
|
|
|
for (EncodedFeature feature : layer.encodedFeatures) {
|
2021-09-10 00:46:20 +00:00
|
|
|
VectorTileProto.Tile.Feature.Builder featureBuilder = VectorTileProto.Tile.Feature.newBuilder()
|
|
|
|
.addAllTags(Ints.asList(feature.tags.toArray()))
|
|
|
|
.setType(feature.geometry().geomType().asProtobufType())
|
|
|
|
.addAllGeometry(Ints.asList(feature.geometry().commands()));
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2024-01-15 11:22:30 +00:00
|
|
|
if (feature.id != NO_FEATURE_ID) {
|
2021-04-25 11:42:13 +00:00
|
|
|
featureBuilder.setId(feature.id);
|
|
|
|
}
|
|
|
|
|
|
|
|
tileLayer.addFeatures(featureBuilder.build());
|
|
|
|
}
|
|
|
|
|
|
|
|
tile.addLayers(tileLayer.build());
|
|
|
|
}
|
2023-09-22 01:44:09 +00:00
|
|
|
return tile.build();
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Creates a vector tile protobuf with all features in this tile and serializes it as a byte array.
|
|
|
|
* <p>
|
|
|
|
* Does not compress the result.
|
|
|
|
*/
|
|
|
|
public byte[] encode() {
|
|
|
|
return toProto().toByteArray();
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2022-06-04 01:04:17 +00:00
|
|
|
/**
|
|
|
|
* Returns true if this tile contains only polygon fills.
|
|
|
|
*/
|
|
|
|
public boolean containsOnlyFills() {
|
|
|
|
return containsOnlyFillsOrEdges(false);
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns true if this tile contains only polygon fills or horizontal/vertical edges that are likely to be repeated
|
|
|
|
* across tiles.
|
|
|
|
*/
|
|
|
|
public boolean containsOnlyFillsOrEdges() {
|
|
|
|
return containsOnlyFillsOrEdges(true);
|
|
|
|
}
|
|
|
|
|
|
|
|
private boolean containsOnlyFillsOrEdges(boolean allowEdges) {
|
|
|
|
boolean empty = true;
|
|
|
|
for (var layer : layers.values()) {
|
|
|
|
for (var feature : layer.encodedFeatures) {
|
|
|
|
empty = false;
|
|
|
|
if (!feature.geometry.isFillOrEdge(allowEdges)) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return !empty;
|
|
|
|
}
|
|
|
|
|
2023-01-14 21:03:50 +00:00
|
|
|
/**
|
|
|
|
* Determine whether a tile is likely to be a duplicate of some other tile hence it makes sense to calculate a hash
|
|
|
|
* for it.
|
|
|
|
* <p>
|
|
|
|
* Deduplication code is aiming for a balance between filtering-out all duplicates and not spending too much CPU on
|
|
|
|
* hash calculations: calculating hashes for all tiles costs too much CPU, not calculating hashes at all means
|
2023-01-17 12:05:45 +00:00
|
|
|
* generating archives which are too big. This method is responsible for achieving that balance.
|
2023-01-14 21:03:50 +00:00
|
|
|
* <p>
|
|
|
|
* Current understanding is, that for the whole planet, there are 267m total tiles and 38m unique tiles. The
|
|
|
|
* {@link #containsOnlyFillsOrEdges()} heuristic catches >99.9% of repeated tiles and cuts down the number of tile
|
|
|
|
* hashes we need to track by 98% (38m to 735k). So it is considered a good tradeoff.
|
|
|
|
*
|
|
|
|
* @return {@code true} if the tile might have duplicates hence we want to calculate a hash for it
|
|
|
|
*/
|
|
|
|
public boolean likelyToBeDuplicated() {
|
|
|
|
return layers.values().stream().allMatch(v -> v.encodedFeatures.isEmpty()) || containsOnlyFillsOrEdges();
|
|
|
|
}
|
|
|
|
|
2023-12-15 00:26:27 +00:00
|
|
|
/**
|
|
|
|
* Call back to {@code layerStats} as vector tile features are being encoded in
|
|
|
|
* {@link #addLayerFeatures(String, List)} to track attribute types present on features in each layer, for example to
|
|
|
|
* emit in tilejson metadata stats.
|
|
|
|
*/
|
|
|
|
public void trackLayerStats(LayerAttrStats.Updater.ForZoom layerStats) {
|
|
|
|
this.layerStatsTracker = layerStats;
|
|
|
|
}
|
|
|
|
|
2023-09-24 12:10:47 +00:00
|
|
|
enum Command {
|
2021-04-25 11:42:13 +00:00
|
|
|
MOVE_TO(1),
|
|
|
|
LINE_TO(2),
|
|
|
|
CLOSE_PATH(7);
|
2022-03-09 02:08:03 +00:00
|
|
|
|
2021-04-25 11:42:13 +00:00
|
|
|
final int value;
|
|
|
|
|
|
|
|
Command(int value) {
|
|
|
|
this.value = value;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2023-09-24 12:10:47 +00:00
|
|
|
/**
|
|
|
|
* Utility that combines encoded geometries of the same type into a merged multipoint, multilinestring, or
|
|
|
|
* multipolygon.
|
|
|
|
*/
|
|
|
|
public static class VectorGeometryMerger implements Consumer<VectorGeometry> {
|
|
|
|
// For the most part this just concatenates the individual command arrays together
|
|
|
|
// EXCEPT we need to adjust the first coordinate of each subsequent linestring to
|
|
|
|
// be an offset from the end of the previous linestring.
|
|
|
|
// AND we need to combine all multipoint "move to" commands into one at the start of
|
|
|
|
// the sequence
|
|
|
|
|
|
|
|
private final GeometryType geometryType;
|
2023-09-27 00:56:04 +00:00
|
|
|
private final IntArrayList result = new IntArrayList();
|
2023-09-24 12:10:47 +00:00
|
|
|
private int overallX = 0;
|
|
|
|
private int overallY = 0;
|
|
|
|
|
|
|
|
private VectorGeometryMerger(GeometryType geometryType) {
|
|
|
|
this.geometryType = geometryType;
|
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public void accept(VectorGeometry vectorGeometry) {
|
|
|
|
if (vectorGeometry.geomType != geometryType) {
|
|
|
|
throw new IllegalArgumentException(
|
|
|
|
"Cannot merge a " + vectorGeometry.geomType.name().toLowerCase(Locale.ROOT) + " geometry into a multi" +
|
|
|
|
vectorGeometry.geomType.name().toLowerCase(Locale.ROOT));
|
|
|
|
}
|
|
|
|
if (vectorGeometry.isEmpty()) {
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
var commands = vectorGeometry.unscale().commands();
|
|
|
|
int x = 0;
|
|
|
|
int y = 0;
|
|
|
|
|
|
|
|
int geometryCount = commands.length;
|
|
|
|
int length = 0;
|
|
|
|
int command = 0;
|
|
|
|
int i = 0;
|
|
|
|
|
|
|
|
result.ensureCapacity(result.elementsCount + commands.length);
|
|
|
|
// and multipoints will end up with only one command ("move to" with length=# points)
|
|
|
|
if (geometryType != GeometryType.POINT || result.isEmpty()) {
|
|
|
|
result.add(commands[0]);
|
|
|
|
}
|
|
|
|
result.add(zigZagEncode(zigZagDecode(commands[1]) - overallX));
|
|
|
|
result.add(zigZagEncode(zigZagDecode(commands[2]) - overallY));
|
|
|
|
if (commands.length > 3) {
|
|
|
|
result.add(commands, 3, commands.length - 3);
|
|
|
|
}
|
|
|
|
|
|
|
|
while (i < geometryCount) {
|
|
|
|
if (length <= 0) {
|
|
|
|
length = commands[i++];
|
|
|
|
command = length & ((1 << 3) - 1);
|
|
|
|
length = length >> 3;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (length > 0) {
|
|
|
|
length--;
|
|
|
|
if (command != Command.CLOSE_PATH.value) {
|
|
|
|
x += zigZagDecode(commands[i++]);
|
|
|
|
y += zigZagDecode(commands[i++]);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
overallX = x;
|
|
|
|
overallY = y;
|
|
|
|
}
|
|
|
|
|
|
|
|
/** Returns the merged multi-geometry. */
|
|
|
|
public VectorGeometry finish() {
|
|
|
|
// set the correct "move to" length for multipoints based on how many points were actually added
|
|
|
|
if (geometryType == GeometryType.POINT) {
|
|
|
|
result.buffer[0] = Command.MOVE_TO.value | (((result.size() - 1) / 2) << 3);
|
|
|
|
}
|
|
|
|
return new VectorGeometry(result.toArray(), geometryType, 0);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
2023-01-23 11:06:57 +00:00
|
|
|
* A vector geometry encoded as a list of commands according to the
|
2022-03-09 02:08:03 +00:00
|
|
|
* <a href="https://github.com/mapbox/vector-tile-spec/tree/master/2.1#43-geometry-encoding">vector tile
|
|
|
|
* specification</a>.
|
2021-10-20 01:57:47 +00:00
|
|
|
* <p>
|
|
|
|
* To encode extra precision in intermediate feature geometries, the geometry contained in {@code commands} is scaled
|
|
|
|
* to a tile extent of {@code EXTENT * 2^scale}, so when the {@code scale == 0} the extent is {@link #EXTENT} and when
|
|
|
|
* {@code scale == 2} the extent is 4x{@link #EXTENT}. Geometries must be scaled back to 0 using {@link #unscale()}
|
2023-01-17 12:05:45 +00:00
|
|
|
* before outputting to the archive.
|
2021-09-10 00:46:20 +00:00
|
|
|
*/
|
2022-02-24 01:45:56 +00:00
|
|
|
public record VectorGeometry(int[] commands, GeometryType geomType, int scale) {
|
2021-10-20 01:57:47 +00:00
|
|
|
|
2022-06-04 01:04:17 +00:00
|
|
|
private static final int LEFT = 1;
|
|
|
|
private static final int RIGHT = 1 << 1;
|
|
|
|
private static final int TOP = 1 << 2;
|
|
|
|
private static final int BOTTOM = 1 << 3;
|
|
|
|
private static final int INSIDE = 0;
|
|
|
|
private static final int ALL = TOP | LEFT | RIGHT | BOTTOM;
|
2023-09-24 12:10:47 +00:00
|
|
|
private static final VectorGeometry EMPTY_POINT = new VectorGeometry(new int[0], GeometryType.POINT, 0);
|
2022-06-04 01:04:17 +00:00
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
public VectorGeometry {
|
|
|
|
if (scale < 0) {
|
|
|
|
throw new IllegalArgumentException("scale can not be less than 0, got: " + scale);
|
|
|
|
}
|
|
|
|
}
|
2021-04-30 10:31:56 +00:00
|
|
|
|
2022-06-04 01:04:17 +00:00
|
|
|
private static int getSide(int x, int y, int extent) {
|
|
|
|
int result = INSIDE;
|
|
|
|
if (x < 0) {
|
|
|
|
result |= LEFT;
|
|
|
|
} else if (x > extent) {
|
|
|
|
result |= RIGHT;
|
|
|
|
}
|
|
|
|
if (y < 0) {
|
|
|
|
result |= TOP;
|
|
|
|
} else if (y > extent) {
|
|
|
|
result |= BOTTOM;
|
|
|
|
}
|
|
|
|
return result;
|
|
|
|
}
|
|
|
|
|
|
|
|
private static boolean slanted(int x1, int y1, int x2, int y2) {
|
|
|
|
return x1 != x2 && y1 != y2;
|
|
|
|
}
|
|
|
|
|
|
|
|
private static boolean segmentCrossesTile(int x1, int y1, int x2, int y2, int extent) {
|
|
|
|
return (y1 >= 0 || y2 >= 0) &&
|
|
|
|
(y1 <= extent || y2 <= extent) &&
|
|
|
|
(x1 >= 0 || x2 >= 0) &&
|
|
|
|
(x1 <= extent || x2 <= extent);
|
|
|
|
}
|
|
|
|
|
|
|
|
private static boolean isSegmentInvalid(boolean allowEdges, int x1, int y1, int x2, int y2, int extent) {
|
|
|
|
boolean crossesTile = segmentCrossesTile(x1, y1, x2, y2, extent);
|
|
|
|
if (allowEdges) {
|
|
|
|
return crossesTile && slanted(x1, y1, x2, y2);
|
|
|
|
} else {
|
|
|
|
return crossesTile;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
private static boolean visitedEnoughSides(boolean allowEdges, int sides) {
|
|
|
|
if (allowEdges) {
|
|
|
|
return ((sides & LEFT) > 0 && (sides & RIGHT) > 0) || ((sides & TOP) > 0 && (sides & BOTTOM) > 0);
|
|
|
|
} else {
|
|
|
|
return sides == ALL;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/** Converts an encoded geometry back to a JTS geometry. */
|
2021-05-23 19:06:26 +00:00
|
|
|
public Geometry decode() throws GeometryException {
|
2021-10-20 01:57:47 +00:00
|
|
|
return decodeCommands(geomType, commands, scale);
|
|
|
|
}
|
|
|
|
|
2023-01-17 12:05:45 +00:00
|
|
|
/** Returns this encoded geometry, scaled back to 0, so it is safe to emit to archive output. */
|
2021-10-20 01:57:47 +00:00
|
|
|
public VectorGeometry unscale() {
|
|
|
|
return scale == 0 ? this : new VectorGeometry(VectorTile.unscale(commands, scale, geomType), geomType, 0);
|
2021-04-30 10:31:56 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public boolean equals(Object o) {
|
|
|
|
if (this == o) {
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
if (o == null || getClass() != o.getClass()) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
VectorGeometry that = (VectorGeometry) o;
|
|
|
|
|
|
|
|
if (geomType != that.geomType) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
return Arrays.equals(commands, that.commands);
|
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public int hashCode() {
|
|
|
|
int result = Arrays.hashCode(commands);
|
2021-05-25 12:01:29 +00:00
|
|
|
result = 31 * result + geomType.hashCode();
|
2021-04-30 10:31:56 +00:00
|
|
|
return result;
|
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public String toString() {
|
|
|
|
return "VectorGeometry[" +
|
|
|
|
"commands=int[" + commands.length +
|
|
|
|
"], geomType=" + geomType +
|
2021-05-25 12:01:29 +00:00
|
|
|
" (" + geomType.asByte() + ")]";
|
2021-04-30 10:31:56 +00:00
|
|
|
}
|
2022-06-04 01:04:17 +00:00
|
|
|
|
|
|
|
/** Returns true if the encoded geometry is a polygon fill. */
|
|
|
|
public boolean isFill() {
|
|
|
|
return isFillOrEdge(false);
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns true if the encoded geometry is a polygon fill, rectangle edge, or part of a horizontal/vertical line
|
|
|
|
* that is likely to be repeated across tiles.
|
|
|
|
*/
|
|
|
|
public boolean isFillOrEdge() {
|
|
|
|
return isFillOrEdge(true);
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns true if the encoded geometry is a polygon fill, or if {@code allowEdges == true} then also a rectangle
|
|
|
|
* edge, or part of a horizontal/vertical line that is likely to be repeated across tiles.
|
|
|
|
*/
|
|
|
|
public boolean isFillOrEdge(boolean allowEdges) {
|
|
|
|
if (geomType != GeometryType.POLYGON && (!allowEdges || geomType != GeometryType.LINE)) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
boolean isLine = geomType == GeometryType.LINE;
|
|
|
|
|
|
|
|
int extent = EXTENT << scale;
|
|
|
|
int visited = INSIDE;
|
|
|
|
int firstX = 0;
|
|
|
|
int firstY = 0;
|
|
|
|
int x = 0;
|
|
|
|
int y = 0;
|
|
|
|
|
|
|
|
int geometryCount = commands.length;
|
|
|
|
int length = 0;
|
|
|
|
int command = 0;
|
|
|
|
int i = 0;
|
|
|
|
while (i < geometryCount) {
|
|
|
|
|
|
|
|
if (length <= 0) {
|
|
|
|
length = commands[i++];
|
|
|
|
command = length & ((1 << 3) - 1);
|
|
|
|
length = length >> 3;
|
|
|
|
if (isLine && length > 2) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
if (length > 0) {
|
|
|
|
if (command == Command.CLOSE_PATH.value) {
|
|
|
|
if (isSegmentInvalid(allowEdges, x, y, firstX, firstY, extent) ||
|
|
|
|
!visitedEnoughSides(allowEdges, visited)) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
length--;
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
int dx = commands[i++];
|
|
|
|
int dy = commands[i++];
|
|
|
|
|
|
|
|
length--;
|
|
|
|
|
|
|
|
dx = zigZagDecode(dx);
|
|
|
|
dy = zigZagDecode(dy);
|
|
|
|
|
|
|
|
int nextX = x + dx;
|
|
|
|
int nextY = y + dy;
|
|
|
|
|
|
|
|
if (command == Command.MOVE_TO.value) {
|
|
|
|
firstX = nextX;
|
|
|
|
firstY = nextY;
|
|
|
|
if ((visited = getSide(firstX, firstY, extent)) == INSIDE) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
} else {
|
|
|
|
if (isSegmentInvalid(allowEdges, x, y, nextX, nextY, extent)) {
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
visited |= getSide(nextX, nextY, extent);
|
|
|
|
}
|
|
|
|
y = nextY;
|
|
|
|
x = nextX;
|
|
|
|
}
|
|
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
return visitedEnoughSides(allowEdges, visited);
|
|
|
|
}
|
|
|
|
|
2023-09-24 12:10:47 +00:00
|
|
|
/** Returns true if there are no commands in this geometry. */
|
|
|
|
public boolean isEmpty() {
|
|
|
|
return commands.length == 0;
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* If this is a point, returns an empty geometry if more than {@code buffer} pixels outside the tile bounds, or if
|
|
|
|
* it is a multipoint than removes all points outside the buffer.
|
|
|
|
*/
|
|
|
|
public VectorGeometry filterPointsOutsideBuffer(double buffer) {
|
|
|
|
if (geomType != GeometryType.POINT) {
|
|
|
|
return this;
|
|
|
|
}
|
|
|
|
IntArrayList result = null;
|
|
|
|
|
|
|
|
int extent = (EXTENT << scale);
|
|
|
|
int bufferInt = (int) Math.ceil(buffer * extent / 256);
|
|
|
|
int min = -bufferInt;
|
|
|
|
int max = extent + bufferInt;
|
|
|
|
|
|
|
|
int x = 0;
|
|
|
|
int y = 0;
|
|
|
|
int lastX = 0;
|
|
|
|
int lastY = 0;
|
|
|
|
|
|
|
|
int geometryCount = commands.length;
|
|
|
|
int length = 0;
|
|
|
|
int i = 0;
|
|
|
|
|
|
|
|
while (i < geometryCount) {
|
|
|
|
if (length <= 0) {
|
|
|
|
length = commands[i++] >> 3;
|
|
|
|
assert i <= 1 : "Bad index " + i;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (length > 0) {
|
|
|
|
length--;
|
|
|
|
x += zigZagDecode(commands[i++]);
|
|
|
|
y += zigZagDecode(commands[i++]);
|
|
|
|
if (x < min || y < min || x > max || y > max) {
|
|
|
|
if (result == null) {
|
|
|
|
// short-circuit the common case of only a single point that gets filtered-out
|
|
|
|
if (commands.length == 3) {
|
|
|
|
return EMPTY_POINT;
|
|
|
|
}
|
|
|
|
result = new IntArrayList(commands.length);
|
|
|
|
result.add(commands, 0, i - 2);
|
|
|
|
}
|
|
|
|
} else {
|
|
|
|
if (result != null) {
|
|
|
|
result.add(zigZagEncode(x - lastX), zigZagEncode(y - lastY));
|
|
|
|
}
|
|
|
|
lastX = x;
|
|
|
|
lastY = y;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
if (result != null) {
|
|
|
|
if (result.size() < 3) {
|
|
|
|
result.elementsCount = 0;
|
|
|
|
} else {
|
|
|
|
result.set(0, Command.MOVE_TO.value | (((result.size() - 1) / 2) << 3));
|
|
|
|
}
|
|
|
|
|
|
|
|
return new VectorGeometry(result.toArray(), geomType, scale);
|
|
|
|
} else {
|
|
|
|
return this;
|
|
|
|
}
|
|
|
|
}
|
2023-09-27 00:56:04 +00:00
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns the hilbert index of the zig-zag-encoded first point of this feature.
|
|
|
|
* <p>
|
|
|
|
* This can be useful for sorting geometries to minimize encoded vector tile geometry command size since smaller
|
|
|
|
* offsets take fewer bytes using protobuf varint encoding.
|
|
|
|
*/
|
|
|
|
public int hilbertIndex() {
|
|
|
|
if (commands.length < 3) {
|
|
|
|
return 0;
|
|
|
|
}
|
|
|
|
int x = commands[1];
|
|
|
|
int y = commands[2];
|
|
|
|
return Hilbert.hilbertXYToIndex(15, x >> scale, y >> scale);
|
|
|
|
}
|
|
|
|
|
2021-04-30 10:31:56 +00:00
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* A feature in a vector tile.
|
|
|
|
*
|
|
|
|
* @param layer the layer the feature was in
|
|
|
|
* @param id the feature ID
|
|
|
|
* @param geometry the encoded feature geometry (decode using {@link VectorGeometry#decode()})
|
|
|
|
* @param attrs tags for the feature to output
|
|
|
|
* @param group grouping key used to limit point density or {@link #NO_GROUP} if not in a group. NOTE: this is only
|
|
|
|
* populated when this feature was deserialized from {@link FeatureGroup}, not when parsed from a tile
|
|
|
|
* since vector tile schema does not encode group.
|
|
|
|
*/
|
2022-02-24 01:45:56 +00:00
|
|
|
public record Feature(
|
2021-04-30 10:31:56 +00:00
|
|
|
String layer,
|
|
|
|
long id,
|
|
|
|
VectorGeometry geometry,
|
2021-05-31 11:16:44 +00:00
|
|
|
Map<String, Object> attrs,
|
|
|
|
long group
|
2021-04-30 10:31:56 +00:00
|
|
|
) {
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
public static final long NO_GROUP = Long.MIN_VALUE;
|
|
|
|
|
2021-05-31 11:16:44 +00:00
|
|
|
public Feature(
|
|
|
|
String layer,
|
|
|
|
long id,
|
|
|
|
VectorGeometry geometry,
|
|
|
|
Map<String, Object> attrs
|
|
|
|
) {
|
|
|
|
this(layer, id, geometry, attrs, NO_GROUP);
|
|
|
|
}
|
|
|
|
|
2021-06-25 11:06:55 +00:00
|
|
|
public boolean hasGroup() {
|
|
|
|
return group != NO_GROUP;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* Encodes {@code newGeometry} and returns a copy of this feature with {@code geometry} replaced with the encoded
|
|
|
|
* new geometry.
|
|
|
|
*/
|
2021-04-30 10:31:56 +00:00
|
|
|
public Feature copyWithNewGeometry(Geometry newGeometry) {
|
2021-10-20 01:57:47 +00:00
|
|
|
return copyWithNewGeometry(encodeGeometry(newGeometry));
|
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Returns a copy of this feature with {@code geometry} replaced with {@code newGeometry}.
|
|
|
|
*/
|
|
|
|
public Feature copyWithNewGeometry(VectorGeometry newGeometry) {
|
2023-09-24 12:10:47 +00:00
|
|
|
return newGeometry == geometry ? this : new Feature(
|
2021-04-30 10:31:56 +00:00
|
|
|
layer,
|
|
|
|
id,
|
2021-10-20 01:57:47 +00:00
|
|
|
newGeometry,
|
2021-05-31 11:16:44 +00:00
|
|
|
attrs,
|
|
|
|
group
|
|
|
|
);
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/** Returns a copy of this feature with {@code extraAttrs} added to {@code attrs}. */
|
2021-05-31 11:16:44 +00:00
|
|
|
public Feature copyWithExtraAttrs(Map<String, Object> extraAttrs) {
|
|
|
|
return new Feature(
|
|
|
|
layer,
|
|
|
|
id,
|
|
|
|
geometry,
|
|
|
|
Stream.concat(attrs.entrySet().stream(), extraAttrs.entrySet().stream())
|
|
|
|
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)),
|
|
|
|
group
|
2021-04-30 10:31:56 +00:00
|
|
|
);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* Encodes a geometry as a sequence of integers according to the
|
2022-03-09 02:08:03 +00:00
|
|
|
* <a href="https://github.com/mapbox/vector-tile-spec/tree/master/2.1#43-geometry-encoding">Geometry * Encoding
|
2021-09-10 00:46:20 +00:00
|
|
|
* Specification</a>.
|
|
|
|
*/
|
2021-04-25 11:42:13 +00:00
|
|
|
private static class CommandEncoder {
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
final IntArrayList result = new IntArrayList();
|
2021-10-20 01:57:47 +00:00
|
|
|
private final double SCALE;
|
2021-09-10 00:46:20 +00:00
|
|
|
// Initial points use absolute locations, then subsequent points in a geometry use offsets so
|
|
|
|
// need to keep track of previous x/y location during the encoding.
|
|
|
|
int x = 0, y = 0;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
CommandEncoder(int scale) {
|
|
|
|
this.SCALE = (EXTENT << scale) / SIZE;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
static boolean shouldClosePath(Geometry geometry) {
|
2021-04-25 11:42:13 +00:00
|
|
|
return (geometry instanceof Polygon) || (geometry instanceof LinearRing);
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
static int commandAndLength(Command command, int repeat) {
|
2021-04-25 11:42:13 +00:00
|
|
|
return repeat << 3 | command.value;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
void accept(Geometry geometry) {
|
2023-10-28 00:29:26 +00:00
|
|
|
switch (geometry) {
|
|
|
|
case MultiLineString multiLineString -> {
|
|
|
|
for (int i = 0; i < multiLineString.getNumGeometries(); i++) {
|
|
|
|
encode(((LineString) multiLineString.getGeometryN(i)).getCoordinateSequence(), false, GeometryType.LINE);
|
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2023-10-28 00:29:26 +00:00
|
|
|
case Polygon polygon -> {
|
|
|
|
LineString exteriorRing = polygon.getExteriorRing();
|
|
|
|
encode(exteriorRing.getCoordinateSequence(), true, GeometryType.POLYGON);
|
|
|
|
for (int i = 0; i < polygon.getNumInteriorRing(); i++) {
|
|
|
|
LineString interiorRing = polygon.getInteriorRingN(i);
|
|
|
|
encode(interiorRing.getCoordinateSequence(), true, GeometryType.LINE);
|
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2023-10-28 00:29:26 +00:00
|
|
|
case MultiPolygon multiPolygon -> {
|
|
|
|
for (int i = 0; i < multiPolygon.getNumGeometries(); i++) {
|
|
|
|
accept(multiPolygon.getGeometryN(i));
|
|
|
|
}
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
2023-10-28 00:29:26 +00:00
|
|
|
case LineString lineString ->
|
|
|
|
encode(lineString.getCoordinateSequence(), shouldClosePath(geometry), GeometryType.LINE);
|
|
|
|
case Point point -> encode(point.getCoordinateSequence(), false, GeometryType.POINT);
|
|
|
|
case Puntal ignored -> encode(new CoordinateArraySequence(geometry.getCoordinates()), shouldClosePath(geometry),
|
2021-10-20 01:57:47 +00:00
|
|
|
geometry instanceof MultiPoint, GeometryType.POINT);
|
2023-10-28 00:29:26 +00:00
|
|
|
case null -> LOGGER.warn("Null geometry type");
|
|
|
|
default -> LOGGER.warn("Unrecognized geometry type: " + geometry.getGeometryType());
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
void encode(CoordinateSequence cs, boolean closePathAtEnd, GeometryType geomType) {
|
|
|
|
encode(cs, closePathAtEnd, false, geomType);
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
void encode(CoordinateSequence cs, boolean closePathAtEnd, boolean multiPoint, GeometryType geomType) {
|
2021-04-25 11:42:13 +00:00
|
|
|
if (cs.size() == 0) {
|
|
|
|
throw new IllegalArgumentException("empty geometry");
|
|
|
|
}
|
|
|
|
|
2021-10-20 01:57:47 +00:00
|
|
|
int startIdx = result.size();
|
|
|
|
int numPoints = 0;
|
2021-04-25 11:42:13 +00:00
|
|
|
int lineToIndex = 0;
|
|
|
|
int lineToLength = 0;
|
2021-10-20 01:57:47 +00:00
|
|
|
int startX = x;
|
|
|
|
int startY = y;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
|
|
|
for (int i = 0; i < cs.size(); i++) {
|
|
|
|
|
|
|
|
double cx = cs.getX(i);
|
|
|
|
double cy = cs.getY(i);
|
|
|
|
|
|
|
|
if (i == 0) {
|
|
|
|
result.add(commandAndLength(Command.MOVE_TO, multiPoint ? cs.size() : 1));
|
|
|
|
}
|
|
|
|
|
|
|
|
int _x = (int) Math.round(cx * SCALE);
|
|
|
|
int _y = (int) Math.round(cy * SCALE);
|
|
|
|
|
|
|
|
// prevent point equal to the previous
|
2021-10-20 01:57:47 +00:00
|
|
|
if (i > 0 && _x == x && _y == y && !multiPoint) {
|
2021-04-25 11:42:13 +00:00
|
|
|
lineToLength--;
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
// prevent double closing
|
|
|
|
if (closePathAtEnd && cs.size() > 1 && i == (cs.size() - 1) && cs.getX(0) == cx && cs.getY(0) == cy) {
|
|
|
|
lineToLength--;
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
// delta, then zigzag
|
|
|
|
result.add(zigZagEncode(_x - x));
|
|
|
|
result.add(zigZagEncode(_y - y));
|
2021-10-20 01:57:47 +00:00
|
|
|
numPoints++;
|
2021-04-25 11:42:13 +00:00
|
|
|
|
|
|
|
x = _x;
|
|
|
|
y = _y;
|
|
|
|
|
|
|
|
if (i == 0 && cs.size() > 1 && !multiPoint) {
|
|
|
|
// can length be too long?
|
|
|
|
lineToIndex = result.size();
|
|
|
|
lineToLength = cs.size() - 1;
|
|
|
|
result.add(commandAndLength(Command.LINE_TO, lineToLength));
|
|
|
|
}
|
|
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
// update LineTo length
|
|
|
|
if (lineToIndex > 0) {
|
|
|
|
if (lineToLength == 0) {
|
|
|
|
// remove empty LineTo
|
|
|
|
result.remove(lineToIndex);
|
|
|
|
} else {
|
|
|
|
// update LineTo with new length
|
|
|
|
result.set(lineToIndex, commandAndLength(Command.LINE_TO, lineToLength));
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
if (closePathAtEnd) {
|
|
|
|
result.add(commandAndLength(Command.CLOSE_PATH, 1));
|
2021-10-20 01:57:47 +00:00
|
|
|
numPoints++;
|
|
|
|
}
|
|
|
|
|
|
|
|
// degenerate geometry, skip emitting
|
|
|
|
if (numPoints < geomType.minPoints()) {
|
|
|
|
result.elementsCount = startIdx;
|
|
|
|
// reset deltas
|
|
|
|
x = startX;
|
|
|
|
y = startY;
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2022-02-24 01:45:56 +00:00
|
|
|
private record EncodedFeature(IntArrayList tags, long id, VectorGeometry geometry) {
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-04-30 10:31:56 +00:00
|
|
|
EncodedFeature(Feature in) {
|
|
|
|
this(new IntArrayList(), in.id(), in.geometry());
|
2021-04-25 11:42:13 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/**
|
|
|
|
* Holds all features in an output layer of this tile, along with the index of each tag key/value so that features can
|
|
|
|
* store each key/value as a pair of integers.
|
|
|
|
*/
|
2021-04-25 11:42:13 +00:00
|
|
|
private static final class Layer {
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
final List<EncodedFeature> encodedFeatures = new ArrayList<>();
|
|
|
|
final Map<String, Integer> keys = new LinkedHashMap<>();
|
|
|
|
final Map<Object, Integer> values = new LinkedHashMap<>();
|
2021-04-25 11:42:13 +00:00
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
List<String> keys() {
|
|
|
|
return new ArrayList<>(keys.keySet());
|
|
|
|
}
|
|
|
|
|
|
|
|
List<Object> values() {
|
|
|
|
return new ArrayList<>(values.keySet());
|
|
|
|
}
|
|
|
|
|
|
|
|
/** Returns the ID associated with {@code key} or adds a new one if not present. */
|
|
|
|
Integer key(String key) {
|
2021-04-25 11:42:13 +00:00
|
|
|
Integer i = keys.get(key);
|
|
|
|
if (i == null) {
|
|
|
|
i = keys.size();
|
|
|
|
keys.put(key, i);
|
|
|
|
}
|
|
|
|
return i;
|
|
|
|
}
|
|
|
|
|
2021-09-10 00:46:20 +00:00
|
|
|
/** Returns the ID associated with {@code value} or adds a new one if not present. */
|
|
|
|
Integer value(Object value) {
|
2021-04-25 11:42:13 +00:00
|
|
|
Integer i = values.get(value);
|
|
|
|
if (i == null) {
|
|
|
|
i = values.size();
|
|
|
|
values.put(value, i);
|
|
|
|
}
|
|
|
|
return i;
|
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public String toString() {
|
|
|
|
return "Layer{" + encodedFeatures.size() + "}";
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|