Copyright (C) 2019-2022 HERE Global B.V. and its affiliate(s).

All rights reserved.

This software and other materials contain proprietary information

controlled by HERE and are protected by applicable copyright legislation.

Any use and utilization of this software and other materials and

disclosure to any third parties is conditional upon having a separate

agreement with HERE for the access, use, utilization or disclosure of this

software. In the absence of such agreement, the use of the software is not

allowed.

"""
Module to operate with HERETile tiling scheme.
"""

from collections import OrderedDict as OrdDict
from typing import Iterator, Optional, OrderedDict, Tuple

from mapquadlib import BoundingBox, GeoCoordinate, HereQuad
from mapquadlib.common.mapquad_iterator import MapQuadIterator
from shapely.geometry import LinearRing, Point, Polygon, box
from shapely.geometry.base import BaseGeometry

The term "Tile ID" here means the integer (long) key of a HereQuad.

TileID = int

[docs]
def root() -> TileID:
"""
Return the ID of the root tile.
"""
return 1

[docs]
def is_valid(tile_id) -> bool:
"""
Check if an integer is a valid tile ID.

:param tile_id: an integer
:return: if the passed integer is a valid tile identifier

Valid tile IDs

is_valid(1)
True
is_valid(5)
True
is_valid("5")
True
is_valid(from_coordinates(13.3, 52.5, 7))
True

Invalid tile IDs

is_valid(0)
False
is_valid(7)
False
is_valid("7")
False
is_valid(from_coordinates(13.3, 52.5, 7) << 1)
False
"""
try:
tile_id = int(tile_id)
HereQuad.validate_key(tile_id)
return True
except TypeError:
return False
except ValueError:
return False

[docs]
def from_x_y_level(x: int, y: int, level: int) -> TileID:
"""
Return the tile given X and Y components and level.

:param x: the tile X component
:param y: the tile Y component
:param level: the tiling level
:return: the tile ID
"""
return TileID(HereQuad.from_x_y_level(x, y, level).long_key)

[docs]
def from_coordinates(lng: float, lat: float, level: int) -> TileID:
"""
Return the tile that contains a point.

:param lng: longitude
:param lat: latitude
:param level: the tiling level
:return: the tile ID
:raises ValueError: if no tile ID can correspond to the input parameters

Berlin main station

from_coordinates(13.36937, 52.52507, 14)
377894440

Boundary conditions: at a given level, one points belongs to only one tile.
For this purpose, the western and southern border of a tile is considered
included in the tile, while eastern and norther borders are not.
A point located on the border between two tiles belongs to only of the them.

Longitude boundary

from_coordinates(90, 45, 2)
23

Latitude boundary

from_coordinates(45, 0, 2)
22

If you're interested in obtaining two or four tile IDs in case the
point is on a border or corner of a tile, please use in_geometry.
"""
if level < 0:
raise ValueError("Tile level cannot be negative.")
return TileID(HereQuad.from_lat_lng_level(lat, lng, level).long_key)

[docs]
def from_point(pt: Point, level: int) -> TileID:
"""
Return the tile that contains a point.

:param pt: the point
:param level: the tile level
:return: the tile ID

Berlin main station

p = Point(13.36937, 52.52507)
from_point(p, 14)
377894440

Boundary conditions: at a given level, one points belongs to only one tile.
For this purpose, the western and southern border of a tile is considered
included in the tile, while eastern and norther borders are not.
A point located on the border between two tiles belongs to only of the them.

Longitude boundary

p = Point(90, 45)
from_point(p, 2)
23

Latitude boundary

p = Point(45, 0)
from_point(p, 2)
22

If you're interested in obtaining two or four tile IDs in case the
point is on a border or corner of a tile, please use in_geometry.
"""
return from_coordinates(pt.x, pt.y, level)

