open location code / published by https://github.com/dacr/code-examples-manager #4075d3d8-e8de-46d9-a984-e5e3a694a34c/1d879d100a152d381eed9b1c5145944deef0966a

algo-open-location-code.sc

// summary : open location code
// keywords : scala, open-location-code, olc, pluscodes, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : 4075d3d8-e8de-46d9-a984-e5e3a694a34c
// created-on : 2024-02-11T10:09:30+01:00
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file

// ---------------------
//> using scala  "3.3.1"
// ---------------------

/* MORE INFORMATION :
  - https://en.wikipedia.org/wiki/Open_Location_Code
  - https://github.com/google/open-location-code
  - https://maps.google.com/pluscodes/
 */

import scala.io.AnsiColor.*
import scala.util.Random.*
import scala.math.*

// Inspired from https://github.com/google/open-location-code/blob/main/java/src/main/java/com/google/openlocationcode/OpenLocationCode.java

case class CodeArea(
  southLatitude: Double,
  westLongitude: Double,
  northLatitude: Double,
  eastLongitude: Double,
  length: Int
) {
  def longitudeWidth  = eastLongitude - westLongitude
  def centerLatitude  = (southLatitude + northLatitude) / 2
  def centerLongitude = (westLongitude + eastLongitude) / 2

}

