001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.imagery.vectortile.mapbox;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.awt.Shape;
007import java.awt.geom.Area;
008import java.awt.geom.Ellipse2D;
009import java.awt.geom.Path2D;
010import java.util.ArrayList;
011import java.util.Collection;
012import java.util.Collections;
013import java.util.List;
014
015/**
016 * A class to generate geometry for a vector tile
017 * @author Taylor Smock
018 * @since 17862
019 */
020public class Geometry {
021    final Collection<Shape> shapes;
022
023    /**
024     * Create a {@link Geometry} for a {@link Feature}
025     * @param geometryType The type of geometry
026     * @param commands The commands used to create the geometry
027     * @throws IllegalArgumentException if arguments are not understood or if the shoelace formula returns 0 for a polygon ring.
028     */
029    public Geometry(GeometryTypes geometryType, List<CommandInteger> commands) {
030        if (geometryType == GeometryTypes.POINT) {
031            // This gets rid of most of the expensive array copies from ArrayList#grow
032            shapes = new ArrayList<>(commands.size());
033            initializePoints(geometryType, commands);
034        } else if (geometryType == GeometryTypes.LINESTRING || geometryType == GeometryTypes.POLYGON) {
035            // This gets rid of most of the expensive array copies from ArrayList#grow
036            shapes = new ArrayList<>(1);
037            initializeWayGeometry(geometryType, commands);
038        } else {
039            shapes = Collections.emptyList();
040        }
041    }
042
043    /**
044     * Initialize point geometry
045     * @param geometryType The geometry type (used for logging)
046     * @param commands The commands to use to create the geometry
047     */
048    private void initializePoints(GeometryTypes geometryType, List<CommandInteger> commands) {
049        for (CommandInteger command : commands) {
050            final short[] operations = command.getOperations();
051            // Each MoveTo command is a new point
052            if (command.getType() == Command.MoveTo && operations.length % 2 == 0 && operations.length > 0) {
053                for (int i = 0; i < operations.length / 2; i++) {
054                    // Just using Ellipse2D since it extends Shape
055                    shapes.add(new Ellipse2D.Float(operations[2 * i], operations[2 * i + 1], 0, 0));
056                }
057            } else {
058                throw new IllegalArgumentException(tr("{0} with {1} arguments is not understood", geometryType, operations.length));
059            }
060        }
061    }
062
063    /**
064     * Initialize way geometry
065     * @param geometryType The geometry type
066     * @param commands The commands to use to create the geometry
067     */
068    private void initializeWayGeometry(GeometryTypes geometryType, List<CommandInteger> commands) {
069        Path2D.Float line = null;
070        Area area = null;
071        // MVT uses delta encoding. Each feature starts at (0, 0).
072        int x = 0;
073        int y = 0;
074        // Area is used to determine the inner/outer of a polygon
075        final int maxArraySize = commands.stream().filter(command -> command.getType() != Command.ClosePath)
076                .mapToInt(command -> command.getOperations().length).sum();
077        final List<Integer> xArray = new ArrayList<>(maxArraySize);
078        final List<Integer> yArray = new ArrayList<>(maxArraySize);
079        for (CommandInteger command : commands) {
080            final short[] operations = command.getOperations();
081            // Technically, there is no reason why there can be multiple MoveTo operations in one command, but that is undefined behavior
082            if (command.getType() == Command.MoveTo && operations.length == 2) {
083                x += operations[0];
084                y += operations[1];
085                // Avoid fairly expensive Arrays.copyOf calls
086                line = new Path2D.Float(Path2D.WIND_NON_ZERO, commands.size());
087                line.moveTo(x, y);
088                xArray.add(x);
089                yArray.add(y);
090                shapes.add(line);
091            } else if (command.getType() == Command.LineTo && operations.length % 2 == 0 && line != null) {
092                for (int i = 0; i < operations.length / 2; i++) {
093                    x += operations[2 * i];
094                    y += operations[2 * i + 1];
095                    xArray.add(x);
096                    yArray.add(y);
097                    line.lineTo(x, y);
098                }
099                // ClosePath should only be used with Polygon geometry
100            } else if (geometryType == GeometryTypes.POLYGON && command.getType() == Command.ClosePath && line != null) {
101                shapes.remove(line);
102                // new Area() closes the line if it isn't already closed
103                if (area == null) {
104                    area = new Area();
105                    shapes.add(area);
106                }
107
108                final double areaAreaSq = calculateSurveyorsArea(xArray.stream().mapToInt(i -> i).toArray(),
109                        yArray.stream().mapToInt(i -> i).toArray());
110                Area nArea = new Area(line);
111                // SonarLint thinks that this is never > 0. It can be.
112                if (areaAreaSq > 0) {
113                    area.add(nArea);
114                } else if (areaAreaSq < 0) {
115                    area.exclusiveOr(nArea);
116                } else {
117                    throw new IllegalArgumentException(tr("{0} cannot have zero area", geometryType));
118                }
119                xArray.clear();
120                yArray.clear();
121            } else {
122                throw new IllegalArgumentException(tr("{0} with {1} arguments is not understood", geometryType, operations.length));
123            }
124        }
125    }
126
127    /**
128     * This is also known as the "shoelace formula".
129     * @param xArray The array of x coordinates
130     * @param yArray The array of y coordinates
131     * @return The area of the object
132     * @throws IllegalArgumentException if the array lengths are not equal
133     */
134    static double calculateSurveyorsArea(int[] xArray, int[] yArray) {
135        if (xArray.length != yArray.length) {
136            throw new IllegalArgumentException("Cannot calculate areas when arrays are uneven");
137        }
138        // Lines have no area
139        if (xArray.length < 3) {
140            return 0;
141        }
142        int area = 0;
143        // Do the non-special stuff first (x0 * y1 - x1 * y0)
144        for (int i = 0; i < xArray.length - 1; i++) {
145            area += xArray[i] * yArray[i + 1] - xArray[i + 1] * yArray[i];
146        }
147        // Now calculate the edges (xn * y0 - x0 * yn)
148        area += xArray[xArray.length - 1] * yArray[0] - xArray[0] * yArray[yArray.length - 1];
149        return area / 2d;
150    }
151
152    /**
153     * Get the shapes to draw this geometry with
154     * @return A collection of shapes
155     */
156    public Collection<Shape> getShapes() {
157        return Collections.unmodifiableCollection(this.shapes);
158    }
159}