[docs]
def in_bounding_box(
west: float, south: float, east: float, north: float, level: int, fully_contained: bool = False
) -> Iterator[TileID]:
"""
Return the tiles that are included the given bounding box.

If fully_contained is false, some of the returned tiles may be partially
outside the bounding box. Otherwise, return only the tiles wholly inside the bounding box.

:param west: western border of the bounding box
:param south: southern border of the bounding box
:param east: eastern border of the bounding box
:param north: northern border of the bounding box
:param level: the tiling level
:param fully_contained: return only tiles wholly inside the bounding box
:yield: the tile IDs in the order of West to East first, then South to North.

next(in_bounding_box(
... west=13.36937,
... south=52.52507,
... east=13.36938,
... north=52.52508,
... level=12
... ))
23618402
list(in_bounding_box(
... west=-115.81741,
... south=46.16326,
... east=-115.51230,
... north=46.39060,
... level=12,
... fully_contained=True
... ))
[19681773, 19681784]
"""
bbox = BoundingBox(west, south, east, north)
dummy_quad = HereQuad.from_long_key(1)
for q in MapQuadIterator(quad_type=dummy_quad, level=level, bounding_box=bbox):
if not fully_contained or bbox.covers(q.bounding_box):
yield q.long_key

[docs]
def between_points(
south_west: Point,
north_east: Point,
level: int,
fully_contained: bool = False,
) -> Iterator[TileID]:
"""
Return the tiles that are included the the bounding box identified by two points.

:param south_west: point at the south-western corner of the bounding box
:param north_east: point at the north-eastern corner of the bounding box
:param level: the tiling level
:param fully_contained: return only tiles wholly inside the bounding box
:return: the tile IDs in the order of West to East first, then South to North.
"""
west = south_west.x
south = south_west.y
east = north_east.x
north = north_east.y

return in_bounding_box(west, south, east, north, level, fully_contained)

[docs]
def in_geometry_bounds(
geometry: BaseGeometry, level: int, fully_contained: bool = False
) -> Iterator[TileID]:
"""
Return the tiles that are included in the bounds of a geometry.

If fully_contained is false, some of the returned tiles may be partially
outside the bounds. Otherwise, return only the tiles wholly inside the bounds.

:param geometry: an arbitrary geometry
:param level: the tiling level
:param fully_contained: return only tiles wholly inside the bounding box
:return: iterator of tile IDs in the order of West to East first, then South to North.
"""
west, south, east, north = geometry.bounds
return in_bounding_box(west, south, east, north, level, fully_contained)

[docs]
def in_geometry(
geometry: BaseGeometry, level: int, fully_contained: bool = False
) -> Iterator[TileID]:
"""
Return the tiles that are included in the given geometry.

:param geometry: an arbitrary geometry
:param level: the tiling level
:param fully_contained: return only tiles wholly inside the geometry
:return: iterator of tile IDs, in no particular order

If fully_contained is false, some of the returned tiles may be partially
outside the geometry. Otherwise, return only the tiles wholly inside the geometry.

Inclusion is modeled as the shapely relation intersects (fully_contained is false)
or contains (otherwise) between the geometry and the tiles.

Examples (fully_contained is false):

• if the geometry is a point, return one, two or four tiles
• if the geometry is a line string, it return all the tiles along the line
• if the geometry is a polygon, it returns all the tiles intersecting with the polygon
• for multi-geometries, return the union of the tiles in each geometry

Examples (fully_contained is true):

• if the geometry is a point, nothing is returned
• if the geometry is a line string, nothing is returned
• if the geometry is a polygon, it returns all the tiles contained in the polygon
• for multi-geometries, return the union of the tiles in each geometry
  """

def filter_tile(tile_id):
poly = get_polygon(tile_id)
return (fully_contained and geometry.contains(poly)) or (
not fully_contained and geometry.intersects(poly)
)

return filter(filter_tile, in_geometry_bounds(geometry, level, fully_contained=False))

[docs]
def get_x(tile_id) -> int:
"""
Return the X component of a given tile.

:param tile_id: the tile ID
:return: the X component of the tile ID
"""
tile_id = int(tile_id)
return int(HereQuad.from_long_key(tile_id).x)

[docs]
def get_y(tile_id) -> int:
"""
Return the Y component of a given tile.

:param tile_id: the tile ID
:return: the Y component of the tile ID
"""
tile_id = int(tile_id)
return int(HereQuad.from_long_key(tile_id).y)

[docs]
def get_level(tile_id) -> int:
"""
Return the level of a given tile.

:param tile_id: the tile ID
:return: the level of the tile ID
"""
tile_id = int(tile_id)
return int(HereQuad.from_long_key(tile_id).level)

[docs]
def get_x_y_level(tile_id) -> Tuple[int, int, int]:
"""
Return the X and Y components and level of a given tile.

:param tile_id: the tile ID
:return: the components and level, a tuple of 3 elements: (x, y, level)
"""
tile_id = int(tile_id)
quad = HereQuad.from_long_key(tile_id)
return quad.x, quad.y, quad.level