case class OpenLocationCode private (code: String) {
  import OpenLocationCode.*
  def decode(): CodeArea = {
    if (!isFullCode(code)) throw IllegalStateException(s"Method decode() could only be called on valid full codes, code was $code.")
    // Strip padding and separator characters out of the code.
    val clean = code.replace(String.valueOf(SEPARATOR), "").replace(String.valueOf(PADDING_CHARACTER), "")

    // Initialise the values. We work them out as integers and convert them to doubles at the end.
    var latVal      = -LATITUDE_MAX * LAT_INTEGER_MULTIPLIER
    var lngVal      = -LONGITUDE_MAX * LNG_INTEGER_MULTIPLIER
    // Define the place value for the digits. We'll divide this down as we work through the code.
    var latPlaceVal = LAT_MSP_VALUE
    var lngPlaceVal = LNG_MSP_VALUE
    var i           = 0
    while (i < Math.min(clean.length, PAIR_CODE_LENGTH)) {
      latPlaceVal /= ENCODING_BASE
      lngPlaceVal /= ENCODING_BASE
      latVal += CODE_ALPHABET.indexOf(clean.charAt(i)) * latPlaceVal
      lngVal += CODE_ALPHABET.indexOf(clean.charAt(i + 1)) * lngPlaceVal

      i += 2
    }
    i = PAIR_CODE_LENGTH
    while (i < Math.min(clean.length, MAX_DIGIT_COUNT)) {
      latPlaceVal /= GRID_ROWS
      lngPlaceVal /= GRID_COLUMNS
      val digit = CODE_ALPHABET.indexOf(clean.charAt(i))
      val row   = digit / GRID_COLUMNS
      val col   = digit % GRID_COLUMNS
      latVal += row * latPlaceVal
      lngVal += col * lngPlaceVal

      i += 1
    }
    val latitudeLo  = latVal.toDouble / LAT_INTEGER_MULTIPLIER
    val longitudeLo = lngVal.toDouble / LNG_INTEGER_MULTIPLIER
    val latitudeHi  = (latVal + latPlaceVal).toDouble / LAT_INTEGER_MULTIPLIER
    val longitudeHi = (lngVal + lngPlaceVal).toDouble / LNG_INTEGER_MULTIPLIER
    CodeArea(latitudeLo, longitudeLo, latitudeHi, longitudeHi, Math.min(clean.length, MAX_DIGIT_COUNT))
  }

  def isFull = code.indexOf(SEPARATOR) == SEPARATOR_POSITION

  def isShort = code.indexOf(SEPARATOR) >= 0 && code.indexOf(SEPARATOR) < SEPARATOR_POSITION

  def isPadded = code.indexOf(PADDING_CHARACTER) >= 0

  def shorten(referenceLatitude: Double, referenceLongitude: Double): OpenLocationCode = {
    if (!isFull) throw new IllegalStateException("shorten() method could only be called on a full code.")
    if (isPadded) throw new IllegalStateException("shorten() method can not be called on a padded code.")

    val codeArea = decode()
    val range    = Math.max(Math.abs(referenceLatitude - codeArea.centerLatitude), Math.abs(referenceLongitude - codeArea.centerLongitude))
    // We are going to check to see if we can remove three pairs, two pairs or just one pair of
    // digits from the code.
    for (i <- 4 to 1 by -1) {
      // Check if we're close enough to shorten. The range must be less than 1/2
      // the precision to shorten at all, and we want to allow some safety, so
      // use 0.3 instead of 0.5 as a multiplier.
      if (range < (computeLatitudePrecision(i * 2) * 0.3)) {
        // We're done.
        return new OpenLocationCode(code.substring(i * 2))
      }
    }
    throw new IllegalArgumentException("Reference location is too far from the Open Location Code center.")
  }

  def recover(thatReferenceLatitude: Double, thatReferenceLongitude: Double): OpenLocationCode = {
    if (isFull) {
      // Note: each code is either full xor short, no other option.
      return this
    }
    val referenceLatitude  = clipLatitude(thatReferenceLatitude)
    val referenceLongitude = normalizeLongitude(thatReferenceLongitude)

    val digitsToRecover = SEPARATOR_POSITION - code.indexOf(SEPARATOR)
    // The precision (height and width) of the missing prefix in degrees.
    val prefixPrecision = Math.pow(ENCODING_BASE, 2 - (digitsToRecover / 2))

    // Use the reference location to generate the prefix.
    val recoveredPrefix    = OpenLocationCode(referenceLatitude, referenceLongitude).code.substring(0, digitsToRecover)
    // Combine the prefix with the short code and decode it.
    val recovered          = OpenLocationCode(recoveredPrefix + code)
    val recoveredCodeArea  = recovered.decode()
    // Work out whether the new code area is too far from the reference location. If it is, we
    // move it. It can only be out by a single precision step.
    var recoveredLatitude  = recoveredCodeArea.centerLatitude
    var recoveredLongitude = recoveredCodeArea.centerLongitude

    // Move the recovered latitude by one precision up or down if it is too far from the reference,
    // unless doing so would lead to an invalid latitude.
    val latitudeDiff = recoveredLatitude - referenceLatitude
    if (latitudeDiff > prefixPrecision / 2 && recoveredLatitude - prefixPrecision > -LATITUDE_MAX) recoveredLatitude -= prefixPrecision
    else if (latitudeDiff < -prefixPrecision / 2 && recoveredLatitude + prefixPrecision < LATITUDE_MAX) recoveredLatitude += prefixPrecision

    // Move the recovered longitude by one precision up or down if it is too far from the
    // reference.
    val longitudeDiff = recoveredCodeArea.centerLongitude - referenceLongitude
    if (longitudeDiff > prefixPrecision / 2) recoveredLongitude -= prefixPrecision
    else if (longitudeDiff < -prefixPrecision / 2) recoveredLongitude += prefixPrecision

    OpenLocationCode.apply(recoveredLatitude, recoveredLongitude, recovered.code.length - 1)
  }

  def contains(latitude: Double, longitude: Double) = {
    val codeArea = decode()
    codeArea.southLatitude <= latitude &&
    latitude < codeArea.northLatitude &&
    codeArea.westLongitude <= longitude &&
    longitude < codeArea.eastLongitude
  }
}

object OpenLocationCode {
  // Provides a normal precision code, approximately 14x14 meters. // Provides a normal precision code, approximately 14x14 meters.
  val CODE_PRECISION_NORMAL = 10

  // The character set used to encode the values.
  val CODE_ALPHABET = "23456789CFGHJMPQRVWX"

  // A separator used to break the code into two parts to aid memorability.
  val SEPARATOR = '+'

  // The character used to pad codes.
  val PADDING_CHARACTER = '0'

  // The number of characters to place before the separator.
  private val SEPARATOR_POSITION = 8

