001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm;
003
004import java.awt.geom.Rectangle2D;
005import java.util.Objects;
006
007import org.openstreetmap.josm.data.Bounds;
008import org.openstreetmap.josm.data.IBounds;
009import org.openstreetmap.josm.data.coor.ILatLon;
010import org.openstreetmap.josm.data.coor.LatLon;
011import org.openstreetmap.josm.data.coor.QuadTiling;
012
013/**
014 * A BBox represents an area in lat/lon space. It is used for the quad tree.
015 *
016 * In contrast to a {@link Bounds} object, a BBox can represent an invalid (empty) area.
017 */
018public class BBox implements IBounds {
019
020    protected double xmin = Double.POSITIVE_INFINITY;
021    protected double xmax = Double.NEGATIVE_INFINITY;
022    protected double ymin = Double.POSITIVE_INFINITY;
023    protected double ymax = Double.NEGATIVE_INFINITY;
024
025    /**
026     * Constructs a new (invalid) BBox
027     */
028    public BBox() {
029        // Nothing to do
030    }
031
032    /**
033     * Constructs a new {@code BBox} defined by a single point.
034     *
035     * @param x X coordinate
036     * @param y Y coordinate
037     * @since 6203
038     */
039    public BBox(final double x, final double y) {
040        add(x, y);
041    }
042
043    /**
044     * Constructs a new {@code BBox} defined by points <code>a</code> and <code>b</code>.
045     * Result is minimal BBox containing both points if they are both valid, else undefined
046     *
047     * @param a first point
048     * @param b second point
049     */
050    public BBox(LatLon a, LatLon b) {
051        this(a.lon(), a.lat(), b.lon(), b.lat());
052    }
053
054    /**
055     * Constructs a new {@code BBox} from another one.
056     *
057     * @param copy the BBox to copy
058     */
059    public BBox(BBox copy) {
060        this.xmin = copy.xmin;
061        this.xmax = copy.xmax;
062        this.ymin = copy.ymin;
063        this.ymax = copy.ymax;
064    }
065
066    /**
067     * Creates bbox around the coordinate (x, y).
068     * Coordinate defines center of bbox, its edge will be 2*r.
069     *
070     * @param x X coordinate
071     * @param y Y coordinate
072     * @param r size
073     * @since 13140
074     */
075    public BBox(double x, double y, double r) {
076        this(x - r, y - r, x + r, y + r);
077    }
078
079    /**
080     * Create minimal BBox so that {@code this.bounds(ax,ay)} and {@code this.bounds(bx,by)} will both return true
081     * @param ax left or right X value (-180 .. 180)
082     * @param ay top or bottom Y value (-90 .. 90)
083     * @param bx left or right X value (-180 .. 180)
084     * @param by top or bottom Y value (-90 .. 90)
085     */
086    public BBox(double ax, double ay, double bx, double by) {
087        if (!(Double.isNaN(ax) || Double.isNaN(ay) || Double.isNaN(bx) || Double.isNaN(by))) {
088            add(ax, ay);
089            add(bx, by);
090        }
091        // otherwise use default which is an invalid BBox
092    }
093
094    /**
095     * Create BBox for all nodes of the way with known coordinates.
096     * If no node has a known coordinate, an invalid BBox is returned.
097     * @param w the way
098     */
099    public BBox(IWay<?> w) {
100        for (INode ll : w.getNodes()) {
101            add(ll);
102        }
103    }
104
105    /**
106     * Create BBox for a node. An invalid BBox is returned if the coordinates are not known.
107     * @param n the node
108     */
109    public BBox(INode n) {
110        this((ILatLon) n);
111    }
112
113    /**
114     * Create BBox for a given latlon. An invalid BBox is returned if the coordinates are not known.
115     * @param ll The lat lon position
116     */
117    public BBox(ILatLon ll) {
118        add(ll);
119    }
120
121    /**
122     * Add a point to an existing BBox. Extends this bbox if necessary so that this.bounds(c) will return true
123     * if c is a valid LatLon instance.
124     * Kept for binary compatibility
125     * @param c a LatLon point
126     */
127    public final void add(LatLon c) {
128        add((ILatLon) c);
129    }
130
131    /**
132     * Add a point to an existing BBox. Extends this bbox if necessary so that this.bounds(c) will return true
133     * if c is a valid LatLon instance.
134     * If it is invalid or <code>null</code>, this call is ignored.
135     * @param c a LatLon point.
136     */
137    public final void add(ILatLon c) {
138        if (c != null) {
139            add(c.lon(), c.lat());
140        }
141    }
142
143    /**
144     * Extends this bbox to include the point (x, y)
145     * @param x X coordinate
146     * @param y Y coordinate
147     */
148    public final void add(double x, double y) {
149        if (!Double.isNaN(x) && !Double.isNaN(y)) {
150            set(Math.min(xmin, x), Math.max(xmax, x), Math.min(ymin, y), Math.max(ymax, y));
151        }
152    }
153
154    /**
155     * Extends this bbox to include the bbox other. Does nothing if other is not valid.
156     * @param other a bbox
157     */
158    public final void add(BBox other) {
159        if (other.isValid()) {
160            set(Math.min(xmin, other.xmin), Math.max(xmax, other.xmax), Math.min(ymin, other.ymin), Math.max(ymax, other.ymax));
161        }
162    }
163
164    protected void set(double xmin, double xmax, double ymin, double ymax) {
165        this.xmin = xmin;
166        this.xmax = xmax;
167        this.ymin = ymin;
168        this.ymax = ymax;
169    }
170
171    /**
172     * Extends this bbox to include the bbox of the primitive extended by extraSpace.
173     * @param primitive an OSM primitive
174     * @param extraSpace the value to extend the primitives bbox. Unit is in LatLon degrees.
175     */
176    public void addPrimitive(OsmPrimitive primitive, double extraSpace) {
177        this.addPrimitive((IPrimitive) primitive, extraSpace);
178    }
179
180    /**
181     * Extends this bbox to include the bbox of the primitive extended by extraSpace.
182     * @param primitive an primitive
183     * @param extraSpace the value to extend the primitives bbox. Unit is in LatLon degrees.
184     * @since 17862
185     */
186    public void addPrimitive(IPrimitive primitive, double extraSpace) {
187        IBounds primBbox = primitive.getBBox();
188        add(primBbox.getMinLon() - extraSpace, primBbox.getMinLat() - extraSpace);
189        add(primBbox.getMaxLon() + extraSpace, primBbox.getMaxLat() + extraSpace);
190    }
191
192    /**
193     * Extends this bbox to include the bbox of the primitive extended by extraSpace.
194     * @param latLon a LatLon
195     * @param extraSpace the value to extend the primitives bbox. Unit is in LatLon degrees.
196     * @since 15877
197     */
198    public void addLatLon(LatLon latLon, double extraSpace) {
199        Objects.requireNonNull(latLon, "LatLon cannot be null");
200        add(latLon);
201        add(latLon.getX() - extraSpace, latLon.getY() - extraSpace);
202        add(latLon.getX() + extraSpace, latLon.getY() + extraSpace);
203    }
204
205    /**
206     * Gets the height of the bbox.
207     * @return The difference between ymax and ymin. 0 for invalid bboxes.
208     */
209    public double height() {
210        return getHeight();
211    }
212
213    @Override
214    public double getHeight() {
215        if (isValid()) {
216            return ymax - ymin;
217        } else {
218            return 0;
219        }
220    }
221
222    /**
223     * Gets the width of the bbox.
224     * @return The difference between xmax and xmin. 0 for invalid bboxes.
225     */
226    public double width() {
227        return getWidth();
228    }
229
230    @Override
231    public double getWidth() {
232        if (isValid()) {
233            return xmax - xmin;
234        } else {
235            return 0;
236        }
237    }
238
239    /**
240     * Gets the area of the bbox.
241     * @return the area computed from {@link #width()} and {@link #height()}
242     */
243    public double area() {
244        return width() * height();
245    }
246
247    /**
248     * Tests, whether the bbox {@code b} lies completely inside this bbox.
249     * @param b bounding box
250     * @return {@code true} if {@code b} lies completely inside this bbox
251     */
252    public boolean bounds(BBox b) {
253        return contains(b);
254    }
255
256    /**
257     * Tests, whether the Point {@code c} lies within the bbox.
258     * @param c point
259     * @return {@code true} if {@code c} lies within the bbox
260     */
261    public boolean bounds(LatLon c) {
262        return contains(c);
263    }
264
265    /**
266     * Tests, whether two BBoxes intersect as an area.
267     * I.e. whether there exists a point that lies in both of them.
268     * @param b other bounding box
269     * @return {@code true} if this bbox intersects with the other
270     */
271    public boolean intersects(BBox b) {
272        return intersects((IBounds) b);
273    }
274
275    /**
276     * Returns the top-left point.
277     * @return The top-left point
278     */
279    public LatLon getTopLeft() {
280        return new LatLon(ymax, xmin);
281    }
282
283    /**
284     * Returns the latitude of top-left point.
285     * @return The latitude of top-left point
286     * @since 6203
287     */
288    public double getTopLeftLat() {
289        return getMaxLat();
290    }
291
292    @Override
293    public double getMaxLat() {
294        return ymax;
295    }
296
297    /**
298     * Returns the longitude of top-left point.
299     * @return The longitude of top-left point
300     * @since 6203
301     */
302    public double getTopLeftLon() {
303        return getMinLon();
304    }
305
306    @Override
307    public double getMinLon() {
308        return xmin;
309    }
310
311    /**
312     * Returns the bottom-right point.
313     * @return The bottom-right point
314     */
315    public LatLon getBottomRight() {
316        return new LatLon(ymin, xmax);
317    }
318
319    /**
320     * Returns the latitude of bottom-right point.
321     * @return The latitude of bottom-right point
322     * @since 6203
323     */
324    public double getBottomRightLat() {
325        return getMinLat();
326    }
327
328    @Override
329    public double getMinLat() {
330        return ymin;
331    }
332
333    /**
334     * Returns the longitude of bottom-right point.
335     * @return The longitude of bottom-right point
336     * @since 6203
337     */
338    public double getBottomRightLon() {
339        return getMaxLon();
340    }
341
342    @Override
343    public double getMaxLon() {
344        return xmax;
345    }
346
347    /**
348     * Gets the center of this BBox.
349     * @return The center.
350     */
351    @Override
352    public LatLon getCenter() {
353        return new LatLon(ymin + (ymax-ymin)/2.0, xmin + (xmax-xmin)/2.0);
354    }
355
356    byte getIndex(final int level) {
357
358        byte idx1 = QuadTiling.index(ymin, xmin, level);
359
360        final byte idx2 = QuadTiling.index(ymin, xmax, level);
361        if (idx1 == -1) idx1 = idx2;
362        else if (idx1 != idx2) return -1;
363
364        final byte idx3 = QuadTiling.index(ymax, xmin, level);
365        if (idx1 == -1) idx1 = idx3;
366        else if (idx1 != idx3) return -1;
367
368        final byte idx4 = QuadTiling.index(ymax, xmax, level);
369        if (idx1 == -1) idx1 = idx4;
370        else if (idx1 != idx4) return -1;
371
372        return idx1;
373    }
374
375    /**
376     * Converts the bounds to a rectangle
377     * @return The rectangle in east/north space.
378     */
379    public Rectangle2D toRectangle() {
380        return new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin);
381    }
382
383    @Override
384    public final int hashCode() {
385        return Objects.hash(xmin, xmax, ymin, ymax);
386    }
387
388    @Override
389    public final boolean equals(Object o) {
390        if (this == o) return true;
391        if (!(o instanceof BBox)) return false;
392        BBox b = (BBox) o;
393        return Double.compare(b.xmax, xmax) == 0 && Double.compare(b.ymax, ymax) == 0
394            && Double.compare(b.xmin, xmin) == 0 && Double.compare(b.ymin, ymin) == 0;
395    }
396
397    /**
398     * Check if bboxes are functionally equal
399     * @param other The other bbox to compare with
400     * @param maxDifference The maximum difference (in degrees) between the bboxes. May be null.
401     * @return true if they are functionally equivalent
402     * @since 15486
403     */
404    public boolean bboxIsFunctionallyEqual(BBox other, Double maxDifference) {
405        return bboxesAreFunctionallyEqual(this, other, maxDifference);
406    }
407
408    /**
409     * Check if bboxes are functionally equal
410     * @param bbox1 A bbox to compare with another bbox
411     * @param bbox2 The other bbox to compare with
412     * @param maxDifference The maximum difference (in degrees) between the bboxes. May be null.
413     * @return true if they are functionally equivalent
414     * @since 15483
415     */
416    public static boolean bboxesAreFunctionallyEqual(BBox bbox1, BBox bbox2, Double maxDifference) {
417        if (maxDifference == null) {
418            maxDifference = LatLon.MAX_SERVER_PRECISION;
419        }
420        return (bbox1 != null && bbox2 != null)
421                && (Math.abs(bbox1.getBottomRightLat() - bbox2.getBottomRightLat()) <= maxDifference
422                        && Math.abs(bbox1.getBottomRightLon() - bbox2.getBottomRightLon()) <= maxDifference
423                        && Math.abs(bbox1.getTopLeftLat() - bbox2.getTopLeftLat()) <= maxDifference
424                        && Math.abs(bbox1.getTopLeftLon() - bbox2.getTopLeftLon()) <= maxDifference);
425    }
426
427    /**
428     * Determines if the bbox covers a part of the planet surface.
429     * @return true if the bbox covers a part of the planet surface.
430     * Height and width must be non-negative, but may (both) be 0.
431     * @since 11269
432     */
433    @Override
434    public boolean isValid() {
435        return xmin <= xmax && ymin <= ymax;
436    }
437
438    /**
439     * Determines if the bbox is valid and covers a part of the planet surface.
440     * @return true if the bbox is valid and covers a part of the planet surface
441     * @since 11269
442     */
443    public boolean isInWorld() {
444        return xmin >= -180.0 && xmax <= 180.0 && ymin >= -90.0 && ymax <= 90.0 && isValid();
445    }
446
447    @Override
448    public String toString() {
449        return "[ x: " + xmin + " -> " + xmax + ", y: " + ymin + " -> " + ymax + " ]";
450    }
451
452    /**
453     * Creates a CSV string for this bbox
454     * @param separator The separator to use
455     * @return A string
456     */
457    public String toStringCSV(String separator) {
458        return String.join(separator,
459                LatLon.cDdFormatter.format(xmin),
460                LatLon.cDdFormatter.format(ymin),
461                LatLon.cDdFormatter.format(xmax),
462                LatLon.cDdFormatter.format(ymax));
463    }
464
465    /**
466     * Returns an immutable version of this bbox, i.e., modifying calls throw an {@link UnsupportedOperationException}.
467     * @return an immutable version of this bbox
468     * @since 17862 (interface)
469     */
470    public BBox toImmutable() {
471        return new Immutable(this);
472    }
473
474    private static class Immutable extends BBox {
475
476        Immutable(BBox copy) {
477            super(copy);
478        }
479
480        @Override
481        protected void set(double xmin, double xmax, double ymin, double ymax) {
482            throw new UnsupportedOperationException();
483        }
484
485        @Override
486        public BBox toImmutable() {
487            return this;
488        }
489    }
490}