Point.java

/*
 * Copyright (C) 2016-2021, Stichting Mapcode Foundation (http://www.mapcode.com)
 *
 * Licensed 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.
 */

package com.mapcode;

import javax.annotation.Nonnull;
import java.util.Arrays;
import java.util.Random;

import static com.mapcode.CheckArgs.checkNonnull;

/**
 * This class defines a class for lat/lon points.
 *
 * Internally, the class implements a fixed-point representation where a coordinate is expressed in
 * "fractions", of 1/3.240,000,000,000th of a degree. A double (an IEEE 754-1985 binary64) is just
 * sufficient to represent coordinates between -180 and +180 degrees in such fractions.
 * However, for applications that use micro-degrees a lot, the implementation below is more efficient.
 * It represent the fractions in pairs of integers, the first integer
 * representing 1/1,000,000th of degrees, the second representing the remainder.
 */
@SuppressWarnings("MagicNumber")
public final class Point {

    // Latitude and longitude ranges.
    @SuppressWarnings("unused")
    public static final double LON_DEG_MIN = -180.0;
    @SuppressWarnings("unused")
    public static final double LON_DEG_MAX = 180.0;
    @SuppressWarnings("unused")
    public static final double LAT_DEG_MIN = -90.0;
    @SuppressWarnings("unused")
    public static final double LAT_DEG_MAX = 90.0;

    // Conversion constants.
    public static final int DEG_TO_MICRO_DEG = 1000000;
    public static final int MICRO_DEG_90 = 90 * DEG_TO_MICRO_DEG;
    public static final int MICRO_DEG_180 = 180 * DEG_TO_MICRO_DEG;
    public static final int MICRO_DEG_360 = 360 * DEG_TO_MICRO_DEG;

    // Radius of Earth.
    public static final double EARTH_RADIUS_X_METERS = 6378137.0;
    public static final double EARTH_RADIUS_Y_METERS = 6356752.3;

    // Circumference of Earth.
    public static final double EARTH_CIRCUMFERENCE_X = EARTH_RADIUS_X_METERS * 2.0 * Math.PI;
    public static final double EARTH_CIRCUMFERENCE_Y = EARTH_RADIUS_Y_METERS * 2.0 * Math.PI;

    // Meters per degree latitude is fixed. For longitude: use factor * cos(midpoint of two degree latitudes).
    public static final double METERS_PER_DEGREE_LAT = EARTH_CIRCUMFERENCE_Y / 360.0;
    public static final double METERS_PER_DEGREE_LON_EQUATOR = EARTH_CIRCUMFERENCE_X / 360.0; // * cos(deg(lat)).

    /**
     * Create a point from lat/lon in degrees (may be precision!)
     *
     * @param latDeg Latitude in degrees. Range: [-90, 90].
     * @param lonDeg Longitude in degrees. Range: [-180, 180).
     * @return A defined point.
     */
    @Nonnull
    public static Point fromDeg(final double latDeg, final double lonDeg) {
        return new Point(latDeg, lonDeg);
    }

    /**
     * Public construction, from integer microdegrees (no loss of precision).
     *
     * @param latMicroDeg Latitude, in microdegrees.
     * @param lonMicroDeg Longitude, in microdegrees.
     * @return A defined point.
     */
    @Nonnull
    public static Point fromMicroDeg(final int latMicroDeg, final int lonMicroDeg) {
        final Point p = new Point();
        p.latMicroDeg = latMicroDeg;
        p.latFractionOnlyDeg = 0;
        p.lonMicroDeg = lonMicroDeg;
        p.lonFractionOnlyDeg = 0;
        p.defined = true;
        return p.wrap();
    }

    /**
     * Get the latitude in degrees (may lose precision).
     *
     * @return Latitude in degrees. No range is enforced.
     */
    public double getLatDeg() {
        assert defined;
        return (latMicroDeg / MICRODEG_TO_DEG_FACTOR) + (latFractionOnlyDeg / LAT_TO_FRACTIONS_FACTOR);
    }

    /**
     * Get the longitude in degrees (may lose precision).
     *
     * @return Longitude in degrees. No range is enforced.
     */
    public double getLonDeg() {
        assert defined;
        return (lonMicroDeg / MICRODEG_TO_DEG_FACTOR) + (lonFractionOnlyDeg / LON_TO_FRACTIONS_FACTOR);
    }

