001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.vector;
003
004import static java.util.stream.Collectors.toCollection;
005import static java.util.stream.Collectors.toList;
006
007import java.awt.Shape;
008import java.awt.geom.Area;
009import java.awt.geom.Ellipse2D;
010import java.awt.geom.Path2D;
011import java.awt.geom.PathIterator;
012import java.util.ArrayList;
013import java.util.Collection;
014import java.util.Collections;
015import java.util.List;
016import java.util.Objects;
017
018import org.openstreetmap.gui.jmapviewer.Coordinate;
019import org.openstreetmap.gui.jmapviewer.Tile;
020import org.openstreetmap.gui.jmapviewer.interfaces.ICoordinate;
021import org.openstreetmap.josm.data.IQuadBucketType;
022import org.openstreetmap.josm.data.imagery.vectortile.VectorTile;
023import org.openstreetmap.josm.data.imagery.vectortile.mapbox.Feature;
024import org.openstreetmap.josm.data.imagery.vectortile.mapbox.Layer;
025import org.openstreetmap.josm.data.osm.BBox;
026import org.openstreetmap.josm.data.osm.INode;
027import org.openstreetmap.josm.data.osm.IPrimitive;
028import org.openstreetmap.josm.data.osm.IRelation;
029import org.openstreetmap.josm.data.osm.IWay;
030import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
031import org.openstreetmap.josm.data.osm.SimplePrimitiveId;
032import org.openstreetmap.josm.data.osm.UniqueIdGenerator;
033import org.openstreetmap.josm.gui.dialogs.relation.sort.RelationSorter;
034import org.openstreetmap.josm.tools.Destroyable;
035import org.openstreetmap.josm.tools.Geometry;
036import org.openstreetmap.josm.tools.JosmRuntimeException;
037import org.openstreetmap.josm.tools.Logging;
038
039/**
040 * A data store for Vector Data sets
041 * @author Taylor Smock
042 * @since 17862
043 */
044public class VectorDataStore extends DataStore<VectorPrimitive, VectorNode, VectorWay, VectorRelation> implements Destroyable {
045    private static final String JOSM_MERGE_TYPE_KEY = "josm_merge_type";
046    private static final String ORIGINAL_ID = "original_id";
047    private static final String MULTIPOLYGON_TYPE = "multipolygon";
048    private static final String RELATION_TYPE = "type";
049
050    @Override
051    protected void addPrimitive(VectorPrimitive primitive) {
052        // The field is uint64, so we can use negative numbers to indicate that it is a "generated" object (e.g., nodes for ways)
053        if (primitive.getUniqueId() == 0) {
054            final UniqueIdGenerator generator = primitive.getIdGenerator();
055            long id;
056            do {
057                id = generator.generateUniqueId();
058            } while (this.primitivesMap.containsKey(new SimplePrimitiveId(id, primitive.getType())));
059            primitive.setId(primitive.getIdGenerator().generateUniqueId());
060        }
061        if (primitive instanceof VectorRelation && !primitive.isMultipolygon()) {
062            primitive = mergeWays((VectorRelation) primitive);
063        }
064        final VectorPrimitive alreadyAdded = this.primitivesMap.get(primitive.getPrimitiveId());
065        final VectorRelation mergedRelation = (VectorRelation) this.primitivesMap
066          .get(new SimplePrimitiveId(primitive.getPrimitiveId().getUniqueId(),
067            OsmPrimitiveType.RELATION));
068        if (alreadyAdded == null || alreadyAdded.equals(primitive)) {
069            super.addPrimitive(primitive);
070        } else if (mergedRelation != null && mergedRelation.get(JOSM_MERGE_TYPE_KEY) != null) {
071            mergedRelation.addRelationMember(new VectorRelationMember("", primitive));
072            super.addPrimitive(primitive);
073            // Check that all primitives can be merged
074            if (mergedRelation.getMemberPrimitivesList().stream().allMatch(IWay.class::isInstance)) {
075                // This pretty much does the "right" thing
076                this.mergeWays(mergedRelation);
077            } else if (!(primitive instanceof IWay)) {
078                // Can't merge, ever (one of the childs is a node/relation)
079                mergedRelation.remove(JOSM_MERGE_TYPE_KEY);
080            }
081        } else if (mergedRelation != null && primitive instanceof IRelation) {
082            // Just add to the relation
083            ((VectorRelation) primitive).getMembers().forEach(mergedRelation::addRelationMember);
084        } else if (alreadyAdded instanceof VectorWay && primitive instanceof VectorWay) {
085            final VectorRelation temporaryRelation =
086              mergedRelation == null ? new VectorRelation(primitive.getLayer()) : mergedRelation;
087            if (mergedRelation == null) {
088                temporaryRelation.put(JOSM_MERGE_TYPE_KEY, "merge");
089                temporaryRelation.addRelationMember(new VectorRelationMember("", alreadyAdded));
090            }
091            temporaryRelation.addRelationMember(new VectorRelationMember("", primitive));
092            super.addPrimitive(primitive);
093            super.addPrimitive(temporaryRelation);
094        }
095    }
096
097    private VectorPrimitive mergeWays(VectorRelation relation) {
098        List<VectorRelationMember> members = RelationSorter.sortMembersByConnectivity(relation.getMembers());
099        Collection<VectorWay> relationWayList = members.stream().map(VectorRelationMember::getMember)
100          .filter(VectorWay.class::isInstance)
101          .map(VectorWay.class::cast).collect(toCollection(ArrayList::new));
102        // Only support way-only relations
103        if (relationWayList.size() != relation.getMemberPrimitivesList().size()) {
104            return relation;
105        }
106        List<VectorWay> wayList = new ArrayList<>(relation.getMembersCount());
107        // Assume that the order may not be correct, worst case O(n), best case O(n/2)
108        // Assume that the ways were drawn in order
109        final int maxIteration = relationWayList.size();
110        int iteration = 0;
111        while (iteration < maxIteration && wayList.size() < relationWayList.size()) {
112            for (VectorWay way : relationWayList) {
113                if (wayList.isEmpty()) {
114                    wayList.add(way);
115                    continue;
116                }
117                // Check first/last ways (last first, since the list *should* be sorted)
118                if (canMergeWays(wayList.get(wayList.size() - 1), way, false)) {
119                    wayList.add(way);
120                } else if (canMergeWays(wayList.get(0), way, false)) {
121                    wayList.add(0, way);
122                }
123            }
124            iteration++;
125            relationWayList.removeIf(wayList::contains);
126        }
127        return relation;
128    }
129
130    private static <N extends INode, W extends IWay<N>> boolean canMergeWays(W old, W toAdd, boolean allowReverse) {
131        final List<N> nodes = new ArrayList<>(old.getNodes());
132        boolean added = true;
133        if (allowReverse && old.firstNode().equals(toAdd.firstNode())) {
134            // old <-|-> new becomes old ->|-> new
135            Collections.reverse(nodes);
136            nodes.addAll(toAdd.getNodes());
137        } else if (old.firstNode().equals(toAdd.lastNode())) {
138            // old <-|<- new, so we prepend the new nodes in order
139            nodes.addAll(0, toAdd.getNodes());
140        } else if (old.lastNode().equals(toAdd.firstNode())) {
141            // old ->|-> new, we just add it
142            nodes.addAll(toAdd.getNodes());
143        } else if (allowReverse && old.lastNode().equals(toAdd.lastNode())) {
144            // old ->|<- new, we need to reverse new
145            final List<N> toAddNodes = new ArrayList<>(toAdd.getNodes());
146            Collections.reverse(toAddNodes);
147            nodes.addAll(toAddNodes);
148        } else {
149            added = false;
150        }
151        if (added) {
152            // This is (technically) always correct
153            old.setNodes(nodes);
154        }
155        return added;
156    }
157
158    private synchronized <T extends Tile & VectorTile> VectorNode pointToNode(T tile, Layer layer,
159      Collection<VectorPrimitive> featureObjects, int x, int y) {
160        final BBox tileBbox;
161        if (tile instanceof IQuadBucketType) {
162            tileBbox = ((IQuadBucketType) tile).getBBox();
163        } else {
164            final ICoordinate upperLeft = tile.getTileSource().tileXYToLatLon(tile);
165            final ICoordinate lowerRight = tile.getTileSource()
166                    .tileXYToLatLon(tile.getXtile() + 1, tile.getYtile() + 1, tile.getZoom());
167
168            tileBbox = new BBox(upperLeft.getLon(), upperLeft.getLat(), lowerRight.getLon(), lowerRight.getLat());
169        }
170        final int layerExtent = layer.getExtent();
171        final ICoordinate coords = new Coordinate(
172                tileBbox.getMaxLat() - (tileBbox.getMaxLat() - tileBbox.getMinLat()) * y / layerExtent,
173                tileBbox.getMinLon() + (tileBbox.getMaxLon() - tileBbox.getMinLon()) * x / layerExtent
174        );
175        final Collection<VectorNode> nodes = this.store
176          .searchNodes(new BBox(coords.getLon(), coords.getLat(), VectorDataSet.DUPE_NODE_DISTANCE));
177        final VectorNode node;
178        if (!nodes.isEmpty()) {
179            final VectorNode first = nodes.iterator().next();
180            if (first.isDisabled() || !first.isVisible()) {
181                // Only replace nodes that are not visible
182                node = new VectorNode(layer.getName());
183                node.setCoor(node.getCoor());
184                first.getReferrers(true).forEach(primitive -> {
185                    if (primitive instanceof VectorWay) {
186                        List<VectorNode> nodeList = new ArrayList<>(((VectorWay) primitive).getNodes());
187                        nodeList.replaceAll(vnode -> vnode.equals(first) ? node : vnode);
188                        ((VectorWay) primitive).setNodes(nodeList);
189                    } else if (primitive instanceof VectorRelation) {
190                        List<VectorRelationMember> members = new ArrayList<>(((VectorRelation) primitive).getMembers());
191                        members.replaceAll(member ->
192                          member.getMember().equals(first) ? new VectorRelationMember(member.getRole(), node) : member);
193                        ((VectorRelation) primitive).setMembers(members);
194                    }
195                });
196                this.removePrimitive(first);
197            } else {
198                node = first;
199            }
200        } else {
201            node = new VectorNode(layer.getName());
202        }
203        node.setCoor(coords);
204        featureObjects.add(node);
205        return node;
206    }
207
208    private <T extends Tile & VectorTile> List<VectorWay> pathToWay(T tile, Layer layer,
209      Collection<VectorPrimitive> featureObjects, Path2D shape) {
210        final PathIterator pathIterator = shape.getPathIterator(null);
211        final List<VectorWay> ways = pathIteratorToObjects(tile, layer, featureObjects, pathIterator).stream()
212          .filter(VectorWay.class::isInstance).map(VectorWay.class::cast).collect(toList());
213        // These nodes technically do not exist, so we shouldn't show them
214        ways.stream().flatMap(way -> way.getNodes().stream())
215          .filter(prim -> !prim.isTagged() && prim.getReferrers(true).size() == 1 && prim.getId() <= 0)
216          .forEach(prim -> {
217              prim.setDisabled(true);
218              prim.setVisible(false);
219          });
220        return ways;
221    }
222
223    private <T extends Tile & VectorTile> List<VectorPrimitive> pathIteratorToObjects(T tile, Layer layer,
224      Collection<VectorPrimitive> featureObjects, PathIterator pathIterator) {
225        final List<VectorNode> nodes = new ArrayList<>();
226        final double[] coords = new double[6];
227        final List<VectorPrimitive> ways = new ArrayList<>();
228        do {
229            final int type = pathIterator.currentSegment(coords);
230            pathIterator.next();
231            if ((PathIterator.SEG_MOVETO == type || PathIterator.SEG_CLOSE == type) && !nodes.isEmpty()) {
232                if (PathIterator.SEG_CLOSE == type) {
233                    nodes.add(nodes.get(0));
234                }
235                // New line
236                if (!nodes.isEmpty()) {
237                    final VectorWay way = new VectorWay(layer.getName());
238                    way.setNodes(nodes);
239                    featureObjects.add(way);
240                    ways.add(way);
241                }
242                nodes.clear();
243            }
244            if (PathIterator.SEG_MOVETO == type || PathIterator.SEG_LINETO == type) {
245                final VectorNode node = pointToNode(tile, layer, featureObjects, (int) coords[0], (int) coords[1]);
246                nodes.add(node);
247            } else if (PathIterator.SEG_CLOSE != type) {
248                // Vector Tiles only have MoveTo, LineTo, and ClosePath. Anything else is not supported at this time.
249                throw new UnsupportedOperationException();
250            }
251        } while (!pathIterator.isDone());
252        if (!nodes.isEmpty()) {
253            final VectorWay way = new VectorWay(layer.getName());
254            way.setNodes(nodes);
255            featureObjects.add(way);
256            ways.add(way);
257        }
258        return ways;
259    }
260
261    private <T extends Tile & VectorTile> VectorRelation areaToRelation(T tile, Layer layer,
262      Collection<VectorPrimitive> featureObjects, Area area) {
263        VectorRelation vectorRelation = new VectorRelation(layer.getName());
264        for (VectorPrimitive member : pathIteratorToObjects(tile, layer, featureObjects, area.getPathIterator(null))) {
265            final String role;
266            if (member instanceof VectorWay && ((VectorWay) member).isClosed()) {
267                role = Geometry.isClockwise(((VectorWay) member).getNodes()) ? "outer" : "inner";
268            } else {
269                role = "";
270            }
271            vectorRelation.addRelationMember(new VectorRelationMember(role, member));
272        }
273        return vectorRelation;
274    }
275
276    /**
277     * Add the information from a tile to this object
278     * @param tile The tile to add
279     * @param <T> The tile type
280     */
281    public <T extends Tile & VectorTile> void addDataTile(T tile) {
282        for (Layer layer : tile.getLayers()) {
283            for (Feature feature : layer.getFeatures()) {
284                try {
285                    addFeatureData(tile, layer, feature);
286                } catch (IllegalArgumentException e) {
287                    Logging.error("Cannot add vector data for feature {0} of tile {1}: {2}", feature, tile, e.getMessage());
288                    Logging.error(e);
289                }
290            }
291        }
292        // Replace original_ids with the same object (reduce memory usage)
293        // Strings aren't interned automatically in some GC implementations
294        Collection<IPrimitive> primitives = this.getAllPrimitives().stream().filter(p -> p.hasKey(ORIGINAL_ID)).collect(toList());
295        List<String> toReplace = primitives.stream().map(p -> p.get(ORIGINAL_ID)).filter(Objects::nonNull).collect(toList());
296        primitives.stream().filter(p -> toReplace.contains(p.get(ORIGINAL_ID)))
297                .forEach(p -> p.put(ORIGINAL_ID, toReplace.stream().filter(shared -> shared.equals(p.get(ORIGINAL_ID)))
298                        .findAny().orElse(null)));
299    }
300
301    private <T extends Tile & VectorTile> void addFeatureData(T tile, Layer layer, Feature feature) {
302        List<VectorPrimitive> featureObjects = new ArrayList<>();
303        List<VectorPrimitive> primaryFeatureObjects = feature.getGeometryObject().getShapes().stream()
304                .map(shape -> shapeToPrimaryFeatureObject(tile, layer, shape, featureObjects)).collect(toList());
305        final VectorPrimitive primitive;
306        if (primaryFeatureObjects.size() == 1) {
307            primitive = primaryFeatureObjects.get(0);
308            if (primitive instanceof IRelation && !primitive.isMultipolygon()) {
309                primitive.put(JOSM_MERGE_TYPE_KEY, "merge");
310            }
311        } else if (!primaryFeatureObjects.isEmpty()) {
312            VectorRelation relation = new VectorRelation(layer.getName());
313            primaryFeatureObjects.stream().map(prim -> new VectorRelationMember("", prim))
314              .forEach(relation::addRelationMember);
315            primitive = relation;
316        } else {
317            return;
318        }
319        primitive.setId(feature.getId());
320        // Version 1 <i>and</i> 2 <i>do not guarantee</i> that non-zero ids are unique
321        // We depend upon unique ids in the data store
322        if (feature.getId() != 0 && this.primitivesMap.containsKey(primitive.getPrimitiveId())) {
323            // This, unfortunately, makes a new string
324            primitive.put(ORIGINAL_ID, Long.toString(feature.getId()));
325            primitive.setId(primitive.getIdGenerator().generateUniqueId());
326        }
327        if (feature.getTags() != null) {
328            feature.getTags().forEach(primitive::put);
329        }
330        featureObjects.forEach(this::addPrimitive);
331        primaryFeatureObjects.forEach(this::addPrimitive);
332        try {
333            this.addPrimitive(primitive);
334        } catch (JosmRuntimeException e) {
335            Logging.error("{0}/{1}/{2}: {3}", tile.getZoom(), tile.getXtile(), tile.getYtile(), primitive.get("key"));
336            throw e;
337        }
338    }
339
340    private <T extends Tile & VectorTile> VectorPrimitive shapeToPrimaryFeatureObject(
341            T tile, Layer layer, Shape shape, List<VectorPrimitive> featureObjects) {
342        final VectorPrimitive primitive;
343        if (shape instanceof Ellipse2D) {
344            primitive = pointToNode(tile, layer, featureObjects,
345                    (int) ((Ellipse2D) shape).getCenterX(), (int) ((Ellipse2D) shape).getCenterY());
346        } else if (shape instanceof Path2D) {
347            primitive = pathToWay(tile, layer, featureObjects, (Path2D) shape).stream().findFirst().orElse(null);
348        } else if (shape instanceof Area) {
349            primitive = areaToRelation(tile, layer, featureObjects, (Area) shape);
350            primitive.put(RELATION_TYPE, MULTIPOLYGON_TYPE);
351        } else {
352            // We shouldn't hit this, but just in case
353            throw new UnsupportedOperationException(Objects.toString(shape));
354        }
355        return primitive;
356    }
357
358    @Override
359    public void destroy() {
360        this.addedTiles.forEach(tile -> tile.setLoaded(false));
361        this.addedTiles.forEach(tile -> tile.setImage(null));
362        this.addedTiles.clear();
363        this.store.clear();
364        this.allPrimitives.clear();
365        this.primitivesMap.clear();
366    }
367}