  // The max number of digits to process in a plus code.
  val MAX_DIGIT_COUNT = 15

  // Maximum code length using just lat/lng pair encoding.
  private val PAIR_CODE_LENGTH = 10

  // Number of digits in the grid coding section.
  private val GRID_CODE_LENGTH = MAX_DIGIT_COUNT - PAIR_CODE_LENGTH

  // The base to use to convert numbers to/from.
  private val ENCODING_BASE = CODE_ALPHABET.length

  // The maximum value for latitude in degrees.
  private val LATITUDE_MAX = 90

  // The maximum value for longitude in degrees.
  private val LONGITUDE_MAX = 180

  // Number of columns in the grid refinement method.
  private val GRID_COLUMNS = 4

  // Number of rows in the grid refinement method.
  private val GRID_ROWS = 5

  // Value to multiple latitude degrees to convert it to an integer with the maximum encoding
  // precision. I.e. ENCODING_BASE**3 * GRID_ROWS**GRID_CODE_LENGTH
  private val LAT_INTEGER_MULTIPLIER = 8000 * 3125

  // Value to multiple longitude degrees to convert it to an integer with the maximum encoding
  // precision. I.e. ENCODING_BASE**3 * GRID_COLUMNS**GRID_CODE_LENGTH
  private val LNG_INTEGER_MULTIPLIER = 8000 * 1024

  // Value of the most significant latitude digit after it has been converted to an integer.
  private val LAT_MSP_VALUE = LAT_INTEGER_MULTIPLIER * ENCODING_BASE * ENCODING_BASE

  // Value of the most significant longitude digit after it has been converted to an integer.
  private val LNG_MSP_VALUE = LNG_INTEGER_MULTIPLIER * ENCODING_BASE * ENCODING_BASE

  /** Creates Open Location Code.
    *
    * @param latitude
    *   The latitude in decimal degrees.
    * @param longitude
    *   The longitude in decimal degrees.
    * @param codeLength
    *   The desired number of digits in the code.
    * @throws IllegalArgumentException
    *   if the code length is not valid.
    */
  def apply(thatLatitude: Double, thatLongitude: Double, thatCodeLength: Int): OpenLocationCode = {
    var latitude   = thatLatitude
    var longitude  = thatLongitude
    // Limit the maximum number of digits in the code.
    var codeLength = Math.min(thatCodeLength, MAX_DIGIT_COUNT)
    // Check that the code length requested is valid.
    if (codeLength < PAIR_CODE_LENGTH && (codeLength % 2 eq 1) || codeLength < 4) throw new IllegalArgumentException("Illegal code length " + codeLength)
    // Ensure that latitude and longitude are valid.
    latitude = clipLatitude(latitude)
    longitude = normalizeLongitude(longitude)

    // Latitude 90 needs to be adjusted to be just less, so the returned code can also be decoded.
    if (latitude eq LATITUDE_MAX) latitude = latitude - 0.9 * computeLatitudePrecision(codeLength)

    // Store the code - we build it in reverse and reorder it afterwards.
    val revCodeBuilder = new java.lang.StringBuilder()

    // Compute the code.
    // This approach converts each value to an integer after multiplying it by
    // the final precision. This allows us to use only integer operations, so
    // avoiding any accumulation of floating point representation errors.

    // Multiply values by their precision and convert to positive. Rounding
    // avoids/minimises errors due to floating point precision.
    var latVal = (Math.round((latitude + LATITUDE_MAX) * LAT_INTEGER_MULTIPLIER * 1e6) / 1e6).asInstanceOf[Long]
    var lngVal = (Math.round((longitude + LONGITUDE_MAX) * LNG_INTEGER_MULTIPLIER * 1e6) / 1e6).asInstanceOf[Long]

    // Compute the grid part of the code if necessary.
    if (codeLength > PAIR_CODE_LENGTH) {
      var i = 0
      while (i < GRID_CODE_LENGTH) {
        val latDigit = latVal % GRID_ROWS
        val lngDigit = lngVal % GRID_COLUMNS
        val ndx      = (latDigit * GRID_COLUMNS + lngDigit).asInstanceOf[Int]
        revCodeBuilder.append(CODE_ALPHABET.charAt(ndx))
        latVal /= GRID_ROWS
        lngVal /= GRID_COLUMNS

        i += 1
      }
    } else {
      latVal = (latVal / Math.pow(GRID_ROWS, GRID_CODE_LENGTH)).toLong
      lngVal = (lngVal / Math.pow(GRID_COLUMNS, GRID_CODE_LENGTH)).toLong
    }
    // Compute the pair section of the code.
    var i           = 0
    while (i < PAIR_CODE_LENGTH / 2) {
      revCodeBuilder.append(CODE_ALPHABET.charAt((lngVal % ENCODING_BASE).asInstanceOf[Int]))
      revCodeBuilder.append(CODE_ALPHABET.charAt((latVal % ENCODING_BASE).asInstanceOf[Int]))
      latVal /= ENCODING_BASE
      lngVal /= ENCODING_BASE
      // If we are at the separator position, add the separator.
      if (i == 0) revCodeBuilder.append(SEPARATOR)

      i += 1
    }
    // Reverse the code.
    val codeBuilder = revCodeBuilder.reverse

    // If we need to pad the code, replace some of the digits.
    if (codeLength < SEPARATOR_POSITION) {
      var i = codeLength
      while (i < SEPARATOR_POSITION) {
        codeBuilder.setCharAt(i, PADDING_CHARACTER)

        i += 1
      }
    }
    OpenLocationCode(codeBuilder.subSequence(0, Math.max(SEPARATOR_POSITION + 1, codeLength + 1)).toString)
  }

