001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.imagery;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.awt.Polygon;
007import java.text.MessageFormat;
008import java.util.AbstractList;
009import java.util.List;
010import java.util.stream.Collectors;
011
012import org.openstreetmap.gui.jmapviewer.Coordinate;
013import org.openstreetmap.josm.data.coor.LatLon;
014import org.openstreetmap.josm.tools.CheckParameterUtil;
015
016/**
017 * Data class to store the outline for background imagery coverage.
018 *
019 * Configuration data for imagery to describe the coverage area ({@link ImageryInfo.ImageryBounds}).
020 * @author Vincent
021 */
022public class Shape {
023
024    private final Polygon coords;
025
026    public Shape(String asString, String separator) {
027        CheckParameterUtil.ensureParameterNotNull(asString, "asString");
028        String[] components = asString.split(separator, -1);
029        if (components.length % 2 != 0)
030            throw new IllegalArgumentException(MessageFormat.format("Even number of doubles expected in string, got {0}: {1}",
031                    components.length, asString));
032        int size = components.length / 2;
033        this.coords = new Polygon(new int[size], new int[size], 0);
034        for (int i = 0; i < components.length; i += 2) {
035            addPoint(components[i], components[i+1]);
036        }
037    }
038
039    /**
040     * Constructs a new empty {@code Shape}.
041     */
042    public Shape() {
043        coords = new Polygon();
044        // shape contents can be set later with addPoint()
045    }
046
047    /**
048     * Encodes this as a string so that it may be parsed using {@link #Shape(String, String)}
049     * @param separator The separator
050     * @return The string encoded shape
051     */
052    public String encodeAsString(String separator) {
053        return getPoints().stream()
054                .map(c -> c.getLat() + separator + c.getLon())
055                .collect(Collectors.joining(separator));
056    }
057
058    /**
059     * Encodes the shapes as a string using {@code ,} and {@code ;} as separators
060     * @param shapes The shapes to encode
061     * @return The string encoded shapes
062     */
063    public static String encodeAsString(List<Shape> shapes) {
064        return shapes.stream()
065                .map(s -> s.encodeAsString(","))
066                .collect(Collectors.joining(";"));
067    }
068
069    public List<Coordinate> getPoints() {
070        return new CoordinateList(this.coords);
071    }
072
073    /**
074     * Check if the coordinates are inside this shape.
075     * @param latlon The latlon to look for
076     * @return {@code true} if the LatLon is inside the shape.
077     * @see Polygon#contains(int, int)
078     */
079    public boolean contains(LatLon latlon) {
080        return coords.contains(
081                latlon.getX() * LatLon.MAX_SERVER_INV_PRECISION,
082                latlon.getY() * LatLon.MAX_SERVER_INV_PRECISION);
083    }
084
085    public void addPoint(String sLat, String sLon) {
086        CheckParameterUtil.ensureParameterNotNull(sLat, "sLat");
087        CheckParameterUtil.ensureParameterNotNull(sLon, "sLon");
088
089        double lat, lon;
090
091        try {
092            lat = Double.parseDouble(sLat);
093            if (!LatLon.isValidLat(lat))
094                throw new IllegalArgumentException(tr("Illegal latitude value ''{0}''", lat));
095        } catch (NumberFormatException e) {
096            throw new IllegalArgumentException(MessageFormat.format("Illegal double value ''{0}''", sLat), e);
097        }
098
099        try {
100            lon = Double.parseDouble(sLon);
101            if (!LatLon.isValidLon(lon))
102                throw new IllegalArgumentException(tr("Illegal longitude value ''{0}''", lon));
103        } catch (NumberFormatException e) {
104            throw new IllegalArgumentException(MessageFormat.format("Illegal double value ''{0}''", sLon), e);
105        }
106
107        coords.addPoint(
108                (int) Math.round((lon * LatLon.MAX_SERVER_INV_PRECISION)),
109                (int) Math.round((lat * LatLon.MAX_SERVER_INV_PRECISION)));
110    }
111
112    @Override
113    public int hashCode() {
114        // This was Objects.hash(getPoints()), but that made 8-24MB of allocations on application startup
115        return 31 + hashPolygon(this.coords); // Arrays#hash, new array instantiation
116    }
117
118    @Override
119    public boolean equals(Object obj) {
120        if (this == obj) return true;
121        if (obj == null || getClass() != obj.getClass()) return false;
122        Shape shape = (Shape) obj;
123        return equalsPolygon(this.coords, shape.coords);
124    }
125
126    @Override
127    public String toString() {
128        return "Shape{coords=" + getPoints() + '}';
129    }
130
131    /**
132     * Hash a polygon
133     * @param coords The polygon to hash
134     * @return The hashcode to use; equivalent to {@link Polygon#hashCode()}, but zero allocations.
135     */
136    private static int hashPolygon(Polygon coords) {
137        // This is faster than coords.hashCode() by ~90% and performs effectively no memory allocations.
138        // This was originally written to replace Objects.hash(getPoints()). The only difference is +31 on the return.
139        // Objects.hash(getPoints()) -> Arrays.hash(getPoints()) -> sum of hashes of Coordinates
140        // First, AbstractList#hashCode equivalent
141        int hashCode = 1;
142        for (int index = 0; index < coords.npoints; index++) {
143            final double lat = coords.ypoints[index] / LatLon.MAX_SERVER_INV_PRECISION;
144            final double lon = coords.xpoints[index] / LatLon.MAX_SERVER_INV_PRECISION;
145            // Coordinate uses Object.hash(x, y) - new array instantiation *and* two Double instantiations
146            // Double conversion is 3.22MB
147            // The array creation for Object.hash(x, y) is 2.11 MB
148            final int coordinateHash = 31 * (31 + Double.hashCode(lon)) + Double.hashCode(lat);
149            hashCode = 31 * hashCode + coordinateHash; // hashCode * 31 + coordinate.hashCode()
150        }
151        return hashCode;
152    }
153
154    /**
155     * Check that two {@link Polygon}s are equal
156     * @param first The first polygon to check
157     * @param second The second polygon to check
158     * @return {@code true} if the polygons are equal
159     */
160    private static boolean equalsPolygon(Polygon first, Polygon second) {
161        // If the coordinate lists aren't the same size, short circuit.
162        // We aren't doing fuzzy comparisons here.
163        if (first.npoints != second.npoints) {
164            return false;
165        }
166        for (int i = 0; i < first.npoints; i++) {
167            if (first.xpoints[i] != second.xpoints[i] ||
168                    first.ypoints[i] != second.ypoints[i]) {
169                return false;
170            }
171        }
172        return true;
173    }
174
175    /**
176     * A list of {@link Coordinate}s that attempts to be very efficient in terms of CPU time and memory allocations.
177     */
178    private static final class CoordinateList extends AbstractList<Coordinate> {
179        private final Polygon coords;
180
181        CoordinateList(Polygon coords) {
182            this.coords = coords;
183        }
184
185        @Override
186        public Coordinate get(int index) {
187            double lat = coords.ypoints[index] / LatLon.MAX_SERVER_INV_PRECISION;
188            double lon = coords.xpoints[index] / LatLon.MAX_SERVER_INV_PRECISION;
189            return new Coordinate(lat, lon);
190        }
191
192        @Override
193        public int size() {
194            return coords.npoints;
195        }
196
197        @Override
198        public boolean equals(Object o) {
199            if (o instanceof CoordinateList) {
200                CoordinateList other = (CoordinateList) o;
201                return equalsPolygon(this.coords, other.coords);
202            }
203            return super.equals(o);
204        }
205
206        @Override
207        public int hashCode() {
208            return hashPolygon(this.coords);
209        }
210    }
211}