    /**
     * Get latitude as micro-degrees. Note that this looses precision beyond microdegrees!
     *
     * @return floor(Latitude in microdegrees)
     */
    public int getLatMicroDeg() {
        assert defined;
        return latMicroDeg;
    }

    /**
     * Get longitude as micro-degrees. Note that this looses precision beyond microdegrees!
     *
     * @return floor(Longitude in microdegrees)
     */
    public int getLonMicroDeg() {
        assert defined;
        return lonMicroDeg;
    }

    /**
     * Create a random point, uniformly distributed over the surface of the Earth.
     *
     * @param randomGenerator Random generator used to create a point.
     * @return Random point with uniform distribution over the sphere.
     */
    @Nonnull
    public static Point fromUniformlyDistributedRandomPoints(@Nonnull final Random randomGenerator) {
        checkNonnull("randomGenerator", randomGenerator);

        // Calculate uniformly distributed 3D point on sphere (radius = 1.0):
        // http://mathproofs.blogspot.co.il/2005/04/uniform-random-distribution-on-sphere.html
        final double unitRand1 = randomGenerator.nextDouble();
        final double unitRand2 = randomGenerator.nextDouble();
        final double theta0 = (2.0 * Math.PI) * unitRand1;
        final double theta1 = Math.acos(1.0 - (2.0 * unitRand2));
        final double x = Math.sin(theta0) * Math.sin(theta1);
        final double y = Math.cos(theta0) * Math.sin(theta1);
        final double z = Math.cos(theta1);

        // Convert Carthesian 3D point into lat/lon (radius = 1.0):
        // http://stackoverflow.com/questions/1185408/converting-from-longitude-latitude-to-cartesian-coordinates
        final double latRad = Math.asin(z);
        final double lonRad = Math.atan2(y, x);

        // Convert radians to degrees.
        assert !Double.isNaN(latRad);
        assert !Double.isNaN(lonRad);
        final double lat = latRad * (180.0 / Math.PI);
        final double lon = lonRad * (180.0 / Math.PI);
        return fromDeg(lat, lon);
    }

    /**
     * Calculate the distance between two points. This algorithm does not take the curvature of the Earth into
     * account, so it only works for small distance up to, say 200 km, and not too close to the poles.
     *
     * @param p1 Point 1.
     * @param p2 Point 2.
     * @return Straight distance between p1 and p2. Only accurate for small distances up to 200 km.
     */
    public static double distanceInMeters(@Nonnull final Point p1, @Nonnull final Point p2) {
        checkNonnull("p1", p1);
        checkNonnull("p2", p2);

        final Point from;
        final Point to;
        if (p1.getLonDeg() <= p2.getLonDeg()) {
            from = p1;
            to = p2;
        } else {
            from = p2;
            to = p1;
        }

        // Calculate mid point of 2 latitudes.
        final double avgLat = (from.getLatDeg() + to.getLatDeg()) / 2.0;

        final double deltaLatDeg = Math.abs(to.getLatDeg() - from.getLatDeg());
        final double deltaLonDeg360 = Math.abs(to.getLonDeg() - from.getLonDeg());
        final double deltaLonDeg = ((deltaLonDeg360 <= 180.0) ? deltaLonDeg360 : (360.0 - deltaLonDeg360));

        // Meters per longitude is fixed; per latitude requires * cos(avg(lat)).
        final double deltaXMeters = degreesLonToMetersAtLat(deltaLonDeg, avgLat);
        final double deltaYMeters = degreesLatToMeters(deltaLatDeg);


        // Calculate length through Earth. This is an approximation, but works fine for short distances.
        return Math.sqrt((deltaXMeters * deltaXMeters) + (deltaYMeters * deltaYMeters));
    }

    public static double degreesLatToMeters(final double latDegrees) {
        return latDegrees * METERS_PER_DEGREE_LAT;
    }

    public static double degreesLonToMetersAtLat(final double lonDegrees, final double lat) {
        return lonDegrees * METERS_PER_DEGREE_LON_EQUATOR * Math.cos(Math.toRadians(lat));
    }