  /** Creates Open Location Code with the default precision length.
    *
    * @param latitude
    *   The latitude in decimal degrees.
    * @param longitude
    *   The longitude in decimal degrees.
    */
  def apply(latitude: Double, longitude: Double): OpenLocationCode = {
    apply(latitude, longitude, CODE_PRECISION_NORMAL)
  }

  /**
   * Creates Open Location Code object for the provided code.
   *
   * @param code A valid OLC code. Can be a full code or a shortened code.
   * @throws IllegalArgumentException when the passed code is not valid.
   */
  def fromCode(code: String): OpenLocationCode = {
    if (!isValidCode(code.toUpperCase))
      throw new IllegalArgumentException(s"The provided code '$code' is not a valid Open Location Code.")
    OpenLocationCode(code.toUpperCase)
  }


  /** Encodes latitude/longitude into 10 digit Open Location Code. This method is equivalent to creating the OpenLocationCode object and getting the code from it.
    *
    * @param latitude
    *   The latitude in decimal degrees.
    * @param longitude
    *   The longitude in decimal degrees.
    * @return
    *   The code.
    */
  def encode(latitude: Double, longitude: Double): String = {
    OpenLocationCode.apply(latitude, longitude).code
  }

  /** Returns whether the provided Open Location Code is a full Open Location Code.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is a full code.
    */
  @throws[IllegalArgumentException]
  def isFull(code: String): Boolean = OpenLocationCode.apply(code).isFull

  /** Returns whether the provided Open Location Code is a short Open Location Code.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is short.
    */
  @throws[IllegalArgumentException]
  def isShort(code: String): Boolean = OpenLocationCode.apply(code).isShort

  /** Returns whether the provided Open Location Code is a padded Open Location Code, meaning that it contains less than 8 valid digits.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is padded.
    */
  @throws[IllegalArgumentException]
  def isPadded(code: String): Boolean = OpenLocationCode(code).isPadded