[docs]
def get_center_coordinates(tile_id) -> Tuple[float, float]:
"""
Return the center point of given tile.

:param tile_id: the tile ID
:return: the center point, a tuple of 2 coordinates: (longitude, latitude)
"""
tile_id = int(tile_id)
c = HereQuad.from_long_key(tile_id).bounding_box.center
return c.lng, c.lat

[docs]
def get_center_point(tile_id) -> Point:
"""
Return the center point of given tile.

:param tile_id: the tile ID
:return: the center point
"""
tile_id = int(tile_id)
c = HereQuad.from_long_key(tile_id).bounding_box.center
return Point(c.lng, c.lat)

[docs]
def get_corners(tile_id) -> Tuple[Point, Point]:
"""
Return the southwestern and northeastern corners of given tile.

:param tile_id: the tile ID
:return: the corner points, a tuple of 2 points: (sw, ne)
"""
tile_id = int(tile_id)
bbox = HereQuad.from_long_key(tile_id).bounding_box
return Point(bbox.west, bbox.south), Point(bbox.east, bbox.north)

[docs]
def get_bounds(tile_id) -> Tuple[float, float, float, float]:
"""
Return the bounds of given tile.

This function returns bounds following the same
convention of the bounds function of shapely.

:param tile_id: the tile ID
:return: the bounds, a tuple of 4 coordinates: (west, south, east, north)

get_bounds(23618402)
(13.359375, 52.470703125, 13.447265625, 52.55859375)
"""
tile_id = int(tile_id)
bbox = HereQuad.from_long_key(tile_id).bounding_box
return bbox.west, bbox.south, bbox.east, bbox.north

[docs]
def get_boundary_ring(tile_id) -> LinearRing:
"""
Return the boundary of given tile as linear ring.
The ring describes the boundary counter-clockwise.
It contains 5 points, since a linear ring is always closed
by repeating its first point.
:param tile_id: the tile ID
:return: the tile boundary as linear ring

lr = get_boundary_ring(23618402)
lr.equals(LinearRing([(13.447265625, 52.470703125),
... (13.447265625, 52.55859375),
... (13.359375, 52.55859375),
... (13.359375, 52.470703125),
... (13.447265625, 52.470703125)
... ]))
True
"""
tile_id = int(tile_id)
return get_polygon(tile_id).exterior

[docs]
def get_polygon(tile_id) -> Polygon:
"""
Return the given tile as polygon.
:param tile_id: the tile ID
:return: the tile as polygon

p = get_polygon(23618402)
p.equals(Polygon([(13.447265625, 52.470703125),
... (13.447265625, 52.55859375),
... (13.359375, 52.55859375),
... (13.359375, 52.470703125),
... (13.447265625, 52.470703125)
... ]))
True
"""
tile_id = int(tile_id)
bbox = HereQuad.from_long_key(tile_id).bounding_box
return box(bbox.west, bbox.south, bbox.east, bbox.north)

[docs]
def contains_coordinates(tile_id, lng: float, lat: float) -> bool:
"""
Return if the tile contains a point.

The check includes the tile boundary, aligned with the
way shapely intersects operates.
:param tile_id: the tile ID
:param lng: longitude
:param lat: latitude
:return: if the point is inside the given tile

tile = from_x_y_level(2, 1, 2)
contains_coordinates(tile, 45, 45)
True
contains_coordinates(tile, 0, 0)
True
"""
tile_id = int(tile_id)
quad = HereQuad.from_long_key(tile_id)
return bool(quad.bounding_box.contains(GeoCoordinate(lng, lat)))

[docs]
def contains_point(tile_id, pt: Point) -> bool:
"""
Return if the tile contains a point.

This method is more efficient than contains_geometry for points.

The check includes the tile boundary, aligned with the
way shapely intersects operates.

:param tile_id: the tile ID
:param pt: a point
:return: if the point is inside the given tile

tile = from_x_y_level(2, 1, 2)
contains_point(tile, Point(90, 45))
True
contains_point(tile, Point(0, 0))
True
"""
tile_id = int(tile_id)
return contains_coordinates(tile_id, pt.x, pt.y)