    public static double metersToDegreesLonAtLat(final double eastMeters, final double lat) {
        return (eastMeters / METERS_PER_DEGREE_LON_EQUATOR) / Math.cos(Math.toRadians(lat));
    }

    @Nonnull
    @Override
    public String toString() {
        return defined ? ("(" + getLatDeg() + ", " + getLonDeg() + ')') : "undefined";
    }

    @SuppressWarnings("NonFinalFieldReferencedInHashCode")
    @Override
    public int hashCode() {
        return Arrays.hashCode(new Object[]{latMicroDeg, lonMicroDeg, latFractionOnlyDeg, lonFractionOnlyDeg, defined});
    }

    @SuppressWarnings("NonFinalFieldReferenceInEquals")
    @Override
    public boolean equals(final Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof Point)) {
            return false;
        }
        final Point that = (Point) obj;
        return (this.latMicroDeg == that.latMicroDeg) &&
                (this.lonMicroDeg == that.lonMicroDeg) &&
                (this.latFractionOnlyDeg == that.latFractionOnlyDeg) &&
                (this.lonFractionOnlyDeg == that.lonFractionOnlyDeg) &&
                (this.defined == that.defined);
    }

    // -----------------------------------------------------------------------
    // (Package) private data and methods.
    // -----------------------------------------------------------------------

    // Constants to convert between Degrees, MicroDegrees and Fractions
    static final double MICRODEG_TO_DEG_FACTOR = 1000000.0;
    static final double MAX_PRECISION_FACTOR = 810000.0;
    static final double LAT_MICRODEG_TO_FRACTIONS_FACTOR = MAX_PRECISION_FACTOR;
    static final double LON_MICRODEG_TO_FRACTIONS_FACTOR = MAX_PRECISION_FACTOR * 4;
    static final double LAT_TO_FRACTIONS_FACTOR = MICRODEG_TO_DEG_FACTOR * LAT_MICRODEG_TO_FRACTIONS_FACTOR;
    static final double LON_TO_FRACTIONS_FACTOR = MICRODEG_TO_DEG_FACTOR * LON_MICRODEG_TO_FRACTIONS_FACTOR;

    private int latMicroDeg;            // Whole nr of MICRODEG_TO_DEG_FACTOR.
    private int lonMicroDeg;            // Whole nr of MICRODEG_TO_DEG_FACTOR.
    private int latFractionOnlyDeg;     // Whole nr of LAT_TO_FRACTIONS_FACTOR, relative to latMicroDeg.
    private int lonFractionOnlyDeg;     // Whole nr of LON_TO_FRACTIONS_FACTOR, relative to lonMicroDeg.

    /**
     * Points can be "undefined" within the mapcode implementation, but never outside of that.
     * Any methods creating or setting undefined points must be package private and external
     * interfaces must never pass undefined points to callers.
     */
    private boolean defined;

    /**
     * Private constructors.
     */
    private Point() {
        defined = false;
    }

    /**
     * Public construction, from floating point degrees (potentially lossy).
     */
    @SuppressWarnings("NumericCastThatLosesPrecision")
    private Point(final double latDeg, final double lonDeg) {

        double lat = latDeg + 90;
        if (lat < 0) {
            lat = 0;
        } else if (lat > 180) {
            lat = 180;
        }

        // Rounding factor.
        final double fractionRounding = 0.1;

        // Lat now [0..180].
        lat = lat * LAT_TO_FRACTIONS_FACTOR;
        double latFractionOnly = Math.floor(lat + fractionRounding);
        latMicroDeg = (int) (latFractionOnly / LAT_MICRODEG_TO_FRACTIONS_FACTOR);
        latFractionOnly = latFractionOnly - ((double) latMicroDeg * LAT_MICRODEG_TO_FRACTIONS_FACTOR);
        latFractionOnlyDeg = (int) latFractionOnly;
        latMicroDeg = latMicroDeg - MICRO_DEG_90;

        // Math.floor has limited precision for really large values, so we need to limit the lon explicitly.
        double lon = Math.min(360.0, Math.max(0.0, lonDeg - (360.0 * Math.floor(lonDeg / 360.0))));
        if (Double.compare(lon, 360.0) == 0) {
            lon = 0.0;
        }

        // Lon now in [0..360>.
        lon = lon * LON_TO_FRACTIONS_FACTOR;
        double lonFractionOnly = Math.floor(lon + fractionRounding);
        lonMicroDeg = (int) (lonFractionOnly / LON_MICRODEG_TO_FRACTIONS_FACTOR);
        lonFractionOnly = lonFractionOnly - ((double) lonMicroDeg * LON_MICRODEG_TO_FRACTIONS_FACTOR);
        lonFractionOnlyDeg = (int) lonFractionOnly;

        // Wrap lonMicroDeg from [0..360> to [-180..180).
        if (lonMicroDeg >= MICRO_DEG_180) {
            lonMicroDeg = lonMicroDeg - MICRO_DEG_360;
        }

        defined = true;
    }

    /**
     * Get the the longitude "fractions", which is a whole number of 1/LON_TO_FRACTIONS_FACTOR-th
     * degrees versus the millionths of degrees.
     */
    int getLonFraction() {
        assert defined;
        return lonFractionOnlyDeg;
    }

    /**
     * Get the the latitude "fractions", which is a whole number of 1/LAT_TO_FRACTIONS_FACTOR-th
     * degrees versus the millionths of degrees
     */
    int getLatFraction() {
        assert defined;
        return latFractionOnlyDeg;
    }

    /**
     * Package private construction, from integer fractions (no loss of precision).
     */
    @SuppressWarnings("NumericCastThatLosesPrecision")
    @Nonnull
    static Point fromLatLonFractions(final double latFraction, final double lonFraction) {
        final Point p = new Point();
        p.latMicroDeg = (int) Math.floor(latFraction / LAT_MICRODEG_TO_FRACTIONS_FACTOR);
        p.latFractionOnlyDeg = (int) (latFraction - (LAT_MICRODEG_TO_FRACTIONS_FACTOR * p.latMicroDeg));
        p.lonMicroDeg = (int) Math.floor(lonFraction / LON_MICRODEG_TO_FRACTIONS_FACTOR);
        p.lonFractionOnlyDeg = (int) (lonFraction - (LON_MICRODEG_TO_FRACTIONS_FACTOR * p.lonMicroDeg));
        p.defined = true;
        return p.wrap();
    }

    static int degToMicroDeg(final double deg) {
        //noinspection NumericCastThatLosesPrecision
        return (int) Math.floor(deg * MICRODEG_TO_DEG_FACTOR);
    }

    static double microDegToDeg(final int microDeg) {
        return ((double) microDeg) / MICRODEG_TO_DEG_FACTOR;
    }

    @Nonnull
    Point wrap() {
        if (defined) {
            // Cut latitude to [-90, 90].
            if (latMicroDeg < -MICRO_DEG_90) {
                latMicroDeg = -MICRO_DEG_90;
                latFractionOnlyDeg = 0;
            }
            if (latMicroDeg > MICRO_DEG_90) {
                latMicroDeg = MICRO_DEG_90;
                latFractionOnlyDeg = 0;
            }
            // Map longitude to [-180, 180). Values outside this range are wrapped to this range.
            lonMicroDeg %= MICRO_DEG_360;
            if (lonMicroDeg >= MICRO_DEG_180) {
                lonMicroDeg -= MICRO_DEG_360;
            } else if (lonMicroDeg < -MICRO_DEG_180) {
                lonMicroDeg += MICRO_DEG_360;
            }
        }
        return this;
    }

    /**
     * Create an undefined points. No latitude or longitude can be obtained from it.
     * Only within the mapcode implementation points can be undefined, so this methods is package private.
     *
     * @return Undefined points.
     */
    @Nonnull
    static Point undefined() {
        return new Point();
    }

    /**
     * Set a point to be undefined, invalidating the latitude and longitude.
     * Only within the mapcode implementation points can be undefined, so this methods is package private.
     */
    void setUndefined() {
        defined = false;
    }

    /**
     * Return whether the point is defined or not.
     * Only within the mapcode implementation points can be undefined, so this methods is package private.
     *
     * @return True if defined. If false, no lat/lon is available.
     */
    boolean isDefined() {
        return defined;
    }
}