  /** Returns whether the provided string is a valid Open Location code.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is a valid full or short code.
    */
  def isValidCode(thatCode: String): Boolean = {
    if (thatCode == null || thatCode.length < 2)  false
    else {
      val code = thatCode.toUpperCase
      // There must be exactly one separator.
      val separatorPosition = code.indexOf(SEPARATOR)
      if (separatorPosition == -1) return false
      if (separatorPosition != code.lastIndexOf(SEPARATOR)) return false
      // There must be an even number of at most 8 characters before the separator.
      if (separatorPosition % 2 != 0 || separatorPosition > SEPARATOR_POSITION) return false
      // Check first two characters: only some values from the alphabet are permitted.
      if (separatorPosition == SEPARATOR_POSITION) {
        // First latitude character can only have first 9 values.
        if (CODE_ALPHABET.indexOf(code.charAt(0)) > 8) return false
        // First longitude character can only have first 18 values.
        if (CODE_ALPHABET.indexOf(code.charAt(1)) > 17) return false
      }
      // Check the characters before the separator.
      var paddingStarted = false
      for (i <- 0 until separatorPosition) {
        if ((CODE_ALPHABET.indexOf(code.charAt(i)) eq -1) && code.charAt(i) != PADDING_CHARACTER) {
          // Invalid character.
          return false
        }
        if (paddingStarted) {
          // Once padding starts, there must not be anything but padding.
          if (code.charAt(i) != PADDING_CHARACTER) return false
        } else if (code.charAt(i) == PADDING_CHARACTER) {
          paddingStarted = true
          // Short codes cannot have padding
          if (separatorPosition < SEPARATOR_POSITION) return false
          // Padding can start on even character: 2, 4 or 6.
          if (i != 2 && i != 4 && i != 6) return false
        }
      }
      // Check the characters after the separator.
      if (code.length > separatorPosition + 1) {
        if (paddingStarted) return false
        // Only one character after separator is forbidden.
        if (code.length == separatorPosition + 2) return false
        for (i <- separatorPosition + 1 until code.length) {
          if (CODE_ALPHABET.indexOf(code.charAt(i)) eq -1) return false
        }
      }
      return true
    }
  }

  /** Returns if the code is a valid full Open Location Code.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is a valid full code.
    */
  def isFullCode(code: String): Boolean = {
    try {
      OpenLocationCode.apply(code).isFull
    } catch {
      case _: IllegalArgumentException => false
    }
  }

  /** Returns if the code is a valid short Open Location Code.
    *
    * @param code
    *   The code to check.
    * @return
    *   True if it is a valid short code.
    */
  def isShortCode(code: String): Boolean = {
    try {
      OpenLocationCode.apply(code).isShort
    } catch {
      case _: IllegalArgumentException => false
    }
  }

  private def clipLatitude(latitude: Double) = Math.min(Math.max(latitude, -LATITUDE_MAX), LATITUDE_MAX)

  private def normalizeLongitude(longitude: Double): Double = {
    if (longitude >= -LONGITUDE_MAX && longitude < LONGITUDE_MAX) {
      // longitude is within proper range, no normalization necessary
      longitude
    } else {
      // % in Java uses truncated division with the remainder having the same sign as
      // the dividend. For any input longitude < -360, the result of longitude%CIRCLE_DEG
      // will still be negative but > -360, so we need to add 360 and apply % a second time.
      val CIRCLE_DEG = 2 * LONGITUDE_MAX // 360 degrees
      (longitude % CIRCLE_DEG + CIRCLE_DEG + LONGITUDE_MAX) % CIRCLE_DEG - LONGITUDE_MAX
    }
  }

  /** Compute the latitude precision value for a given code length. Lengths <= 10 have the same precision for latitude and longitude, but lengths > 10 have different precisions due to the grid method
    * having fewer columns than rows. Copied from the JS implementation.
    */
  private def computeLatitudePrecision(codeLength: Int): Double = {
    if (codeLength <= CODE_PRECISION_NORMAL) Math.pow(ENCODING_BASE, (codeLength / -2 + 2).toDouble)
    else Math.pow(ENCODING_BASE, -3) / Math.pow(GRID_ROWS, codeLength - PAIR_CODE_LENGTH)
  }
}


// C673+RQ Plouarzel
// 8CWQC673+RQ
val openLocationCode = OpenLocationCode(48.41457616899414d, -4.7955160075925045d)
println(openLocationCode.code)
println(openLocationCode.isFull)

println(OpenLocationCode.fromCode("C673+RQ").code)
println(OpenLocationCode.fromCode("C673+RQ").isFull)