[docs]
def contains_geometry(tile_id, geometry: BaseGeometry, fully_contained=False) -> bool:
"""
Return if the tile contains a geometry.

Inclusion is modeled as the shapely relation intersects (fully_contained is false)
or contains (otherwise) between the tile and the geometry.

:param tile_id: the tile ID
:param geometry: any geometry
:param fully_contained: check if the geometry is fully contained in the tile
:return: if the geometry is contained in the given tile, fully or partially
"""
tile_id = int(tile_id)
if fully_contained:
return bool(get_polygon(tile_id).contains(geometry))
else:
return bool(get_polygon(tile_id).intersects(geometry))

[docs]
def is_contained_in_geometry(tile_id, geometry: BaseGeometry, fully_contained=False) -> bool:
"""
Return if the tile is contained in a geometry.

Inclusion is modeled as the shapely relation intersects (fully_contained is false)
or contains (otherwise) between the geometry and the tile.

:param tile_id: the tile ID
:param geometry: any geometry
:param fully_contained: check if the tile is fully contained in the geometry
:return: if the tile is contained in the given geometry, fully or partially
"""
tile_id = int(tile_id)
if fully_contained:
return bool(geometry.contains(get_polygon(tile_id)))
else:
return bool(geometry.intersects(get_polygon(tile_id)))

[docs]
def ancestor(tile_id, level: Optional[int] = None) -> Optional[TileID]:
"""
Return the ancestor tile at the given level for the given tile.

:param tile_id: the tile ID
:param level: the tiling level
:return: the tile ID of the ancestor or parent, when existing
"""
tile_id = int(tile_id)
quad = HereQuad.from_long_key(tile_id)
if level is not None:
if quad.level < level:
return None
elif quad.level == level:
return TileID(tile_id)
return TileID(quad.ancestor(level).long_key)
else:
if quad.level < 1:
return None
return TileID(quad.ancestor().long_key)

[docs]
def ancestors(tile_id, level: Optional[int] = None) -> OrderedDict[int, int]:
"""
For a given tile_id return a dictionary of its ancestor levels and tile IDs.

If level is not provided the result contains tile IDs of all ancestors
up to the largest "root" tile, else up to the specified level only.

:param tile_id: the tile ID
:param level: the tiling level
:return: an ordered dictionary with tile levels mapped to tile IDs
"""
tile_id = int(tile_id)
result = OrdDict()
q = HereQuad.from_long_key(tile_id)
while True:
try:
q = q.ancestor()
except ValueError:
break
if level is None or q.level > level - 1:
result[q.level] = q.long_key
result.move_to_end(q.level, last=False)
return result

[docs]
def descendants(tile_id, level: Optional[int] = None) -> Iterator[TileID]:
"""
Return the tile IDs of all descendants at some level for a given tile.
"""
tile_id = int(tile_id)
quad = HereQuad.from_long_key(tile_id)
desc_quads = quad.descendants(level) if level is not None else quad.descendants()
for d in desc_quads:
yield d.long_key

[docs]
def is_parent(tile_id, of_tile_id) -> bool:
"""
Check if a tile is the direct parent of another tile.

:param tile_id: the subject tile ID
:param of_tile_id: check the relationship of the subject with this tile ID
:return: if tile_id is the parent of of_tile_id
"""
tile_id = int(tile_id)
of_tile_id = int(of_tile_id)
qa = HereQuad.from_long_key(tile_id)
qb = HereQuad.from_long_key(of_tile_id)
return qb.level > 0 and bool(qa == qb.ancestor())

[docs]
def is_descendant(tile_id, of_tile_id) -> bool:
"""
Check if a tile is a direct descendant of another tile.

:param tile_id: the subject tile ID
:param of_tile_id: check the relationship of the subject with this tile ID
:return: if tile_id is a descendant of of_tile_id
"""
tile_id = int(tile_id)
of_tile_id = int(of_tile_id)
qa = HereQuad.from_long_key(tile_id)
qb = HereQuad.from_long_key(of_tile_id)
for d in qb.descendants():
if d == qa:
return True
return False

[docs]
def neighbors(tile_id, level: Optional[int] = None) -> Iterator[TileID]:
"""
Return tile IDs of all neighbors on given level for the given tile.

:param tile_id: the subject tile ID
:param level: the tiling level
:yield: neighboring tile IDs, in no particular order
"""
tile_id = int(tile_id)
q = HereQuad.from_long_key(tile_id)
for n in q.neighbors(level) if level is not None else q.neighbors():
yield n.long_key